Research Papers

Quantum computational pseudorandomness has emerged as a fundamental notion that spans connections to complexity theory, cryptography and fundamental physics. However, all known constructions of efficient quantum-secure pseudorandom objects rely on complexity theoretic assumptions.

In this work, we establish the first unconditionally secure efficient pseudorandom constructions against shallow-depth quantum circuit classes. We prove that:

• Any quantum state 2-design yields unconditional pseudorandomness against both $\mathsf{QNC}_0$ circuits with arbitrarily many ancillae and $\mathsf{AC}_0\circ\mathsf{QNC}_0$ circuits with nearly linear ancillae.
• Random phased subspace states, where the phases are picked using a 4-wise independent function, are unconditionally pseudoentangled against the above circuit classes.
• Any unitary 2-design yields unconditionally secure parallel-query pseudorandom unitaries against geometrically local $\mathsf{QNC}_0$ adversaries, even with limited $\mathsf{AC}_0$ postprocessing.

Our indistinguishability results for 2-designs stand in stark contrast to the standard setting of quantum pseudorandomness against $\mathsf{BQP}$ circuits, wherein they can be distinguishable from Haar random ensembles using more than two copies or queries. Our work demonstrates that quantum computational pseudorandomness can be achieved unconditionally for natural classes of restricted adversaries, opening new directions in quantum complexity theory.

@misc{GSZ25,
	title = {Unconditional Pseudorandomness against Shallow Quantum Circuits}, 
	author = {Soumik Ghosh and Sathyawageeswar Subramanian and Wei Zhan},
	year = {2025},
	eprint = {2507.18796},
	archivePrefix = {arXiv},
	primaryClass = {quant-ph}
}

We prove a Carbery-Wright style anti-concentration inequality for the unitary Haar measure, by showing that the probability of a polynomial in the entries of a random unitary falling into an $\varepsilon$ range is at most a polynomial in $\varepsilon$. Using it, we show that the scrambling speed of a random quantum circuit is lower bounded: Namely, every input qubit has an influence that is at least inverse exponential in depth, on any output qubit touched by its lightcone. Our result on scrambling speed works with high probability over the choice of a circuit from an ensemble, as opposed to just working in expectation.

As an application, we give the first polynomial-time algorithm for learning log-depth random quantum circuits with Haar random gates up to polynomially small diamond distance, given oracle access to the circuit. Other applications of this new scrambling speed lower bound include:

• An optimal $\Omega(\log\varepsilon^{-1})$ depth lower bound for $\varepsilon$-approximate unitary designs on any circuit architecture;
• A polynomial-time quantum algorithm that computes the depth of a bounded-depth circuit, given oracle access to the circuit.

Our learning and depth-testing algorithms apply to architectures defined over any geometric dimension, and can be generalized to a wide class of architectures with good lightcone properties.

@misc{FGZ24,
	title = {Anti-Concentration for the Unitary Haar Measure and Applications to Random Quantum Circuits}, 
	author = {Bill Fefferman and Soumik Ghosh and Wei Zhan},
	year = {2024},
	eprint = {2407.19561},
	archivePrefix = {arXiv},
	primaryClass = {quant-ph}
}

Given a distribution over $[n]^n$ such that any $k$ coordinates need $k/\log^{O(1)}n$ bits of communication to sample, we prove that any map that samples this distribution from uniform cells requires locality $\Omega(\log(n/k)/\log\log(n/k))$. In particular, we show that for any constant $\delta>0$, there exists $\varepsilon=2^{-\Omega(n^{1-\delta})}$ such that $\Omega(\log n/\log\log n)$ non-adaptive cell probes on uniform cells are required to:

• Sample a uniformly random permutation on $n$ elements with error $1-\varepsilon$. This provides an exponential improvement on the $\Omega(\log\log n)$ cell probe lower bound by Viola.
• Sample an $n$-vector with each element independently drawn from a random $n^{1-\delta}$-vector, with error $1-\varepsilon$. This provides the first adaptive vs non-adaptive cell probe separation for sampling.

The major technical component in our proof is a new combinatorial theorem about flower with small kernel, i.e. a collection of sets where few elements appear more than once. We show that in a family of $n$ sets, each with size $O(\log n/\log\log n)$, there must be $k=\mathrm{poly}(n)$ sets where at most $k/\log^{O(1)}n$ elements appear more than once.

To show the lower bound on sampling permutation, we also prove a new $\Omega(k)$ communication lower bound on sampling uniformly distributed disjoint subsets of $[n]$ of size $k$, with error $1-2^{-\Omega(k^2/n)}$. This result unifies and subsumes the lower bound for $k=\Theta(\sqrt{n})$ by Ambainis et al., and the lower bound for $k=\Theta(n)$ by Göös and Watson.

