Theory of Computing Report

Designing algorithms for space bounded models with restoration requirements on (most of) the space used by the algorithm is an important challenge posed about the catalytic computation model introduced by Buhrman et al (2014). Motivated by the scenarios where we do not need to restore unless $w$ is "useful", we relax the restoration requirement: only when the content of the catalytic tape is $w \in A \subseteq \Sigma^*$, the catalytic Turing machine needs to restore $w$ at the end of the computation. We define, $ACL(A)$ to be the class of languages that can be accepted by almost-catalytic Turing machines with respect to $A$ (which we call the catalytic set), that uses at most $c\log n$ work space and $n^c$ catalytic space. We prove the following for the almost-catalytic model. - We show that if there are almost-catalytic algorithms for a problem with catalytic set as $A \subseteq \Sigma^*$ and its complement respectively, then the problem can be solved by a zero-error randomized algorithm that runs in expected polynomial time. More formally, for any language $A \subseteq \Sigma^*$, $ACL(A) \cap ACL(\overline{A}) \subseteq ZPP$. In particular, when $A \in LOG$, $ACL(A) \cap ACL(\overline{A}) = CL$. This leads to newer algorithmic approaches for designing catalytic algorithms. - Using the above, we derive that to design catalytic algorithms for a language, it suffices to design almost-catalytic algorithms where the catalytic set is the set of strings of odd weight ($PARITY$). Towards this, we consider two complexity measures of the set $A$ which are maximized for $PARITY$. One is the random projection complexity (denoted by ${\cal R}(A)$) and the other is the subcube partition complexity (denoted by ${\cal P}(A)$). We show that, for all $k \ge 1$, there exists a language $A_k \subseteq \Sigma^* $ such that $DSPACE(n^k) \subseteq ACL(A_k)$ where for every $m \ge 1$, ${\cal R}(A_k \cap \{0,1\}^m) \ge \frac{m}{4}$ and ${\cal P}(A_k \cap \{0,1\}^m)=2^{m/4}$. This is in contrast to the catalytic machine model where it is unclear if it can accept all languages in $DSPACE(\log^{1+\epsilon} n)$ for any $\epsilon > 0$. - Improving the partition complexity of the restoration set $A$ further, we show that for all $k \ge 1$, there exists $A_k \subseteq \{0,1\}^*$ such that $DSPACE(\log^k n) \subseteq ACL(A_k)$ where for every $m \ge 1$, ${\cal R}(A_k \cap \{0,1\}^m) \ge \frac{m}{4}$ and ${\cal P}(A_k \cap \{0,1\}^m)=2^{m/4+\Omega(\log m)}$. Our main new technique for the last two items is the use of error correcting codes to design almost-catalytic algorithms. - We also show that, even when there are more than two alphabet symbols, if the catalytic set $A$ does not use one of the alphabet symbols, then efficient almost-catalytic algorithms with $A$ as the catalytic set can be designed for any language in $PSPACE$.

