The query complexity of recovering a planted assignment from a random constraint-satisfaction instance with one-sided noise is studied, and bounds for nonadaptive algorithms are proved and adaptivity gives a factor $\exp(\Theta(k))$ improvement.
Abstract
We study the query complexity of recovering a planted assignment from a random constraint-satisfaction instance with one-sided noise. We consider the following 1-CNF recovery problem: an unknown binary string with $n/2$ ones and $n/2$ zeros is queried at individual variables. A query to a $1$-variable returns"$1$"with probability $p$ and"$0$"otherwise, while a $0$-variable always returns"$0$"(each query is a fresh noisy draw). The goal is to recover the binary string with probability at least $1 - \delta$. While the naive counting argument may suggest a query complexity of $\log_2 \binom{n}{n/2}=\Theta(n)$, we show that the query complexity is $(1+o(1))c(p) \frac{n}{2} \left( \log_2 n + \log_2(1/\delta)\right)$, where $c(p) = \tfrac{1}{-\log_2(1-p)}$. We then study planted $k$-CNF satisfaction with one-sided noise. Each $k$-set containing a $1$-variable is included as a clause independently with probability $p$, and an algorithm may ask whether any given $k$-set is a clause. Unlike the $1$-CNF case, a clause-existence query is one-shot: each $k$-set either is or is not a clause, so repeating yields no new information. The model is one-sided because an observed clause certifies that at least one queried variable is assigned 1, whereas its absence does not certify all are assigned 0. The goal is to recover the planted assignment with probability at least $1 - \delta$. The counting baseline is $\Theta(n)$, yet we prove a query complexity of $(1+o(1))\,c(p,k)\, \frac{n}{2}\left( \log_2 n + \log_2(1/\delta)\right)$, where $c(p,k) = \tfrac{1}{k(-\log_2(1-p))}$. These bounds are for adaptive algorithms. We also prove bounds for nonadaptive algorithms, showing that for fixed $p$, adaptivity gives a factor $\exp(\Theta(k))$ improvement. Our results also imply lower bounds for noisy sorting of $\{0,1\}$-valued strings, and we study a variant of the model with negations.
An even bigger separation is shown in this regime between randomized and deterministic algorithms: for the latter, $\Theta(\log n/\log\log n)$ rounds are necessary and sufficient to obtain near-optimal query complexity.
Deeparnab Chakrabarty, Aditi Dudeja, David Saulpic· 0 citations
A polynomial-time algorithm for exact recovery at constant correlation of Gaussian vectors, and an improved information-theoretic guarantee, showing that exact recovery is possible when $\rho^2 \gtrsim \max\{\log n/d,\sqrt{\log n/n}\}$.
Xiaochun Niu, T. Schramm, Jiaming Xu· arXiv.org· 0 citations
This paper investigates the direct sum question for expected randomized and distributional query complexity. Our main result gives an exact characterization of the amortized expected randomized query complexity. For any total relation $f$ and any error tolerance $\varepsilon \in [0,1]$, we prove \[ \lim_{n \to \infty} \frac{\overline{R}_\varepsilon(f^n)}{n} = (1 - \varepsilon) \overline{R}_0(f). \] Thus the amortization converts bounded-error into zero error with the exact multiplicative factor $1-\varepsilon$. We also prove corresponding liminf/limsup bounds for worst-case randomized and distributional query complexity. These results improve prior direct-sum bounds that were known only up to constant factors or in restricted error regimes, and they resolve an open question posed by Blais and Brody (2019). Additionally for one-sided computation of the function $\operatorname{OR}_n \circ f$, we obtain analogous exact amortized identities for both expected and worst-case cost. As applications, we obtain separations between amortized and single-instance costs, including unbounded separations for distributional complexity and randomized relations, and a quadratic barrier for randomized total functions.
Consider a poset - or equivalently an $n$-vertex DAG $G=(V, E)$ - and a boolean function $f: V \rightarrow \{0, 1\}$ on its vertex set. We say $f$ is monotone if $f(u) \leq f(v)$ for all $(u, v) \in E$. While there is extensive literature on the query complexity of testing monotonicity, we focus instead on the space complexity and initiate the study of this problem in the streaming setting. Namely, the edges of $G$ arrive in an arbitrary order, and the goal is to estimate distance to monotonicity of a given function $f$ using $\widetilde{O}(n)$ space. Note that while this space allows receiving and storing $f$, it is much smaller than the input graph $G$ which could have up to $\Omega(n^2)$ edges. Our main result is an algorithm that $(1+\epsilon)$-approximates distance to monotonicity in $\sqrt{n}^{1+o(1)}$ passes. We also prove that this is the best pass-complexity one can hope for, for any $O(1)$-approximation, short of improving the state-of-the-art streaming algorithm for $st$-reachability, which is a very well-studied problem. On the technical side, our algorithm approximates the size of maximum matching in (a subgraph of) the transitive closure of $G$. While the maximum matching problem has received significant attention in the streaming setting, the fact that we are computing it in the transitive closure requires very different ideas. In fact, a main contribution of our work is to connect sublinear time algorithms for estimating the maximum matching size to the streaming setting for the first time. While existing off-the-shelf sublinear time algorithms only result in an $n\sqrt{n}^{1+o(1)}$ pass algorithm in our setting, we show how to significantly improve upon them by allowing stronger queries (such as vertex and subset queries) that can be implemented just as efficiently as more standard adjacency matrix and list queries for our problem.
Amir Azarmehr, Soheil Behnezhad, Lily Chung et al.· 0 citations
Let $k_{1,\varepsilon}(n)$ be the smallest number of real linear measurements needed by a randomized oblivious sketch that estimates the nuclear norm of every fixed real $n\times n$ matrix within a factor $1\pm\varepsilon$, with probability at least $2/3$. For every fixed $0<\varepsilon<1$, we prove \[ \frac{n^2}{(\log n)^{A_\varepsilon}} \le k_{1,\varepsilon}(n) \le C_\varepsilon \frac{n^2\{\log\log(e^e n)\}^2}{\log(e n)}. \] Previously, the best unrestricted bounds for general linear sketches of the Schatten--1 norm were $\Omega(n)$ and the trivial $O(n^2)$ upper bound (Li, Nguyen, Woodruff'19), leaving a polynomial gap. Our bounds close that gap up to polylogarithmic factors and give a nontrivial logarithmic saving below the $n^2$-measurement storage bound. The result extends much further. Write $k_{p,\varepsilon}(n)$ for the analogous sketch dimension for the Schatten--$p$ norm. For every fixed finite $p>0$ that is not a positive even integer, there are positive constants $A_{p,\varepsilon},C_{p,\varepsilon},c_p$ such that \[ \frac{n^2}{(\log n)^{A_{p,\varepsilon}}} \le k_{p,\varepsilon}(n) \le C_{p,\varepsilon}\frac{n^2}{(\log n)^{c_p}}, \] so $k_{p,\varepsilon}(n)=n^{2-o(1)}$ throughout the non-even regime. Together with the known tight bounds $\Theta_{p,\varepsilon}(n^{2-4/p})$ for positive even $p$ and $\Theta_\varepsilon(n^2)$ for $p=\infty$ (Li, Woodruff'16), our results close the remaining polynomial gap across the Schatten family and complete, up to polylogarithmic factors, the polynomial-order classification of general linear sketches for all Schatten-$p$ norms.
We study the data structure version of the \emph{element distinctness problem}: preprocess an array of $n$ elements from an alphabet of size $\sigma$ to answer \textsc{All-Distinct} queries, asking whether a given range contains only distinct elements. We first focus on \emph{uniformly random arrays}: in the encoding model, where access to the input at query time is not allowed, we prove a lower bound on the expected space; for instance, the lower bound is $n$, $1.3627n$, $1.5153n$, $1.5824n$ bits for $\sigma = 2,3,4,5$, and approximately $n\sqrt{\pi/(2\sigma)}\,\log\sigma$ bits for $\sigma =\omega(1)$. We complement this by designing different average-case optimal encodings, supporting \textsc{All-Distinct} queries in worst-case time $O(1)$, $o(\log^{2}{\log{n}})$, or $O(\log\log{n})$ depending on $\sigma$, and $O(1)$ expected time for any $\sigma = \omega(1)$. We then switch to worst-case (non-random) arrays: in the indexing model, where access to the input is allowed, we prove a cell-probe space-time tradeoff lower bound showing that any index using $n/b$ bits must have $\Omega(b/\log{b})$ query time. We conclude by presenting a simple index almost matching this lower bound.
Philip Bille, J. Fischer, Inge Li Gørtz et al.· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