@inproceedings{YZ24a,
	author = {Huacheng Yu and Wei Zhan},
	editor  = {Venkatesan Guruswami},
	title  = {Sampling, Flowers and Communication},
	booktitle = {15th Innovations in Theoretical Computer Science Conference, {ITCS} 2024},
	series = {LIPIcs},
	volume = {287},
	pages = {100:1--100:11},
	publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
	year = {2024},
	doi = {10.4230/LIPICS.ITCS.2024.100}
}

We prove the first polynomial separation between randomized and deterministic time-space tradeoffs of multi-output functions. In particular, we present a total function that on the input of $n$ elements in $[n]$, outputs $O(n)$ elements, such that:

• There exists a randomized oblivious algorithm with space $O(\log n)$, time $O(n\log n)$ and one-way access to randomness, that computes the function with probability $1-O(1/n)$;
• Any deterministic oblivious branching program with space $S$ and time $T$ that computes the function must satisfy $T^2S\geq\Omega(n^{2.5}/\log n)$.

This implies that logspace randomized algorithms for multi-output functions cannot be black-box derandomized without an $\tilde{\Omega}(n^{1/4})$ overhead in time.

Since previously all the polynomial time-space tradeoffs of multi-output functions are proved via the Borodin-Cook method, which is a probabilistic method that inherently gives the same lower bound for randomized and deterministic branching programs, our lower bound proof is intrinsically different from previous works.

We also examine other natural candidates for proving such separations, and show that any polynomial separation for these problems would resolve the long-standing open problem of proving $n^{1+\Omega(1)}$ time lower bound for decision problems with $\mathrm{polylog}(n)$ space.

@inproceedings{YZ24,
	author = {Huacheng Yu and Wei Zhan},
	editor  = {Venkatesan Guruswami},
	title  = {Randomized vs. Deterministic Separation in Time-Space Tradeoffs of Multi-Output Functions},
	booktitle = {15th Innovations in Theoretical Computer Science Conference, {ITCS} 2024},
	series = {LIPIcs},
	volume = {287},
	pages = {99:1--99:15},
	publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
	year = {2024},
	doi = {10.4230/LIPICS.ITCS.2024.99}
}

In this note, we observe that quantum logspace computations are verifiable by classical logspace algorithms, with unconditional security. More precisely, every language in $\mathsf{BQL}$ has an (information-theoretically secure) streaming proof with a quantum logspace prover and a classical logspace verifier. The prover provides a polynomial-length proof that is streamed to the verifier. The verifier has a read-once one-way access to that proof and is able to verify that the computation was performed correctly. That is, if the input is in the language and the prover is honest, the verifier accepts with high probability, and, if the input is not in the language, the verifier rejects with high probability even if the prover is adversarial. Moreover, the verifier uses only $O(\log n)$ random bits.

@inproceedings{GRZ24,
	author = {Uma Girish and Ran Raz and Wei Zhan},
	editor = {Merav Parter and Seth Pettie},
	title = {Quantum Logspace Computations are Verifiable},
	booktitle = {2024 Symposium on Simplicity in Algorithms, {SOSA} 2024},
	pages = {144--150},
	publisher = {{SIAM}},
	year = {2024},
	doi = {10.1137/1.9781611977936.14}
}

Let $\mathcal{L}$ be a language that can be decided in linear space and let $\epsilon>0$ be any constant. Let $\mathcal{A}$ be the exponential hardness assumption that for every $n$, membership in $\mathcal{L}$ for inputs of length $n$ cannot be decided by circuits of size smaller than $2^{\epsilon n}$. We prove that for every function $f :\{0,1\}^*\rightarrow\{0,1\}$, computable by a randomized logspace algorithm $R$, there exists a deterministic logspace algorithm $D$ (attempting to compute $f$), such that on every input $x$ of length $n$, the algorithm $D$ outputs one of the following:

1. The correct value $f(x)$.
2. The string: "I am unable to compute $f(x)$ because the hardness assumption $\mathcal{A}$ is false", followed by a (provenly correct) circuit of size smaller than $2^{\epsilon n'}$ for membership in $\mathcal{L}$ for inputs of length $n'$, for some $n'=\Theta(\log n)$; that is, a circuit that refutes $\mathcal{A}$.

Moreover, $D$ is explicitly constructed, given $R$.

We note that previous works on the hardness-versus-randomness paradigm give derandomized algorithms that rely blindly on the hardness assumption. If the hardness assumption is false, the algorithms may output incorrect values, and thus a user cannot trust that an output given by the algorithm is correct. Instead, our algorithm $D$ verifies the computation so that it never outputs an incorrect value. Thus, if $D$ outputs a value for $f(x)$, that value is certified to be correct. Moreover, if $D$ does not output a value for $f(x)$, it alerts that the hardness assumption was found to be false, and refutes the assumption.

Our next result is a universal derandomizer for $\mathsf{BPL}$ (the class of problems solvable by bounded-error randomized logspace algorithms): We give a deterministic algorithm $U$ that takes as an input a randomized logspace algorithm $R$ and an input $x$ and simulates the computation of $R$ on $x$, deteriministically. Under the widely believed assumption $\mathsf{BPL}=\mathsf{L}$, the space used by $U$ is at most $C_R\cdot\log n$ (where $C_R$ is a constant depending on $R$). Moreover, for every constant $c\geq 1$, if $\mathsf{BPL}\subseteq\mathsf{SPACE}[(\log(n))^{c}]$ then the space used by $U$ is at most $C_R\cdot(\log(n))^c$.

Finally, we prove that if optimal hitting sets for ordered branching programs exist then there is a deterministic logspace algorithm that, given a black-box access to an ordered branching program $B$ of size $n$, estimates the probability that $B$ accepts on a uniformly random input. This extends the result of (Cheng and Hoza CCC 2020), who proved that an optimal hitting set implies a white-box two-sided derandomization.

@inproceedings{PRZ23,
	author = {Edward Pyne and Ran Raz and Wei Zhan},
	title = {Certified Hardness vs. Randomness for Log-Space},
	booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS} 2023},
	pages = {989--1007},
	publisher = {{IEEE}},
	year = {2023},
	doi = {10.1109/FOCS57990.2023.00061},
}