This paper revisits the study of two classical technical tools in theoretical computer science: Yao's transformation of distinguishers to next-bit predictors (FOCS 1982), and the ``reconstruction paradigm'' in pseudorandomness (e.g., as in Nisan and Wigderson, JCSS 1994). Recent works of Pyne, Raz, and Zhan (FOCS 2023) and Doron, Pyne, and Tell (STOC 2024) showed that both of these tools can be derandomized in the specific context of read-once branching programs (ROBPs), but left open the question of derandomizing them in more general settings. Our main contributions give appealing evidence that derandomization of the two tools is possible in general settings, show surprisingly strong consequences of such derandomization, and reveal several new settings where such derandomization is unconditionally possible for algorithms stronger than ROBPs (with useful consequences). Specifically: \begin{itemize} \item We show that derandomizing these tools is equivalent to general derandomization. Specifically, we show that derandomizing distinguish-to-predict transformations is equivalent to prBPP$=$prP, and that derandomized reconstruction procedures (in a more general sense that we introduce) is equivalent to prBPP$=$prZPP. These statements hold even when scaled down to weak circuit classes and to algorithms that run in super-polynomial time. \item Our main technical contributions are unconditional constructions of derandomized versions of Yao's transformation (or reductions of this task to other problems) for classes and for algorithms beyond ROBPs. Consequently, we deduce new results: A significant relaxation of the hypotheses required to derandomize the isolation lemma for logspace algorithms and deduce that NL$=$UL; and proofs that derandomization necessitates targeted PRGs in catalytic logspace (unconditionally) and in logspace (conditionally). \end{itemize} In addition, we introduce a natural subclass of prZPP that has been implicitly studied in recent works (Korten FOCS 2021, CCC 2022): The class of problems reducible to a problem called ``Lossy Code''. We provide a structural characterization for this class in terms of derandomized reconstruction procedures, and show that this characterization is robust to several natural variations. Lastly, we present alternative proofs for classical results in the theory of pseudorandomness (such as two-sided derandomization reducing to one-sided), relying on the notion of deterministically transforming distinguishers to predictors as the main technical tool.

If there's a position where I differ from most other complexity theorists it's that I don't believe that natural proofs present a significant barrier to proving circuit results. I wrote about this before but I buried the lead and nobody noticed.

Let's review natural proofs. I'll give a very high-level description. Li-Yang Tan gives a good technical description or you could read the original Razborov-Rudich paper. A natural proof to prove lower bounds against a circuit class \(\cal C\) consists of a collection \(C_n\) of Boolean functions on \(n\) inputs such that

1. No polynomial-size circuit family from \(\cal C\) can compute an element of \(C_n\) for large enough \(n\). 
2. \(C_n\) is a large fraction of all the function on \(n\) inputs.
3. A subset of \(C_n\) is constructive--given the truth-table of a function, you can determine whether it sits in the subset in time polynomial in the length of the truth-table. Note: This is a different than the usual notion of "constructive proof". 

By Lance Fortnow

Authors: Tal Herman, Guy Rothblum

Authors: Florin Manea, Giovanni Pighizzini

Authors: Jakub Jagiełła, Joachim Jelisiejew

Authors: Sándor P. Fekete, Ramin Kosfeld, Peter Kramer, Jonas Neutzner, Christian Rieck, Christian Scheffer

Authors: Farhan Rasheed, Abrar Naseer, Emma Nilsson, Talha Bin Masood, Ingrid Hotz

Authors: Salman Parsa, Bei Wang

Authors: Allison Bishop, Hayder Tirmazi

Authors: Milind Prabhu, David Woodruff

Authors: Ryoga Mahara, Ryuhei Mizutani, Taihei Oki, Tomohiko Yokoyama

Authors: Matthew Andres Moreno, Luis Zaman, Emily Dolson

Authors: Daniel Carter

Authors: Jonas Costa, Lucas Castro, Rosiane de Freitas

Authors: Martin Frohn, Niels Holtgrefe, Leo van Iersel, Mark Jones, Steven Kelk

Authors: Trung Dang, Zhiyi Huang

Authors: Jinyuan Chen

A catalytic machine is a model of computation where a traditional space-bounded machine is augmented with an additional, significantly larger, "catalytic" tape, which, while being available as a work tape, has the caveat of being initialized with an arbitrary string, which must be preserved at the end of the computation. Despite this restriction, catalytic machines have been shown to have surprising additional power; a logspace machine with a polynomial length catalytic tape, known as catalytic logspace ($CL$), can compute problems which are believed to be impossible for $L$. A fundamental question of the model is whether the catalytic condition, of leaving the catalytic tape in its exact original configuration, is robust to minor deviations. This study was initialized by Gupta et al. (2024), who defined lossy catalytic logspace ($LCL[e]$) as a variant of $CL$ where we allow up to $e$ errors when resetting the catalytic tape. They showed that $LCL[e] = CL$ for any $e = O(1)$, which remains the frontier of our understanding. In this work we completely characterize lossy catalytic space ($LCSPACE[s,c,e]$) in terms of ordinary catalytic space ($CSPACE[s,c]$). We show that $$LCSPACE[s,c,e] = CSPACE[\Theta(s + e \log c), \Theta(c)]$$ In other words, allowing $e$ errors on a catalytic tape of length $c$ is equivalent, up to a constant stretch, to an equivalent errorless catalytic machine with an additional $e \log c$ bits of ordinary working memory. As a consequence, we show that for any $e$, $LCL[e] = CL$ implies $SPACE[e \log n] \subseteq ZPP$, thus giving a barrier to any improvement beyond $LCL[O(1)] = CL$. We also show equivalent results for non-deterministic and randomized catalytic space.

