A recent work of Schmidhuber et al. (QIP, SODA, & Phys. Rev. X 2025) exhibited a quantum algorithm for the noisy planted \(k\)xor problem running quartically faster than all known classical algorithms. In this work, we design a new classical algorithm that is quadratically faster than the best previous one, in the case of large constant \(k\). Thus for such \(k\), the quantum speedup of Schmidhuber et al. becomes only quadratic (though it retains a space advantage). Our algorithm, which also works in the semirandom case, combines tools from sublinear-time algorithms (essentially, the birthday paradox) and polynomial anticoncentration.

A fundamental task in quantum information science is state certification: testing whether a lab-prepared n-qubit state is close to a given hypothesis state. In this work, we show that every pure hypothesis state can be certified using only O(n^2) single-qubit measurements applied to O(n) copies of the lab state. Prior to our work, it was not known whether even subexponentially many single-qubit measurements could suffice to certify arbitrary states. This resolves the main open question of Huang, Preskill, and Soleimanifar (FOCS 2024, QIP 2024).

In order to communicate a message over a noisy channel, a sender (Alice) uses an error-correcting code to encode her message, a bitstring x, into a codeword. The receiver (Bob) decodes x correctly whenever there is at most a small constant fraction of adversarial errors in the transmitted codeword. We investigate the setting where Bob is restricted to be a low-space streaming algorithm. Specifically, Bob receives the message as a stream and must process it and write x in order to a write-only tape while using low (say polylogarithmic) space. Note that such a primitive then allows the execution of any downstream streaming computation on x. We show three basic results about this setting, which are informally as follows: [(i)] 1) There is a stream decodable code of near-quadratic length, resilient to error-fractions approaching the optimal bound of 1/4. 2) There is no stream decodable code of sub-quadratic length, even to correct any small constant fraction of errors. 3) If Bob need only compute a private linear function of the bits of x, instead of writing them all to the output tape, there is a stream decodable code of near-linear length. Our constructions use locally decodable codes with additional functionality in the decoding, and (for the result on linear functions) repeated tensoring. Our lower bound, which rather surprisingly demonstrates a strong information-theoretic limitation originating from a computational restriction, proceeds via careful control of the message indices that may be output during successive blocks of the stream, a task complicated by the arbitrary state of the decoder during the algorithm.

In the setting of error correcting codes, Alice wants to send a message x ∈ {0,1}ⁿ to Bob via an encoding enc(x) that is resilient to error. In this work, we investigate the scenario where Bob is a low space decoder. More precisely, he receives Alice’s encoding enc(x) bit-by-bit and desires to compute some function f(x) in low space. A generic error-correcting code does not accomplish this because decoding is a very global process and requires at least linear space. Locally decodable codes partially solve this problem as they allow Bob to learn a given bit of x in low space, but not compute a generic function f. Our main result is an encoding and decoding procedure where Bob is still able to compute any such function f in low space when a constant fraction of the stream is corrupted. More precisely, we describe an encoding function enc(x) of length poly(n) so that for any decoder (streaming algorithm) A that on input x computes f(x) in space s, there is an explicit decoder B that computes f(x) in space s ⋅ polylog(n) as long as there were not more than 1/4 - ε fraction of (adversarial) errors in the input stream enc(x).

In an error-correcting code, a sender encodes a message x ∈ {0, 1}^k such that it is still decodable by a receiver on the other end of a noisy channel. In the setting of error-correcting codes with feedback, after sending each bit, the sender learns what was received at the other end and can tailor future messages accordingly. While the unique decoding radius of feedback codes has long been known to be 1/3, the list decoding capabilities of feedback codes is not well understood. In this paper, we provide the first nontrivial bounds on the list decoding radius of feedback codes for lists of size 𝓁. For 𝓁 = 2, we fully determine the 2-list decoding radius to be 3/7. For larger values of 𝓁, we show an upper bound of 1/2 - 1/{2^(𝓁+2) - 2}, and show that the same techniques for the 𝓁 = 2 case cannot match this upper bound in general.