In a work by Raz (J. ACM and FOCS 16), it was proved that any algorithm for parity learning on $n$ bits requires either $\Omega(n^2)$ bits of classical memory or an exponential number (in $n$) of random samples. A line of recent works continued that research direction and showed that for a large collection of classical learning tasks, either super-linear classical memory size or super-polynomially many samples are needed. All these works consider learning algorithms as classical branching programs, which perform classical computation within bounded memory.

However, these results do not capture all physical computational models, remarkably, quantum computers and the use of quantum memory. It leaves the possibility that a small piece of quantum memory could significantly reduce the need for classical memory or samples and thus completely change the nature of the classical learning task. Despite the recent research on the necessity of quantum memory for intrinsic quantum learning problems like shadow tomography and purity testing, the role of quantum memory in classical learning tasks remains obscure.

In this work, we study classical learning tasks in the presence of quantum memory. We prove that any quantum algorithm with both, classical memory and quantum memory, for parity learning on $n$ bits, requires either $\Omega(n^2)$ bits of classical memory or $\Omega(n)$ bits of quantum memory or an exponential number of samples. In other words, the memory-sample lower bound for parity learning remains qualitatively the same, even if the learning algorithm can use, in addition to the classical memory, a quantum memory of size $cn$ (for some constant $c>0$).

Our result is more general and applies to many other classical learning tasks. Following previous works, we represent by the matrix $M:A\times X \to \{-1,1\}$ the following learning task. An unknown $x$ is sampled uniformly at random from a concept class $X$, and a learning algorithm tries to uncover $x$ by seeing streaming of random samples $(a_i,b_i=M(a_i,x))$ where for every $i$, $a_i\in A$ is chosen uniformly at random. Assume that $k,\ell,r$ are integers such that any submatrix of $M$ of at least $2^{-k}\cdot|A|$ rows and at least $2^{-\ell}\cdot|X|$ columns, has a bias of at most $2^{-r}$. We prove that any algorithm with classical and quantum hybrid memory for the learning problem corresponding to $M$ needs either (1) $\Omega(k\cdot\ell)$ bits of classical memory, or (2) $\Omega(r)$ qubits of quantum memory, or (3) $2^{\Omega(r)}$ random samples, to achieve a success probability at least $2^{-O(r)}$.

Our results refute the possibility that a small amount of quantum memory significantly reduces the size of classical memory needed for efficient learning on these problems. Our results also imply improved security of several existing cryptographical protocols in the bounded-storage model (protocols that are based on parity learning on $n$ bits), proving that security holds even in the presence of a quantum adversary with at most $c n^2$ bits of classical memory and $cn$ bits of quantum memory (for some constant $c>0$).

@inproceedings{LRZ23,
	author = {Qipeng Liu and Ran Raz and Wei Zhan},
	editor = {Barna Saha and Rocco A. Servedio},
	title = {Memory-Sample Lower Bounds for Learning with Classical-Quantum Hybrid Memory},
	booktitle = {55th Annual {ACM} Symposium on Theory of Computing, {STOC} 2023},
	pages = {1097--1110},
	publisher = {{ACM}},
	year = {2023},
	doi = {10.1145/3564246.3585129}
}

Randomized algorithms and protocols assume the availability of a perfect source of randomness. In real life, however, perfect randomness is rare and is almost never guaranteed. The gap between these two facts motivated much of the work on randomness and derandomization in theoretical computer science.

In this work, we define a new type of randomized algorithms (and protocols), that we call robustly-randomized algorithms (protocols). Such algorithms have access to two separate (read-once) random strings. The first string is trusted to be perfectly random, but its length is bounded by some parameter $k = k(n)$ (where $n$ is the length of the input). We think of $k$ as relatively small, say sub-linear or poly-logarithmic in $n$. The second string is of unbounded length and is assumed to be random, but its randomness is not trusted.