The University of California San Diego Computer Science and Engineering Department seeks applications for an Assistant Teaching Professor. Must have a Ph.D. in computer science and/or electrical or computer engineering and/or computing education and/or mathematics and/or bioinformatics or computational biology and/or computational social science.

Website: https://apol-recruit.ucsd.edu/JPF04041
Email: nherrera@ucsd.edu

By shacharlovett

Update: I’d been wavering—should I vote for the terrifying lunatic, ranting about trans criminal illegal aliens cooking cat meat, or for the nice woman constantly making faces as though the lunatic was completely cracking her up? But when the woman explicitly came out in favor of AI and quantum computing research … that really sealed the deal for me.

Between roughly 2001 and 2018, I’ve happy to have done some nice things in quantum computing theory, from the quantum lower bound for the collision problem to the invention of shadow tomography.  I hope that’s not the end of it.  QC research brought me about as much pleasure as anything in life did.  So I hope my tired brain can be revved up a few more times, between now and whenever advances in AI or my failing health or the collapse of civilization makes the issue moot. If not, though, there are still many other quantum activities to fill my days: teaching (to which I’ve returned after two years), advising my students and postdocs, popular writing and podcasts and consulting, and of course, learning about the latest advances in quantum computing so I can share them with you, my loyal readers.

On that note, what a time it is in QC!  Basically, one experimental milestone after another that people talked about since the 90s is finally being achieved, to the point where it’s become hard to keep up with it all. Briefly though:

A couple weeks ago, the Google group announced an experiment that achieved net gain from the use of Kitaev’s surface code, using 101 physical qubits to encode 1 logical qubit. The headline result here is that, in line with theory, they see the performance improve as they pass to larger codes with more physical qubits and higher distance. Their best demonstrated code has a distance of 7, which is enough to get “beyond break-even” (their logical qubit lasts more than twice as long as the underlying physical qubits), and is also enough that any future improvements to the hardware will get amplified a lot. With superconducting qubits, one is (alas) still limited by how many one can cram onto a single chip. On paper, though, they say that scaling the same setup to a distance-27 code with ~1500 physical qubits would get them down to an error rate of 10^-6, good enough to be a building block in a future fault-tolerant QC. They also report correlated bursts of errors that come about once per hour, from a still-unknown source that appears not to be cosmic rays. I hope it’s not Gil Kalai in the next room.

Separately, just this morning, Microsoft and Quantinuum announced that they entangled 12 logical qubits on a 56-physical-qubit trapped-ion processor, building on earlier work that I blogged about in April. They did this by applying a depth-3 logical circuit with 12 logical CNOT gates, to prepare a cat state. They report an 0.2% error rate when they do this, which is 11x better than they would’ve gotten without using error-correction. (Craig Gidney, in the comments, says that these results still involve postselection.)

The Microsoft/Quantinuum group also did what they called a “chemistry simulation” involving 13 physical qubits. The latter involved “only” 2 logical qubits and 4 logical gates, but 3 of those gates were non-Clifford, which are the hard kind when one is doing error-correction using a transversal code. (CNOT, by contrast, is a Clifford gate.)