In the setting of error-correcting codes with feedback, Alice wishes to communicate a k-bit message x to Bob by sending a sequence of bits over a channel while noiselessly receiving feedback from Bob. It has been long known (Berlekamp, 1964) that in this model, Bob can still correctly determine x even if$\approx \frac {1}{3}$of Alice’s bits are flipped adversarially. This improves upon the classical setting without feedback, where recovery is not possible for error fractions exceeding$\frac {1}{4}$. In the corresponding setting of erasures rather than bit flips, feedback improves the error resilience from$\frac {1}{2}-\epsilon $to$1-\epsilon $for any$\epsilon \gt 0$. The original feedback setting assumes that after transmitting each bit, Alice knows (via feedback) what bit Bob received. In this work, our focus in on the limited feedback model, where Bob is only allowed to send a few bits at a small number of pre-designated points in the protocol. For any desired$\epsilon \gt 0$, we construct a coding scheme that tolerates a$ 1/3-\epsilon $fraction of bit flips (respectively a$1-\epsilon $fraction of erasures) relying only on$O_{\epsilon } (\log k)$bits of feedback from Bob sent in a fixed$O_{\epsilon } (1)$number of rounds. We complement this with a matching lower bound showing that$\Omega (\log k)$bits of feedback are necessary to recover from an error fraction exceeding$1/4$(respectively$1/2$for erasures), and for schemes resilient to a$1/3-\epsilon $fraction of bit flips (respectively a$1-\epsilon $fraction of erasures), the number of rounds must grow as$\epsilon \to 0$.

We introduce and study the problem of \textit{dueling optimization with a monotone adversary}, which is a generalization of (noiseless) dueling convex optimization. The goal is to design an online algorithm to find a minimizer $\bm{x}^{\star}$ for a function $f\colon \mathcal{X} \to \mathbb{R}$, where $\mathcal{X} \subseteq \mathbb{R}^d$. In each round, the algorithm submits a pair of guesses, i.e., $\bm{x}^{(1)}$ and $\bm{x}^{(2)}$, and the adversary responds with \textit{any} point in the space that is at least as good as both guesses. The cost of each query is the suboptimality of the worse of the two guesses; i.e., ${\max} \left( f(\bm{x}^{(1)}), f(\bm{x}^{(2)}) \right) - f(\bm{x}^{\star})$. The goal is to minimize the number of iterations required to find an $\eps$-optimal point and to minimize the total cost (regret) of the guesses over many rounds. Our main result is an efficient randomized algorithm for several natural choices of the function $f$ and set $\mathcal{X}$ that incurs cost $O(d)$ and iteration complexity $O(d\log(1/\varepsilon)^2)$. Moreover, our dependence on $d$ is asymptotically optimal, as we show examples in which any randomized algorithm for this problem must incur $\Omega(d)$ cost and iteration complexity.

Interactive coding allows two parties to conduct a distributed computation despite noise corrupting a certain fraction of their communication. Dani et al. (Inf. and Comp., 2018) suggested a novel setting in which the amount of noise is unbounded and can significantly exceed the length of the (noise-free) computation. While no solution is possible in the worst case, under the restriction of oblivious noise, Dani et al. designed a coding scheme that succeeds with a polynomially small failure probability. We revisit the question of conducting computations under this harsh type of noise and devise a computationally-efficient coding scheme that guarantees the success of the computation, except with an exponentially small probability. This higher degree of correctness matches the case of coding schemes with a bounded fraction of noise. Our simulation of an N-bit noise-free computation in the presence of T corruptions, communicates an optimal number of O(N+T) bits and succeeds with probability 1-2^(-Ω(N)). We design this coding scheme by introducing an intermediary noise model, where an oblivious adversary can choose the locations of corruptions in a worst-case manner, but the effect of each corruption is random: the noise either flips the transmission with some probability or otherwise erases it. This randomized abstraction turns out to be instrumental in achieving an optimal coding scheme.

Estimating quantiles is one of the foundational problems of data sketching. Given$n$elements$x_{1},x_{2}, \ldots, x_{n}$from some universe of size$U$arriving in a data stream, a quantile sketch estimates the rank of any element with additive error at most$\varepsilon n$. A low-space algorithm solving this task has applications in database systems, network measurement, load balancing, and many other practical scenarios. Current quantile estimation algorithms described as optimal include the GK sketch (Greenwald and Khanna 2001) using$O(\varepsilon^{-1}\log n)$words (deterministic) and the KLL sketch (Karnin, Lang, and Liberty 2016) using$O (>\varepsilon$log log$(1/\delta)$) words (ran-domized, with failure probability$\delta$). However, both algorithms are only optimal in the comparison-based model, whereas many typical applications involve streams of integers that the sketch can use aside from making comparisons. If we go beyond the comparison-based model, the deterministic q-digest sketch (Shrivastava, Buragohain, Agrawal, and Suri 2004) achieves a space complexity of$O(\varepsilon^{-1}\log U)$words, which is incomparable to the previously-mentioned sketches. It has long been asked whether there is a quantile sketch using$O(\epsilon^{-1})$words of space (which is optimal as long as$n\leq$poly$(U)$). In this work, we present a deterministic algorithm using$O(\varepsilon^{-1})$words, resolving this line of work.