The output of the algorithm is either an output in the set of possible outputs of the problem, or a special symbol, interpreted as do not know and denoted by $\bot$. On every input for the algorithm, the output of the algorithm must satisfy the following two requirements:

1. If the second random string is perfectly random then the algorithm must output the correct answer with high probability.
2. If the second random string is an arbitrary string, even adversarially chosen after seeing the input, the algorithm must output with high probability either the correct answer or the special symbol $\bot$.

We discuss relations of this new definition to several previously studied notions in randomness and derandomization. For example, when considering polynomial-time algorithms, if $k$ is logarithmic we get the complexity class $\mathsf{ZPP}$, while if $k$ is unbounded we get the complexity class $\mathsf{BPP}$, and for a general $k$, the algorithm can be viewed as an interactive proof with a probabilistic polynomial-time prover and a probabilistic polynomial-time verifier, where the prover is allowed an unlimited number of random bits and the verifier is limited to at most $k$ random bits.

Every previously-studied class of randomized algorithms or protocols, and more generally, every previous use of randomness in theoretical computer science, can be revisited and redefined in light of our new definition, by replacing each random string with a pair of random strings, the first is trusted to be perfectly random but is relatively short and the second is of unlimited length but its randomness is not trusted. The main question that we ask is: In which settings and for which problems is the untrusted random string helpful?

Our main technical observation is that every problem in the class $\mathsf{BPL}$ (of problems solvable by bounded-error randomized logspace algorithms) can be solved by a robustly-randomized logspace algorithm with $k=O(\log n)$, that is with just a logarithmic number of trusted random bits. We also give query complexity separations that show cases where the untrusted random string is provenly helpful. Specifically, we show that there are promise problems that can be solved by robustly-randomized protocols with only one query and just a logarithmic number of trusted random bits, whereas any randomized protocol requires either a linear number of random bits or an exponential number of queries, and any zero-error randomized protocol requires a polynomial number of queries.

@inproceedings{GRZ23,
	author = {Uma Girish and Ran Raz and Wei Zhan},
	editor = {Yael Tauman Kalai},
	title = {Is Untrusted Randomness Helpful?},
	booktitle = {14th Innovations in Theoretical Computer Science Conference, {ITCS} 2023},
	series = {LIPIcs},
	volume = {251},
	pages = {56:1--56:18},
	publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
	year = {2023},
	doi = {10.4230/LIPICS.ITCS.2023.56}
}

We prove that for every 3-player (3-prover) game $\mathcal G$ with value less than one, whose query distribution has the support $\mathcal{S} = \{(1,0,0), (0,1,0), (0,0,1)\}$ of hamming weight one vectors, the value of the $n$-fold parallel repetition $\mathcal G^{\otimes n}$ decays polynomially fast to zero; that is, there is a constant $c = c(\mathcal{G})>0$ such that the value of the game $\mathcal{G}^{\otimes n}$ is at most $n^{-c}$.

Following the recent work of Girish, Holmgren, Mittal, Raz and Zhan (STOC 2022), our result is the missing piece that implies a similar bound for a much more general class of multiplayer games: For every 3-player game $\mathcal G$ over binary questions and arbitrary answer lengths, with value less than 1, there is a constant $c = c(\mathcal{G})>0$ such that the value of the game $\mathcal G^{\otimes n}$ is at most $n^{-c}$.

Our proof technique is new and requires many new ideas. For example, we make use of the Level-$k$ inequalities from Boolean Fourier Analysis, which, to the best of our knowledge, have not been explored in this context prior to our work.

@inproceedings{GMRZ22,
	author = {Uma Girish and Kunal Mittal and Ran Raz and Wei Zhan},
	editor = {Amit Chakrabarti and Chaitanya Swamy},
	title = {Polynomial Bounds on Parallel Repetition for All 3-Player Games with Binary Inputs},
	booktitle = {Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques, {APPROX/RANDOM} 2022},
	series = {LIPIcs},
	volume = {245},
	pages = {6:1--6:17},
	publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
	year = {2022},
	doi = {10.4230/LIPICS.APPROX/RANDOM.2022.6}
}

We prove that for every 3-player (3-prover) game, with binary questions and answers and value $\lt 1$, the value of the $n$-fold parallel repetition of the game decays polynomially fast to 0. That is, for every such game, there exists a constant $c>0$, such that the value of the $n$-fold parallel repetition of the game is at most $n^{-c}$.

Along the way to proving this theorem, we prove two additional parallel repetition theorems for multiplayer (multiprover) games, that may be of independent interest:

Playerwise Connected Games (with any number of players and any Alphabet size): We identify a large class of multiplayer games and prove that for every game with value $\lt 1$ in that class, the value of the $n$-fold parallel repetition of the game decays polynomially fast to 0.