Apart from the fact that Google is using superconducting qubits while Microsoft/Quantinuum are using trapped ions, the two results are incomparable in terms of what they demonstrate. Google is just scaling up a single logical qubit, but showing (crucially) that their error rate decreases with increasing size and distance. Microsoft and Quantinuum are sticking with “small” logical qubits with insufficient distance, but they’re showing that they can apply logical circuits that entangle up to 12 of these qubits.

Microsoft also announced today a new collaboration with the startup company Atom Computing, headquartered near Quantinuum in Colorado, which is trying to build neutral-atom QCs (like QuEra in Boston). Over the past few years, Microsoft’s quantum group has decisively switched from a strategy of “topological qubits or bust” to a strategy of “anything that works,” although they assure me that they also remain committed to the topological approach.

Anyway, happy to hear in the comments from anyone who knows more details, or wants to correct me on any particular, or has questions which I or others can try our best to answer.

Let me end by sticking my neck out. If hardware progress continues at the rate we’ve seen for the past year or two, then I find it hard to understand why we won’t have useful fault-tolerant QCs within the next decade. (And now to retreat my neck a bit: the “if” clause in that sentence is important and non-removable!)

By Scott

This is the live blog of Lecture 4 of my graduate class “Convex Optimization.” A Table of Contents is here.

Though I made a big deal last week about how we could reduce all optimization problems to minimizing a linear cost subject to constraints, most people think of cost functions as the central part of optimization. Even though it’s easier to build models by specifying constraints, the act of optimization is easier to conceptualize using functions. Optimization implies a notion of pricing and the existence of a solution of minimal price. Moreover, if I can formulate an optimization problem as finding some point that achieves minimum cost, I can search for such a problem by finding clever ways to reduce the cost at each step.

Since Newton, mathematicians have realized that dynamic search methods can find solutions of minimum value. The most popular search method, usually attributed to Cauchy, is the method of steepest descent. This very greedy method tells you to find the direction that maximally decreases your cost and follow that direction.

Steepest descent is something you learn in calculus. The steepest descent direction at any point is in the direction of the negative gradient. If the gradient is zero, there is no local information about how to make improvements. However, there are weird functions even in 1D, like x³, where the gradient equals zero at the point x=0, but any finite step in the negative direction reduces the cost. Convex functions are the ones for which Cauchy’s method always finds the minimum cost solution. And the proof almost follows from the definition.

A function is convex if and only if the plane tangent to the graph of the function lies below the function at every point:

.

Writing this in math says that for all x and all v

So if the gradient is equal to zero at x0, that means f(x)>= f(x0) for all x. If you get your definitions right, all theorems are trivial. 

Last week, we needed to talk about feasible cones and separating hyperplanes to test optimality. But the condition here for convex functions is so much simpler. A point is a global minimizer of a cost function if the gradient of the function at that point is equal to zero. 

If you can model your cost with convex functions, a simple algorithm always finds the optimal solution. The only question that remains is whether you can model your problem with convex costs. Just like last week, the answer will be to have a brute force definition that is sometimes easy to check and a bunch of rules for building complex convex functions from simple ones.

For this modeling program, we should start with the more common definition of convex functions: a function is convex if, for any two points, the line segment connecting their function values lies above the graph of the function. That is, a convex function is one where the area above the graph is a convex set. Here’s the simplest picture.

Convex functions are all boring like this. Their boringness is their appeal.

Even in high dimensions, convex functions are roughly valley-shaped, perhaps with some sharper edges. But the functions you can prove convex are wild. Feel free to skim these examples, but here are some of the more exotic ones I’ve seen (oddly, all of them introduced to me by Joel Tropp).