Locally decodable codes (LDC’s) are error-correcting codes that allow recovery of individual message indices by accessing only a constant number of codeword indices. For substitution errors, it is evident that LDC’s exist – Hadamard codes are examples of 2-query LDC’s. Research on this front has focused on finding the optimal encoding length for LDC’s, for which there is a nearly exponential gap between the best lower bounds and constructions. Ostrovsky and Paskin-Cherniavsky (ICITS 2015) introduced the notion of local decoding to the insertion and deletion setting. In this context, it is not clear whether constant query LDC’s exist at all. Indeed, in contrast to the classical setting, Block et al. conjecture that they do not exist. Blocki et al. (FOCS 2021) make progress towards this conjecture, proving that any potential code must have at least exponential encoding length. Our work definitively resolves the conjecture and shows that constant query LDC’s do not exist in the insertion/deletion (or even deletion-only) setting. Using a reduction shown by Blocki et al., this also implies that constant query locally correctable codes do not exist in this setting.

An interactive error correcting code (iECC) is an interactive protocol with the guarantee that the receiver can correctly determine the sender’s message, even in the presence of noise. It was shown in works by Gupta, Kalai, and Zhang (STOC 2022) and by Efremenko, Kol, Saxena, and Zhang (FOCS 2022) that there exist iECC’s that are resilient to a larger fraction of errors than is possible in standard error-correcting codes without interaction. In this work, we improve upon these existing works in two ways: - First, we improve upon the erasure iECC of Kalai, Gupta, and Zhang, which has communication complexity quadratic in the message size. In our work, we construct the first iECC resilient to > 1/2 adversarial erasures that is also positive rate. For any ε > 0, our iECC is resilient to 6/11 - ε adversarial erasures and has size O_ε(k). - Second, we prove a better upper bound on the maximal possible error resilience of any iECC in the case of bit flip errors. It is known that an iECC can achieve 1/4 + 10^{-5} error resilience (Efremenko, Kol, Saxena, and Zhang), while the best known upper bound was 2/7 ≈ 0.2857 (Gupta, Kalai, and Zhang). We improve upon the upper bound, showing that no iECC can be resilient to more than 13/47 ≈ 0.2766 fraction of errors.

We investigate one of the most basic problems in streaming algorithms: approximating the number of elements in the stream. Famously, [Mor78] gave a randomized algorithm achieving a constant-factor approximation error for streams of length at most N in space $O(\log\log N)$. We investigate the pseudo-deterministic complexity of the problem and prove a tight $\Omega(\log N)$ lower bound, thus resolving a problem of [GGMW20].

In the setting of error-correcting codes with feedback, Alice wishes to communicate a k-bit message x to Bob by sending a sequence of bits over a channel while noiselessly receiving feedback from Bob. It has been long known (Berlekamp, 1964) that in this model, Bob can still correctly determine x even if ≈ 1/3 of Alice’s bits are flipped adversarially. This improves upon the classical setting without feedback, where recovery is not possible for error fractions exceeding 1/4.

Given a noiseless protocol π0 computing a function f(x, y) of Alice and Bob’s private inputs x, y, the goal of interactive coding is to construct an error-resilient protocol π computing f such that even if some fraction of the communication is adversarially corrupted, both parties still learn f(x, y). Ideally, the resulting scheme π should be positive rate, computationally efficient, and achieve optimal error resilience.

An error correcting code (ECC) allows a sender to send a message to a receiver such that even if a constant fraction of the communicated bits are corrupted, the receiver can still learn the message correctly. Due to their importance and fundamental nature, ECC’s have been extensively studied, one of the main goals being to maximize the fraction of errors that the ECC is resilient to.

In interactive coding, Alice and Bob wish to compute some function f of their individual private inputs x and y. They do this by engaging in a non-adaptive (fixed order, fixed length) interactive protocol to jointly compute f(x,y). The goal is to do this in an error-resilient way, such that even given some fraction of adversarial corruptions to the protocol, both parties still learn f(x,y).