More precisely, our result applies for playerwise connected games, with any number of players and any alphabet size: For each player $i$, we define the graph $G_i$, whose vertices are the possible questions for that player and two questions $x,x'$ are connected by an edge if there exists a vector $y$ of questions for all other players, such that both $(x,y)$ and $(x',y)$ are asked by the referee with non-zero probability. We say that the game is playerwise connected if for every $i$, the graph $G_i$ is connected.

Our class of playerwise connected games is strictly larger than the class of connected games that was defined by Dinur, Harsha, Venkat and Yuen (ITCS 2017) and for which they proved exponential decay bounds on the value of parallel repetition. For playerwise connected games that are not connected, only inverse Ackermann decay bounds were previously known (Verbitsky 1996).

Exponential Bounds for the Anti-Correlation Game: In the 3-player anti-correlation game, two out of three players are given $1$ as input, and the remaining player is given $0$. The two players who were given $1$ must produce different outputs in $\{0,1\}$. We prove that the value of the $n$-fold parallel repetition of that game decays exponentially fast to 0. That is, there exists a constant $c>0$, such that the value of the $n$-fold parallel repetition of the game is at most $2^{-cn}$. Only inverse Ackermann decay bounds were previously known (Verbitsky 1996).

The 3-player anti-correlation game was studied and motivated in several previous works. In particular, Holmgren and Yang (STOC 2019) gave it as an example for a 3-player game whose non-signaling value (is smaller than 1 and yet) does not decrease at all under parallel repetition.

@inproceedings{GHMRZ22,
	author = {Uma Girish and Justin Holmgren and Kunal Mittal and Ran Raz and Wei Zhan},
	editor = {Stefano Leonardi and Anupam Gupta},
	title = {Parallel repetition for all 3-player games over binary alphabet},
	booktitle = {54th Annual {ACM} {SIGACT} Symposium on Theory of Computing, {STOC} 2022},
	pages = {998--1009},
	publisher = {{ACM}},
	year = {2022},
	doi = {10.1145/3519935.3520071}
}

We give a new proof of the fact that the parallel repetition of the (3-player) GHZ game reduces the value of the game to zero polynomially quickly. That is, we show that the value of the $n$-fold GHZ game is at most $n^{-\Omega(1)}$. This was first established by Holmgren and Raz (2020). We present a new proof of this theorem that we believe to be simpler and more direct. Unlike most previous works on parallel repetition, our proof makes no use of information theory, and relies on the use of Fourier analysis.

The GHZ game [Greenberger, Horne and Zeilinger 1989] has played a foundational role in the understanding of quantum information theory, due in part to the fact that quantum strategies can win the GHZ game with probability 1. It is possible that improved parallel repetition bounds may find applications in this setting.

Recently, Dinur, Harsha, Venkat, and Yuen (ITCS'17) highlighted the GHZ game as a simple three-player game, which is in some sense maximally far from the class of multi-player games whose behavior under parallel repetition is well understood. Dinur et al. conjectured that parallel repetition decreases the value of the GHZ game exponentially quickly, and speculated that progress on proving this would shed light on parallel repetition for general multi-player (multi-prover) games.

@inproceedings{GHMRZ21,
	author = {Uma Girish and Justin Holmgren and Kunal Mittal and Ran Raz and Wei Zhan},
	title = {Parallel Repetition for the {GHZ} Game: {A} Simpler Proof},
	booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, {APPROX/RANDOM} 2021},
	series = {LIPIcs},
	volume = {207},
	pages = {62:1--62:19},
	publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
	year = {2021}
}

The Forrelation problem, first introduced by [Aaronson 2010] and [Aaronson and Ambainis 2015], is a well studied computational problem in the context of separating quantum and classical computational models. Variants of this problem were used to give tight separations between quantum and classical query complexity [Aaronson and Ambainis 2015]; the first separation between polylogarithmic quantum query complexity and bounded-depth circuits of super-polynomial size, a result that also implied an oracle separation of the classes $\mathsf{BQP}$ and $\mathsf{PH}$ [Raz and Tal 2019]; and improved separations between quantum and classical communication complexity [Girish, Raz and Tal 2019]. In all these separations, the lower bound for the classical model only holds when the advantage of the protocol (over a random guess) is more than $\approx 1/\sqrt{N}$, that is, the success probability is larger than $\approx 1/2+1/\sqrt{N}$. This is unavoidable as $\approx 1/\sqrt{N}$ is the correlation between two coordinates of an input that is sampled from the Forrelation distribution, and hence there are simple classical protocols that achieve advantage $\approx 1/\sqrt{N}$, in all these models.