• If H hermitian, X positive definite, f(X) = -trace(exp(H + log(X)) is convex. Here exp and log are the matrix exponential and logarithm.

• If X and Z are positive definite, f(X,Z) = trace( X (log X - log Z) - (X - Z)) is convex.

• If f is any complex differentiable function on the subset of complex numbers with real parts between a and b, f(x) = sup_y | f(x+iy) | is convex on the set [a,b].

Wut. Verifying the convexity of these particular examples is a real pain. The first one even has a name associated with it (Lieb’s Theorem). But for those of us who just want to model, it’s better to take the building block approach, again looking at operations that preserve convexity and using these to build up examples. 

Nonnegative Combinations. Any linear combination of convex functions with nonnegative coefficients is convex. You can prove this using the fact that inequalities are preserved under nonnegative combinations. This means that integrals of convex functions are convex, as are expected values.

Composition with Affine Functions. If f(x) is convex, A is a matrix, and b is a vector, then g(x) = f(Ax+b) is convex.

Maximization. The pointwise maximum of several convex functions is itself a convex function. In mathematics: f1, f2, …, fk are convex, then g(x) = max_i f_i(x) is convex. 

Partial minimization. If f(x,z) is convex, then inf_z f(x,z) is convex. 

Composition with scalar functions. If f is convex, and g is convex and nondecreasing, then h(x) = g(f(x)) is convex.

With these simple rules, you can build up a giant library of convex functions. You could argue the only ones you really need are affine functions a^T x + b.  If you just think about this geometrically, a convex function is equal to the pointwise maximum of all of the affine functions that lie below its graph. This is the same as saying that a convex set is the intersection of all halfspaces that contain it.

But such sophisticated mathematical abstractions aren’t necessary for modeling. Instead, we just need to composition rules. We can get some outlandish functions with the building blocks alone:

• The sum of the squared residual errors in a linear model

• The sum of the k largest components of a vector

• The negative geometric mean of a bunch of concave functions

• The Kullback Liebler divergence between two probability distributions

• The maximum eigenvalue of a positive semidefinite matrix

All of these functions are convex and can be proven so using the simple composition rules. And that means that they can be minimized by local search. Disciplined modeling guarantees efficient ways to find global minimizers. The only question (and it’s a hard one) is whether you can find a good model for your problem only using these rules.

Subscribe now

By Ben Recht

Authors: Marten Folkertsma, Ian Mertz, Florian Speelman, Quinten Tupker

Authors: Sarwan Ali, Prakash Chourasia, Bipin Koirala, Murray Patterson

Authors: Pavel Dvořák, Bruno Loff, Suhail Sherif

Authors: Eshan Chattopadhyay, Mohit Gurumukhani, Noam Ringach, Yunya Zhao

Authors: Alejandro García-Castellanos, Aniss Aiman Medbouhi, Giovanni Luca Marchetti, Erik J. Bekkers, Danica Kragic

Authors: Son Le Thanh, Michael Ankele, Tino Weinkauf

Authors: Raunak Sarbajna, Karima Elgarroussi, Hoang D Vo, Jianyuan Ni, Christoph F. Eick

Authors: Jason Gaitonde, Ankur Moitra, Elchanan Mossel

Authors: Brandon Van Over, Bowen Li, Edwin K. P. Chong, Ali Pezeshki

Authors: Arnold Filtser, Ameet Gadekar

Authors: L. Elisa Celis, Amit Kumar, Nisheeth K. Vishnoi, Andrew Xu

Authors: Tamás Fleiner, András Frank, Tamás Király

Authors: Édouard Bonnet, Julien Duron, John Sylvester, Viktor Zamaraev

Authors: Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, Jie Xue, Meirav Zehavi

We study the challenge of derandomizing constant-width standard-order read-once branching programs (ROBPs). Let $c \in [1, 2)$ be any constant. We prove that if there are explicit pseudorandom generators (PRGs) for width-$6$ length-$n$ permutation ROBPs with error $1/n$ and seed length $\widetilde{O}(\log^c n)$, then there are explicit hitting set generators (HSGs) for width-$4$ length-$n$ ROBPs with threshold $1/\mathrm{polylog}(n)$ and seed length $\widetilde{O}(\log^c n)$. For context, there are known explicit PRGs that fool constant-width permutation ROBPs with error $\varepsilon$ and seed length $O(\log n \cdot \log(1/\varepsilon))$ (Koucký, Nimbhorkar, and Pudlák STOC 2011; De CCC 2011; Steinke ECCC 2012). When $\varepsilon = 1/n$, there are known constructions of *weighted* pseudorandom generators (WPRGs) that fool polynomial-width permutation ROBPs with seed length $\widetilde{O}(\log^{3/2} n)$ (Pyne and Vadhan CCC 2021; Chen, Hoza, Lyu, Tal, and Wu FOCS 2023; Chattopadhyay and Liao ITCS 2024), but *unweighted* PRGs with seed length $o(\log^2 n)$ remain elusive. Meanwhile, for width-$4$ ROBPs, there are no known explicit PRGs, WPRGs, or HSGs with seed length $o(\log^2 n)$. Our reduction can be divided into two parts. First, we show that explicit low-error PRGs for width-$6$ permutation ROBPs with seed length $\widetilde{O}(\log^c n)$ would imply explicit low-error PRGs for width-$3$ ROBPs with seed length $\widetilde{O}(\log^c n)$. This would improve Meka, Reingold, and Tal's PRG (STOC 2019), which has seed length $o(\log^2 n)$ only when the error parameter is relatively large. Second, we show that for any $w$, $n$, $s$, and $\varepsilon$, an explicit PRG for width-$w$ ROBPs with error $0.01/n$ and seed length $s$ would imply an explicit $\varepsilon$-HSG for width-$(w + 1)$ ROBPs with seed length $O(s + \log n \cdot \log(1/\varepsilon))$.

Apologies for the late post! After the relative silence of last month, we’re getting back to a moderate cadence of papers. Some distribution testing, quantum testing, learning and testing. We’ve also added a non-sublinear paper on distributions that should be of interest. And here’s the roundup.

Efficient Testable Learning of General Halfspaces with Adversarial Label Noise by Ilias Diakonikolas, Daniel M. Kane, Sihan Liu, and Nikos Zarifis (arXiv). This paper is on the recent model of testable learning introduced by Rubinfeld-Vasiliyan. Consider learning halfspaces over the Gaussian distribution. We have sample access to an input function \(f:\mathbf{R}^d \to \{0,1\}\), where our aim is learn the closest halfspace to \(f\). The samples comes from some fixed, underlying distribution \(\mathcal{D}\). But it is often infeasible to validate this distributional assumption, even in the property testing framework. A tester-learner pair will try to test this assumption, and if it accepts, apply the learning algorithm. The guarantee is: if \(\mathcal{D}\) is indeed (say) Gaussian, then the learning algorithms works as desired. If the tester accepts and the learner outputs a hypothesis (say, halfspace) \(h\), then it is guaranteed that \(h\) is close to \(f\) according to \(\mathcal{D}\), even if \(\mathcal{D}\) is far from Gaussian. This last part makes the whole setup interesting; the distribution tester might fail to reject the distribution, but we can trust the output hypothesis! There have been many results on learning homogenous halfspaces under the Gaussian distribution. So the hypothesis class consists of halfspaces going through the origin. This paper is about general (inhomogenous) halfspaces. At first blush, this might seem like a simple issue; we’re just adding a constant term to the halfspace. But existing techniques break down, often because they’re solving an optimization problem of minimizing error around a band close the origin. This paper gives a careful reduction to the “nearly” homogeneous case, and gives the first polynomial sample tester-learner pair for this problem.

Tolerant testing stabilizer states by Srinivasan Arunachalam and Arkopal Dutt (arXiv). Let us start with a familiar classical problem, low degree testing. Given access to a function \(f:\{0,1\}^n \to \{0,1\}\), we wish to test if \(f\) is a quadratic polynomial (over \(\mathbb{F}_2\)). There exist testers based on the Gowers-norm: basically, compute various (constant dimensional) discrete derivatives and check they are consistent with a quadratic function. These discrete derivatives can be analyzed using Fourier analysis, and the main aim is show that a function that “locally” (in terms of derivatives) behaves like a quadratic is indeed globally close to being one. This method can be used to get tolerant testers for quadratic polynomials. This paper is on a quantum generalization of this testing result. The input is a qubit \(|\psi_f\rangle\), promised to be a “phase state”. A phase state has a Boolean function \(f\) embedded in it, because one can write a phase state as a linear combination of \(2^n\) “base” states, with the coefficients being Boolean. A “stabilizer state” is one where the function \(f\) is a quadratic (or so I believe, I’m probably exposing my ignorance of quantum mechanics). This paper uses the Gowers norm techniques to give the first quantum tolerant tester for stabilizer states.

Improved Bounds for High-Dimensional Equivalence and Product Testing using Subcube Queries by Tomer Adar, Eldar Fischer, and Amit Levi (arXiv). Consider distribution testing on high-dimensional data, so the domain is \(\{0,1\}^n\). A nice model for distribution tester is the subcube conditioning model of Bhattacharyya and Chakraborty. Suppose we fix any subset \(S \subseteq [n]\) coordinates with \(x_S\). We can generate a sample \(y\) from the distribution, conditioned on \(y_S = x_S\) (meaning, \(y\) agrees with \(x\) on \(S\)). The problem is to perform equivalence testing of distributions on this model. Previous results got \(O(n^2/\varepsilon^2)\) query algorithms, and this paper give a significantly improved algorithm making \(O(n/\varepsilon^2)\) queries. Interestingly, the algorithm only makes weaker queries. One distribution is only accessed by “marginal queries”. So, given \(x_S\) as before, but we only sample the marginal distribution over coordinate \(i\), conditioned on \(S\) being fixed as \(x_S\). (Hence, the output is a single bit. Also, we note that the other distribution is accessed by prefix queries, a weaker version of subcube queries.) These generalizations lead to more results, on testing equivalence in the interval query model, and for testing the property of product distributions. This paper also proves a \(\Omega(\sqrt{n}/\varepsilon^2)\) lower bound for testing product distributions.

Parallel Sampling via Counting by Nima Anari, Ruiquan Gao, and Aviad Rubinstein (arXiv). This isn’t a “typical sublinear algorithm” per se, but I think it is quite interesting to those of us who think about sublinearity, adaptivity, and distributions. This result has connections to the previous paper. Our aim is to sample from an unknown distribution \(\mu\) over \([q]^n\). We have access to “marginal queries” as described above. This problem appears in large language models, wherein neural nets are trained on various marginals (next word), but the output is a sentence (list of words). Observe there is a simple “\(O(n)\) round” algorithm. Without any fixing, query the marginal of the first coordinate. Fix the first coordinate, query the marginal of the second coordinate. Fix the first two coordinates, rinse and repeat. This requires \(n\) rounds with the marginal query. In this model, polynomially many marginal queries can be made in a single round, and the aim is to minimize the number of rounds (basically, bounding the adaptivity). This paper gives a \(\widetilde{O}(n^{2/3})\) round procedure for sampling, and shows an \(\Omega(n^{1/3})\) lower bound.

By Seshadhri

Authors: Jean-François Culus, Sophie Toulouse

Authors: Toni Böhnlein, Pál András Papp, A. N. Yzelman

Authors: Therese Biedl, Anna Lubiw, Jack Spalding-Jamieson

Authors: Nicola Amico, Achille Felicetti

Authors: Neng Huang, Will Perkins, Aaron Potechin

Authors: Raul Lopes, Ignasi Sau

Authors: Frederik Glitzner, David Manlove

Authors: Oren Mangoubi, Nisheeth K. Vishnoi

Authors: Klaus Jansen, Alexandra Lassota, Malte Tutas, Adrian Vetta

Authors: Klaus Jansen, Kai Kahler, Lis Pirotton, Malte Tutas

Authors: JiaJun Hou, HongJie Liu, ShengXin Zhu

Authors: Jincheng Zhou, Jin Zhang, Xiang Zhang, Tiaojie Xiao, Di Ma, Chunye Gong