To achieve separations when the classical protocol has smaller advantage, we study in this work the $\mathrm{XOR}$ of $k$ independent copies of (a variant of) the Forrelation function (where $k\ll N$). We prove a very general result that shows that any family of Boolean functions that is closed under restrictions, whose Fourier mass at level $2k$ is bounded by $\alpha^k$ (that is, the sum of the absolute values of all Fourier coefficients at level $2k$ is bounded by $\alpha^k$), cannot compute the $\mathrm{XOR}$ of $k$ independent copies of the Forrelation function with advantage better than $O(\alpha^k/N^{k/2})$. This is a strengthening of a result of [Chattopadhyay, Hatami, Lovett and Tal 2019], that gave a similar statement for $k=1$, using the technique of [Raz and Tal 2019]. We give several applications of our result. In particular, we obtain the following separations:

Quantum versus Classical Communication Complexity: We give the first example of a partial Boolean function that can be computed by a simultaneous-message quantum protocol with communication complexity $\mathrm{polylog}(N)$ (where Alice and Bob also share $\mathrm{polylog}(N)$ EPR pairs), and such that, any classical randomized protocol of communication complexity at most $\tilde{o}(n^{1/4})$, with any number of rounds, has quasipolynomially small advantage over a random guess. Previously, only separations where the classical protocol has polynomially small advantage were known between these models [Gavinsky 2016, Girish, Raz and Tal 2019].

Quantum Query Complexity versus Bounded Depth Circuits: We give the first example of a partial Boolean function that has a quantum query algorithm with query complexity $\mathrm{polylog}(N)$, and such that, any constant-depth circuit of quasipolynomial size has quasipolynomially small advantage over a random guess. Previously, only separations where the constant-depth circuit has polynomially small advantage were known [Raz and Tal 2019].

@inproceedings{GRZ21b,
	author = {Uma Girish and Ran Raz and Wei Zhan},
	title = {Lower Bounds for {XOR} of Forrelations},
	booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, {APPROX/RANDOM} 2021},
	series = {LIPIcs},
	volume = {207},
	pages = {52:1--52:14},
	publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
	year = {2021}
}

We give a quantum logspace algorithm for powering contraction matrices, that is, matrices with spectral norm at most 1. The algorithm gets as an input an arbitrary $n\times n$ contraction matrix $A$, and a parameter $T\leq\mathrm{poly}(n)$ and outputs the entries of $A^T$, up to (arbitrary) polynomially small additive error. The algorithm applies only unitary operators, without intermediate measurements. We show various implications and applications of this result:

First, we use this algorithm to show that the class of quantum logspace algorithms with only quantum memory and with intermediate measurements is equivalent to the class of quantum logspace algorithms with only quantum memory without intermediate measurements. This shows that the deferred-measurement principle, a fundamental principle of quantum computing, applies also for quantum logspace algorithms (without classical memory). More generally, we give a quantum algorithm with space $O(S+\log T)$ that takes as an input the description of a quantum algorithm with quantum space $S$ and time $T$, with intermediate measurements (without classical memory), and simulates it unitarily with polynomially small error, without intermediate measurements.

Since unitary transformations are reversible (while measurements are irreversible) an interesting aspect of this result is that it shows that any quantum logspace algorithm (without classical memory) can be simulated by a reversible quantum logspace algorithm. This proves a quantum analogue of the result of Lange, McKenzie and Tapp that deterministic logspace is equal to reversible logspace [Lange, McKenzie and Tapp, 2000].

Finally, we use our results to show non-trivial classical simulations of quantum logspace learning algorithms.

@inproceedings{GRZ21,
	author = {Uma Girish and Ran Raz and Wei Zhan},
	title = {Quantum Logspace Algorithm for Powering Matrices with Bounded Norm},
	booktitle = {48th International Colloquium on Automata, Languages, and Programming, {ICALP} 2021},
	series = {LIPIcs},
	volume = {198},
	pages = {73:1--73:20},
	publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
	year = {2021}
}

We show that the set of entries generated by any finite set of doubly stochastic matrices is nowhere dense, in contrast to the cases of stochastic matrices or unitary matrices. In other words, there is no finite universal set of doubly stochastic matrices, even with the weakest notion of universality.

Our proof is based on a theorem for topological semigroups with the convergent property. A topological semigroup is convergent if every infinite product converges. We show that in a compact and convergent semigroup, under some restrictions, the closure of every finitely generated subsemigroup can be instead generated directly by the generating set and the limits of infinite products.

@misc{Z21,
	title = {Universality for Doubly Stochastic Matrices}, 
	author = {Wei Zhan},
	year = {2021},
	eprint = {2010.16257},
	archivePrefix = {arXiv},
	primaryClass = {math.FA},
}

We study a new model of space-bounded computation, the random-query model. The model is based on a branching-program over input variables $x_1,\ldots,x_n$. In each time step, the branching program gets as an input a random index $i\in\{1,\ldots,n\}$, together with the input variable $x_i$ (rather than querying an input variable of its choice, as in the case of a standard (oblivious) branching program). We motivate the new model in various ways and study time-space tradeoff lower bounds in this model.

Our main technical result is a quadratic time-space lower bound for zero-error computations in the random-query model, for XOR, Majority and many other functions. More precisely, a zero-error computation is a computation that stops with high probability and such that conditioning on the event that the computation stopped, the output is correct with probability 1. We prove that for any Boolean function $f: \{0,1\}^n \rightarrow \{0,1\}$, with sensitivity $k$, any zero-error computation with time $T$ and space $S$, satisfies $T\cdot (S+\log n) \geq \Omega(n \cdot k)$. We note that the best time-space lower bounds for standard oblivious branching programs are only slightly super linear and improving these bounds is an important long-standing open problem.

To prove our results, we study a memory-bounded variant of the coupon-collector problem that seems to us of independent interest and to the best of our knowledge has not been studied before. We consider a zero-error version of the coupon-collector problem. In this problem, the coupon-collector could explicitly choose to stop when he/she is sure with zero-error that all coupons have already been collected. We prove that any zero-error coupon-collector that stops with high probability in time $T$, and uses space $S$, satisfies $T\cdot (S+\log n) \geq \Omega(n^2)$, where $n$ is the number of different coupons.

@inproceedings{RZ20,
	author = {Ran Raz and Wei Zhan},
	title = {The Random-Query Model and the Memory-Bounded Coupon Collector},
	booktitle = {11th Innovations in Theoretical Computer Science Conference, {ITCS} 2020},
	series = {LIPIcs},
	volume = {151},
	pages = {20:1--20:11},
	publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
	year = {2020}
}

It is a long standing open problem whether Yao-Yao graphs $\mathsf{YY}_k$ are all spanners [Li et al. 2002]. Bauer and Damian [Bauer and Damian, 2012] showed that all $\mathsf{YY}_{6k}$ for $k\geq 6$ are spanners. Li and Zhan [Li and Zhan, 2016] generalized their result and proved that all even Yao-Yao graphs $\mathsf{YY}_{2k}$ are spanners (for $k\geq 42$). However, their technique cannot be extended to odd Yao-Yao graphs, and whether they are spanners are still elusive. In this paper, we show that, surprisingly, for any integer $k\geq 1$, there exist odd Yao-Yao graph $\mathsf{YY}_{2k+1}$ instances, which are not spanners.

@inproceedings{JLZ18,
	author = {Yifei Jin and Jian Li and Wei Zhan},
	title = {Odd Yao-Yao Graphs are Not Spanners},
	booktitle = {34th International Symposium on Computational Geometry, {SoCG} 2018},
	series = {LIPIcs},
	volume = {99},
	pages = {49:1--49:15},
	publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
	year = {2018}
}

We study a type of generalized two-sided markets where a set of sellers, each with multiple units of the same divisible good, trade with a set of buyers. Possible trade of each unit between a buyer and a seller generates a given welfare (to be split among them), indicated by the weight of the edge between them. What makes the markets interesting is a special type of constraints, called transaction threshold constraints, which essentially mean that the amount of goods traded between a pair of agents can either be zero or above a certain edge-specific threshold. This constraints has originally been motivated from the water-right market domain by Liu et. al. where minimum thresholds must be imposed to mitigate administrative and other costs. The same constraints have been witnessed in several other market domains.

Without the threshold constraints, it is known that the seminal result by Shapley and Shubick holds: the social welfare maximizing assignments between buyers and sellers are in the core. In other words, by algorithmically optimizing the market, one can obtain desirable incentive properties for free. This is no longer the case for markets with threshold constraints: the model considered in this paper.

We first demonstrate a counterexample where no optimal assignment (with respect to any way to split the trade welfare) is in the core. Motivated by this observation, we study the stability of the optimal assignments from the following two perspectives: 1) by relaxing the definition of core; 2) by restricting the graph structure. For the first line, we show that the optimal assignments are pairwise stable, and no coalition can benefit twice as large when they deviate. For the second line, we exactly characterize the graph structure for the nonemptyness of core: the core is nonempty if and only if the market graph is a tree. Last but not least, we compliment our previous results by quantitatively measuring the welfare loss caused by the threshold constraints: the optimal welfare without transaction thresholds is no greater than constant times of that with transaction thresholds. We evaluate and confirm our theoretical results using real data from a water-right market.

@inproceedings{LLTXZ17,
	author = {Zhiyuan Li and Yicheng Liu and Pingzhong Tang and Tingting Xu and Wei Zhan},
	title = {Stability of Generalized Two-sided Markets with Transaction Thresholds},
	booktitle = {16th Conference on Autonomous Agents and MultiAgent Systems, {AAMAS} 2017},
	pages = {290--298},
	publisher = {{ACM}},
	year = {2017}
}

Energy is often the most constrained resource for battery-powered wireless devices, and most of the energy is often spent on transceiver usage (i.e., transmitting and receiving packets) rather than computation. In this article, we study the energy complexity of fundamental problems in several models of wireless radio networks. It turns out that energy complexity is very sensitive to whether the devices can generate random bits and their ability to detect collisions. We consider four collision detection models: $\textsf{Strong-CD}$ (in which transmitters and listeners detect collisions), $\textsf{Sender-CD}$ (in which only transmitters detect collisions), $\textsf{Receiver-CD}$ (in which only listeners detect collisions), and $\textsf{No-CD}$ (in which no one detects collisions).

The take-away message of our results is quite surprising. For randomized algorithms, there is an exponential gap between the energy complexity of $\textsf{Sender-CD}$ and $\textsf{Receiver-CD}$: Randomized: $\textsf{No-CD} = \textsf{Sender-CD} \gg \textsf{Receiver-CD} = \textsf{Strong-CD}$ and for deterministic algorithms, there is another exponential gap in energy complexity, but in the reverse direction: Deterministic: $\textsf{No-CD} = \textsf{Receiver-CD} \gg \textsf{Sender-CD} = \textsf{Strong-CD}$ Precisely, the randomized energy complexity of Leader Election is $\Theta(\log^* n)$ in $\textsf{Sender-CD}$ but $\Theta(\log(\log^* n))$ in $\textsf{Receiver-CD}$, where $n$ is the number of devices, which is unknown to the devices at the beginning; the deterministic complexity of Leader Election is $\Theta(\log N)$ in $\textsf{Receiver-CD}$ but $\Theta(\log\log N)$ in $\textsf{Sender-CD}$, where $N$ is the size of the ID space.

There is a tradeoff between time and energy. We provide a new upper bound on the time-energy tradeoff curve for randomized algorithms. A critical component of this algorithm is a new deterministic Leader Election algorithm for dense instances, when $n = \Theta(N)$, with inverse Ackermann energy complexity.

@article{10.1145/3341111,
	author = {Yi-Jun Chang and Tsvi Kopelowitz and Seth Pettie and Ruosong Wang and Wei Zhan},
	title = {Exponential Separations in the Energy Complexity of Leader Election},
	year = {2019},
	publisher = {Association for Computing Machinery},
	volume = {15},
	number = {4},
	issn = {1549-6325},
	doi = {10.1145/3341111},
	journal = {ACM Trans. Algorithms},
	month = oct,
	articleno = {49},
	numpages = {31}
}

We study the k-regret minimizing query ($k$-$\mathsf{RMS}$), which is a useful operator for supporting multi-criteria decision-making. Given two integers $k$ and $r$, a $k$-$\mathsf{RMS}$ returns $r$ tuples from the database which minimize the $k$-regret ratio, defined as one minus the worst ratio between the $k$-th maximum utility score among all tuples in the database and the maximum utility score of the $r$ tuples returned. A solution set contains only $r$ tuples, enjoying the benefits of both top-$k$ queries and skyline queries. Since proposed in 2012, the query has been studied extensively in recent years. In this paper, we advance the theory and the practice of $k$-$\mathsf{RMS}$ in the following aspects. First, we develop efficient algorithms for $k$-$\mathsf{RMS}$ (and its decision version) when the dimensionality is 2. The running time of our algorithms outperforms those of previous ones.

Our experimental results show that our algorithms are more efficient than previous ones on both synthetic and real datasets up to three orders of magnitude. Second, we show that $k$-$\mathsf{RMS}$ is $\mathsf{NP}$-hard even when the dimensionality is 3. This provides a complete characterization of the complexity of $k$-$\mathsf{RMS}$, and answers an open question in previous studies. In addition, we present approximation algorithms for the problem when the dimensionality is 3 or larger.

@inproceedings{CLWWWWZ17,
	author = {Wei Cao and Jian Li and Haitao Wang and Kangning Wang and Ruosong Wang and Raymond Chi{-}Wing Wong and Wei Zhan},
	title = {k-Regret Minimizing Set: Efficient Algorithms and Hardness},
	booktitle = {20th International Conference on Database Theory, {ICDT} 2017},
	series = {LIPIcs},
	volume = {68},
	pages = {11:1--11:19},
	publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
	year = {2017}
}

It is an open problem whether Yao-Yao graphs $\mathsf{YY}_k$ (also known as sparse-Yao graphs) are all spanners when the integer parameter $k$ is large enough. In this paper we show that, for any integer $k\geq42$, the Yao-Yao graph $\mathsf{YY}_{2k}$ is a $t_k$-spanner, with stretch factor $t_k=6.03+O(k^{-1})$ when k tends to infinity. Our result generalizes the best known result which asserts that all $\mathsf{YY}_{6k}$ are spanners for $k\geq 6$ [Bauer and Damian, SODA’13]. Our proof is also somewhat simpler.

@inproceedings{LZ16,
	author = {Jian Li and Wei Zhan},
	title = {Almost All Even Yao-Yao Graphs Are Spanners},
	booktitle = {24th Annual European Symposium on Algorithms, {ESA} 2016},
	series = {LIPIcs},
	volume = {57},
	pages = {62:1--62:13},
	publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
	year = {2016}
}