Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > A-Z > Q:
A - B - C - D - E - F - G - H - I - J - K - L - M - N - O - P - Q - R - S - T - U - V - W - X - Y - Z - Other

Q
TR22-080 | 25th May 2022
Meena Mahajan, Gaurav Sood

QBF Merge Resolution is powerful but unnatural

Revisions: 1

The Merge Resolution proof system (M-Res) for QBFs, proposed by Beyersdorff et al. in 2019, explicitly builds partial strategies inside refutations. The original motivation for this approach was to overcome the limitations encountered in long-distance Q-Resolution proof system (LD-Q-Res), where the syntactic side-conditions, while prohibiting all unsound resolutions, also end ... more >>>


TR23-051 | 18th April 2023
Benjamin Böhm, Olaf Beyersdorff

QCDCL vs QBF Resolution: Further Insights

We continue the investigation on the relations of QCDCL and QBF resolution systems. In particular, we introduce QCDCL versions that tightly characterise QU-Resolution and (a slight variant of) long-distance Q-Resolution. We show that most QCDCL variants - parameterised by different policies for decisions, unit propagations and reductions -- lead to ... more >>>


TR21-131 | 10th September 2021
Olaf Beyersdorff, Benjamin Böhm

QCDCL with Cube Learning or Pure Literal Elimination - What is best?

Revisions: 1

Quantified conflict-driven clause learning (QCDCL) is one of the main approaches for solving quantified Boolean formulas (QBF). We formalise and investigate several versions of QCDCL that include cube learning and/or pure-literal elimination, and formally compare the resulting solving models via proof complexity techniques. Our results show that almost all of ... more >>>


TR19-015 | 7th February 2019
William Kretschmer

QMA Lower Bounds for Approximate Counting

We prove a query complexity lower bound for $QMA$ protocols that solve approximate counting: estimating the size of a set given a membership oracle. This gives rise to an oracle $A$ such that $SBP^A \not\subset QMA^A$, resolving an open problem of Aaronson [2]. Our proof uses the polynomial method to ... more >>>


TR05-129 | 30th October 2005
Scott Aaronson

QMA/qpoly Is Contained In PSPACE/poly: De-Merlinizing Quantum Protocols

This paper introduces a new technique for removing existential quantifiers
over quantum states. Using this technique, we show that there is no way
to pack an exponential number of bits into a polynomial-size quantum
state, in such a way that the value of any one of those bits ... more >>>


TR03-021 | 4th April 2003
Mikhail Vyalyi

QMA=PP implies that PP contains PH

We consider possible equality QMA=PP and give an argument
against it. Namely, this equality implies that PP contains PH. The argument is based on the strong form of Toda's theorem and
the strengthening of the proof for inclusion $QMA\subseteq PP$ due to Kitaev and Watrous.

more >>>

TR21-109 | 20th July 2021
Sravanthi Chede, Anil Shukla

QRAT Polynomially Simulates Merge Resolution.

Merge Resolution (MRes [Beyersdorff et al. J. Autom. Reason.'2021] ) is a refutational proof system for quantified Boolean formulas (QBF). Each line of MRes consists of clauses with only existential literals, together with information of countermodels stored as merge maps. As a result, MRes has strategy extraction by design. The ... more >>>


TR11-084 | 23rd May 2011
Madhur Tulsiani, Julia Wolf

Quadratic Goldreich-Levin Theorems

Decomposition theorems in classical Fourier analysis enable us to express a bounded function in terms of few linear phases with large Fourier coefficients plus a part that is pseudorandom with respect to linear phases. The Goldreich-Levin algorithm can be viewed as an algorithmic analogue of such a decomposition as it ... more >>>


TR15-205 | 15th December 2015
Emanuele Viola

Quadratic maps are hard to sample

This note proves the existence of a quadratic GF(2) map
$p : \{0,1\}^n \to \{0,1\}$ such that no constant-depth circuit
of size $\poly(n)$ can sample the distribution $(u,p(u))$
for uniform $u$.

more >>>

TR17-031 | 15th February 2017
Thomas Watson

Quadratic Simulations of Merlin-Arthur Games

Revisions: 1

The known proofs of $\text{MA}\subseteq\text{PP}$ incur a quadratic overhead in the running time. We prove that this quadratic overhead is necessary for black-box simulations; in particular, we obtain an oracle relative to which $\text{MA-TIME}(t)\not\subseteq\text{P-TIME}(o(t^2))$. We also show that 2-sided-error Merlin--Arthur games can be simulated by 1-sided-error Arthur--Merlin games with quadratic ... more >>>


TR17-123 | 2nd August 2017
Dmytro Gavinsky, Rahul Jain, Hartmut Klauck, Srijita Kundu, Troy Lee, Miklos Santha, Swagato Sanyal, Jevgenijs Vihrovs

Quadratically Tight Relations for Randomized Query Complexity

Let $f:\{0,1\}^n \rightarrow \{0,1\}$ be a Boolean function. The certificate complexity $C(f)$ is a complexity measure that is quadratically tight for the zero-error randomized query complexity $R_0(f)$: $C(f) \leq R_0(f) \leq C(f)^2$. In this paper we study a new complexity measure that we call expectational certificate complexity $EC(f)$, which is ... more >>>


TR05-036 | 28th March 2005
Hubie Chen

Quantified Constraint Satisfaction, Maximal Constraint Languages, and Symmetric Polymorphisms

The constraint satisfaction problem (CSP) is a convenient framework for modelling search problems; the CSP involves deciding, given a set of constraints on variables, whether or not there is an assignment to the variables satisfying all of the constraints. This paper is concerned with the quantified constraint satisfaction problem (QCSP), ... more >>>


TR05-024 | 8th February 2005
Michael Bauland, Elmar Böhler, Nadia Creignou, Steffen Reith, Henning Schnoor, Heribert Vollmer

Quantified Constraints: The Complexity of Decision and Counting for Bounded Alternation

We consider constraint satisfaction problems parameterized by the set of allowed constraint predicates. We examine the complexity of quantified constraint satisfaction problems with a bounded number of quantifier alternations and the complexity of the associated counting problems. We obtain classification results that completely solve the Boolean case, and we show ... more >>>


TR17-145 | 19th September 2017
Roei Tell

Quantified derandomization of linear threshold circuits

Revisions: 2

One of the prominent current challenges in complexity theory is the attempt to prove lower bounds for $TC^0$, the class of constant-depth, polynomial-size circuits with majority gates. Relying on the results of Williams (2013), an appealing approach to prove such lower bounds is to construct a non-trivial derandomization algorithm for ... more >>>


TR18-156 | 8th September 2018
Mark Bun, Robin Kothari, Justin Thaler

Quantum algorithms and approximating polynomials for composed functions with shared inputs

Revisions: 2

We give new quantum algorithms for evaluating composed functions whose inputs may be shared between bottom-level gates. Let $f$ be a Boolean function and consider a function $F$ obtained by applying $f$ to conjunctions of possibly overlapping subsets of $n$ variables. If $f$ has quantum query complexity $Q(f)$, we give ... more >>>


TR21-126 | 25th August 2021
Yilei Chen, Qipeng Liu, Mark Zhandry

Quantum Algorithms for Variants of Average-Case Lattice Problems via Filtering

Revisions: 1

We show polynomial-time quantum algorithms for the following problems:
(*) Short integer solution (SIS) problem under the infinity norm, where the public matrix is very wide, the modulus is a polynomially large prime, and the bound of infinity norm is set to be half of the modulus minus a ... more >>>


TR24-050 | 5th March 2024
Omri Shmueli

Quantum Algorithms in a Superposition of Spacetimes

Revisions: 1

Quantum computers are expected to revolutionize our ability to process information. The advancement from classical to quantum computing is a product of our advancement from classical to quantum physics -- the more our understanding of the universe grows, so does our ability to use it for computation. A natural question ... more >>>


TR04-045 | 15th April 2004
Hartmut Klauck, Robert Spalek, Ronald de Wolf

Quantum and Classical Strong Direct Product Theorems and Optimal Time-Space Tradeoffs

A strong direct product theorem says that if we want to compute
k independent instances of a function, using less than k times
the resources needed for one instance, then our overall success
probability will be exponentially small in k.
We establish such theorems for the classical as well as ... more >>>


TR04-023 | 21st January 2004
Yaoyun Shi

Quantum and Classical Tradeoffs

We initiate the study of quantifying the quantumness of
a quantum circuit by the number of gates that do not preserve
the computational basis, as a means to understand the nature
of quantum algorithmic speedups.
Intuitively, a reduction in the quantumness requires
an increase in the amount of classical computation, ... more >>>


TR13-010 | 4th January 2013
Yang Liu, Shengyu Zhang

Quantum and randomized communication complexity of XOR functions in the SMP model

Communication complexity of XOR functions $f (x \oplus y)$ has attracted increasing attention in recent years, because of its connections to Fourier analysis, and its exhibition of exponential separations between classical and quantum communication complexities of total functions.However, the complexity of certain basic functions still seems elusive especially in the ... more >>>


TR02-013 | 30th January 2002
Chris Pollett, Farid Ablayev, Cristopher Moore, Chris Pollett

Quantum and Stochastic Programs of Bounded Width

Revisions: 1

We prove upper and lower bounds on the power of quantum and stochastic
branching programs of bounded width. We show any NC^1 language can
be accepted exactly by a width-2 quantum branching program of
polynomial length, in contrast to the classical case where width 5 is
necessary unless \NC^1=\ACC. ... more >>>


TR24-029 | 16th February 2024
Noel Arteche, Gaia Carenini, Matthew Gray

Quantum Automating $\mathbf{TC}^0$-Frege Is LWE-Hard

Revisions: 1

We prove the first hardness results against efficient proof search by quantum algorithms. We show that under Learning with Errors (LWE), the standard lattice-based cryptographic assumption, no quantum algorithm can weakly automate $\mathbf{TC}^0$-Frege. This extends the line of results of Kraí?ek and Pudlák (Information and Computation, 1998), Bonet, Pitassi, and ... more >>>


TR03-005 | 28th December 2002
Scott Aaronson

Quantum Certificate Complexity

Given a Boolean function f, we study two natural generalizations of the certificate complexity C(f): the randomized certificate complexity RC(f) and the quantum certificate complexity QC(f). Using Ambainis' adversary method, we exactly characterize QC(f) as the square root of RC(f). We then use this result to prove the new relation ... more >>>


TR99-032 | 7th July 1999
Cristopher Moore

Quantum Circuits: Fanout, Parity, and Counting

We propose definitions of $\QAC^0$, the quantum analog of the
classical class $\AC^0$ of constant-depth circuits with AND and OR
gates of arbitrary fan-in, and $\QACC^0[q]$, the analog of the class
$\ACC^0[q]$ where $\Mod_q$ gates are also allowed. We show that it is
possible to make a `cat' state on ... more >>>


TR24-172 | 5th November 2024
Mika Göös, Tom Gur, Siddhartha Jain, Jiawei Li

Quantum Communication Advantage in TFNP

We exhibit a total search problem whose communication complexity in the quantum SMP (simultaneous message passing) model is exponentially smaller than in the classical two-way randomized model. Moreover, the quantum protocol is computationally efficient and its solutions are classically verifiable, that is, the problem lies in the communication analogue of ... more >>>


TR05-003 | 23rd December 2004
Scott Aaronson

Quantum Computing, Postselection, and Probabilistic Polynomial-Time

I study the class of problems efficiently solvable by a quantum computer, given the ability to "postselect" on the outcomes of measurements. I prove that this class coincides with a classical complexity class called PP, or Probabilistic Polynomial-Time. Using this result, I show that several simple changes to the axioms ... more >>>


TR05-146 | 25th November 2005
Gábor Erdèlyi, Tobias Riege, Jörg Rothe

Quantum Cryptography: A Survey

Revisions: 2

We survey some results in quantum cryptography. After a brief
introduction to classical cryptography, we provide the physical and
mathematical background needed and present some fundamental protocols
from quantum cryptography, including quantum key distribution and
quantum bit commitment protocols.

more >>>

TR07-032 | 27th March 2007
Pavel Pudlak

Quantum deduction rules

We define propositional quantum Frege proof systems and compare it
with classical Frege proof systems.

more >>>

TR17-011 | 22nd January 2017
Boaz Barak, Pravesh Kothari, David Steurer

Quantum entanglement, sum of squares, and the log rank conjecture

For every constant $\epsilon>0$, we give an $\exp(\tilde{O}(\sqrt{n}))$-time algorithm for the $1$ vs $1-\epsilon$ Best Separable State (BSS) problem of distinguishing, given an $n^2\times n^2$ matrix $M$ corresponding to a quantum measurement, between the case that there is a separable (i.e., non-entangled) state $\rho$ that $M$ accepts with probability $1$, ... more >>>


TR10-165 | 4th November 2010
Dmytro Gavinsky, Tsuyoshi Ito

Quantum Fingerprints that Keep Secrets

We introduce a new type of cryptographic primitive that we call hiding fingerprinting. No classical fingerprinting scheme is hiding. We construct quantum hiding fingerprinting schemes and argue their optimality.

more >>>

TR06-020 | 10th February 2006
Akinori Kawachi, Tomoyuki Yamakami

Quantum Hardcore Functions by Complexity-Theoretical Quantum List Decoding

Revisions: 1

We present three new quantum hardcore functions for any quantum one-way function. We also give a "quantum" solution to Damgard's question (CRYPTO'88) on his pseudorandom generator by proving the quantum hardcore property of his generator, which has been unknown to have the classical hardcore property.
Our technical tool is ... more >>>


TR19-041 | 7th March 2019
Srinivasan Arunachalam, Alex Bredariol Grilo, Aarthi Sundaram

Quantum hardness of learning shallow classical circuits

In this paper we study the quantum learnability of constant-depth classical circuits under the uniform distribution and in the distribution-independent framework of PAC learning. In order to attain our results, we establish connections between quantum learning and quantum-secure cryptosystems. We then achieve the following results.

1) Hardness of learning ... more >>>


TR20-066 | 28th April 2020
Scott Aaronson, Shalev Ben-David, Robin Kothari, Avishay Tal

Quantum Implications of Huang's Sensitivity Theorem

Based on the recent breakthrough of Huang (2019), we show that for any total Boolean function $f$, the deterministic query complexity, $D(f)$, is at most quartic in the quantum query complexity, $Q(f)$: $D(f) = O(Q(f)^4)$. This matches the known separation (up to log factors) due to Ambainis, Balodis, Belovs, Lee, ... more >>>


TR05-038 | 10th April 2005
Ran Raz

Quantum Information and the PCP Theorem

We show how to encode $2^n$ (classical) bits $a_1,...,a_{2^n}$
by a single quantum state $|\Psi \rangle$ of size $O(n)$ qubits,
such that:
for any constant $k$ and any $i_1,...,i_k \in \{1,...,2^n\}$,
the values of the bits $a_{i_1},...,a_{i_k}$ can be retrieved
from $|\Psi \rangle$ by a one-round Arthur-Merlin interactive ... more >>>


TR20-185 | 1st December 2020
Srinivasan Arunachalam, Alex Grilo, Tom Gur, Igor Oliveira, Aarthi Sundaram

Quantum learning algorithms imply circuit lower bounds

Revisions: 1

We establish the first general connection between the design of quantum algorithms and circuit lower bounds. Specifically, let $\mathrm{C}$ be a class of polynomial-size concepts, and suppose that $\mathrm{C}$ can be PAC-learned with membership queries under the uniform distribution with error $1/2 - \gamma$ by a time $T$ quantum algorithm. ... more >>>


TR23-173 | 15th November 2023
Louis Golowich, Venkatesan Guruswami

Quantum Locally Recoverable Codes

Classical locally recoverable codes, which permit highly efficient recovery from localized errors as well as global recovery from larger errors, provide some of the most useful codes for distributed data storage in practice. In this paper, we initiate the study of quantum locally recoverable codes (qLRCs). In the long ... more >>>


TR18-201 | 30th November 2018
Anurag Anshu, Naresh Boddu, Dave Touchette

Quantum Log-Approximate-Rank Conjecture is also False

Comments: 1

In a recent breakthrough result, Chattopadhyay, Mande and Sherif [ECCC TR18-17] showed an exponential separation between the log approximate rank and randomized communication complexity of a total function $f$, hence refuting the log approximate rank conjecture of Lee and Shraibman [2009]. We provide an alternate proof of their randomized communication ... more >>>


TR20-087 | 8th June 2020
Uma Girish, Ran Raz, Wei Zhan

Quantum Logspace Algorithm for Powering Matrices with Bounded Norm

Revisions: 2

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 poly(n)$ and outputs the entries of $A^T$, up to (arbitrary) polynomially small additive ... more >>>


TR23-107 | 20th July 2023
Uma Girish, Ran Raz, Wei Zhan

Quantum Logspace Computations are Verifiable

In this note, we observe that quantum logspace computations are verifiable by classical logspace algorithms, with unconditional security. More precisely, every language in 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 ... more >>>


TR18-087 | 20th April 2018
Kun He, Qian Li, Xiaoming Sun, Jiapeng Zhang

Quantum Lov{\'a}sz Local Lemma: Shearer's Bound is Tight

Lov{\'a}sz Local Lemma (LLL) is a very powerful tool in combinatorics and probability theory to show the possibility of avoiding all ``bad" events under some ``weakly dependent" condition. Over the last decades, the algorithmic aspect of LLL has also attracted lots of attention in theoretical computer science \cite{moser2010constructive, kolipaka2011moser, harvey2015algorithmic}. ... more >>>


TR18-137 | 7th August 2018
Scott Aaronson

Quantum Lower Bound for Approximate Counting Via Laurent Polynomials

We consider the following problem: estimate the size of a nonempty set $S\subseteq\left[ N\right] $, given both quantum queries to a membership oracle for $S$, and a device that generates equal superpositions $\left\vert S\right\rangle $ over $S$ elements. We show that, if $\left\vert S\right\vert $ is neither too large nor ... more >>>


TR14-109 | 14th August 2014
Aran Nayebi, Scott Aaronson, Aleksandrs Belovs, Luca Trevisan

Quantum lower bound for inverting a permutation with advice

Revisions: 1

Given a random permutation $f: [N] \to [N]$ as a black box and $y \in [N]$, we want to output $x = f^{-1}(y)$. Supplementary to our input, we are given classical advice in the form of a pre-computed data structure; this advice can depend on the permutation but \emph{not} on ... more >>>


TR02-072 | 12th November 2002
Scott Aaronson

Quantum Lower Bound for Recursive Fourier Sampling

We revisit the oft-neglected 'recursive Fourier sampling' (RFS) problem, introduced by Bernstein and Vazirani to prove an oracle separation between BPP and BQP. We show that the known quantum algorithm for RFS is essentially optimal, despite its seemingly wasteful need to uncompute information. This implies that, to place BQP outside ... more >>>


TR19-062 | 18th April 2019
Scott Aaronson, Robin Kothari, William Kretschmer, Justin Thaler

Quantum Lower Bounds for Approximate Counting via Laurent Polynomials

Revisions: 2

This paper proves new limitations on the power of quantum computers to solve approximate counting---that is, multiplicatively estimating the size of a nonempty set $S\subseteq [N]$.

Given only a membership oracle for $S$, it is well known that approximate counting takes $\Theta(\sqrt{N/|S|})$ quantum queries. But what if a quantum algorithm ... more >>>


TR96-003 | 4th December 1995
Alexei Kitaev

Quantum measurements and the Abelian Stabilizer Problem


We present a polynomial quantum algorithm for the Abelian stabilizer problem
which includes both factoring and the discrete logarithm. Thus we extend famous
Shor's results. Our method is based on a procedure for measuring an eigenvalue
of a unitary operator. Another application of this
procedure is a polynomial ... more >>>


TR21-116 | 10th August 2021
Nai-Hui Chia, Chi-Ning Chou, Jiayu Zhang, Ruizhe Zhang

Quantum Meets the Minimum Circuit Size Problem

Revisions: 1

In this work, we initiate the study of the Minimum Circuit Size Problem (MCSP) in the quantum setting. MCSP is a problem to compute the circuit complexity of Boolean functions. It is a fascinating problem in complexity theory---its hardness is mysterious, and a better understanding of its hardness can have ... more >>>


TR12-024 | 25th March 2012
Scott Aaronson, Paul Christiano

Quantum Money from Hidden Subspaces

Forty years ago, Wiesner pointed out that quantum mechanics raises the striking possibility of money that cannot be counterfeited according to the laws of physics. We propose the first quantum money scheme that is (1) public-key, meaning that anyone can verify a banknote as genuine, not only the bank that ... more >>>


TR14-151 | 13th November 2014
Debajyoti Bera

Quantum One-Sided Exact Error Algorithms

Revisions: 2

We define a complexity class for randomized algorithms with one-sided error that is exactly equal to a constant (unlike the usual definitions, in which the error is only bounded above or below by a constant). We show that the corresponding quantum classes (one each for a different error probability) are ... more >>>


TR10-143 | 19th September 2010
Bo'az Klartag, Oded Regev

Quantum One-Way Communication is Exponentially Stronger Than Classical Communication

In STOC 1999, Raz presented a (partial) function for which there is a quantum protocol
communicating only $O(\log n)$ qubits, but for which any classical (randomized, bounded-error) protocol requires $\poly(n)$ bits of communication. That quantum protocol requires two rounds of communication. Ever since Raz's paper it was open whether the ... more >>>


TR18-105 | 30th May 2018
Joseph Fitzsimons, Zhengfeng Ji, Thomas Vidick, Henry Yuen

Quantum proof systems for iterated exponential time, and beyond

We show that any language in nondeterministic time $\exp(\exp(\cdots\exp(n)))$, where the number of iterated exponentials is an arbitrary function $R(n)$, can be decided by a multiprover interactive proof system with a classical polynomial-time verifier and a constant number of quantum entangled provers, with completeness $1$ and soundness $1 - \exp(-C\exp(\cdots\exp(n)))$, ... more >>>


TR09-102 | 21st October 2009
Andrew Drucker, Ronald de Wolf

Quantum Proofs for Classical Theorems

Alongside the development of quantum algorithms and quantum complexity theory in recent years, quantum techniques have also proved instrumental in obtaining results in classical (non-quantum) areas. In this paper we survey these results and the quantum toolbox they use.

more >>>

TR21-068 | 8th May 2021
Marcel Dall'Agnol, Tom Gur, Subhayan Roy Moulik, Justin Thaler

Quantum Proofs of Proximity

We initiate the systematic study of QMA algorithms in the setting of property testing, to which we refer as QMA proofs of proximity (QMAPs). These are quantum query algorithms that receive explicit access to a sublinear-size untrusted proof and are required to accept inputs having a property $\Pi$ and reject ... more >>>


TR08-086 | 9th July 2008
Vikraman Arvind, Partha Mukhopadhyay

Quantum Query Complexity of Multilinear Identity Testing

Motivated by the quantum algorithm in \cite{MN05} for testing
commutativity of black-box groups, we study the following problem:
Given a black-box finite ring $R=\angle{r_1,\cdots,r_k}$ where
$\{r_1,r_2,\cdots,r_k\}$ is an additive generating set for $R$ and a
multilinear polynomial $f(x_1,\cdots,x_m)$ over $R$ also accessed as
a ... more >>>


TR19-136 | 23rd September 2019
Sourav Chakraborty, Arkadev Chattopadhyay, Nikhil Mande, Manaswi Paraashar

Quantum Query-to-Communication Simulation Needs a Logarithmic Overhead

Buhrman, Cleve and Wigderson (STOC'98) observed that for every Boolean function $f : \{-1, 1\}^n \to \{-1, 1\}$ and $\bullet : \{-1, 1\}^2 \to \{-1, 1\}$ the two-party bounded-error quantum communication complexity of $(f \circ \bullet)$ is $O(Q(f) \log n)$, where $Q(f)$ is the bounded-error quantum query complexity of $f$. ... more >>>


TR07-013 | 6th February 2007
Andris Ambainis, Joseph Emerson

Quantum t-designs: t-wise independence in the quantum world

A t-design for quantum states is a finite set of quantum states with the property of simulating the Haar-measure on quantum states w.r.t. any test that uses at most t copies of a state. We give efficient constructions for approximate quantum t-designs for arbitrary t.

We then show that an ... more >>>


TR22-029 | 27th February 2022
Anthony Leverrier, Gilles Zémor

Quantum Tanner codes

Revisions: 2

Tanner codes are long error correcting codes obtained from short codes and a graph, with bits on the edges and parity-check constraints from the short codes enforced at the vertices of the graph. Combining good short codes together with a spectral expander graph yields the celebrated expander codes of Sipser ... more >>>


TR24-011 | 24th January 2024
Paul Beame, Niels Kornerup

Quantum Time-Space Tradeoffs for Matrix Problems

Revisions: 1

We consider the time and space required for quantum computers to solve a wide variety of problems involving matrices, many of which have only been analyzed classically in prior work. Our main results show that for a range of linear algebra problems---including matrix-vector product, matrix inversion, matrix multiplication and powering---existing ... more >>>


TR06-055 | 10th April 2006
Scott Aaronson, Greg Kuperberg

Quantum Versus Classical Proofs and Advice

This paper studies whether quantum proofs are more powerful than
classical proofs, or in complexity terms, whether QMA=QCMA. We prove
two results about this question. First, we give a "quantum oracle
separation" between QMA and QCMA. More concretely, we show that any
quantum algorithm needs order sqrt(2^n/(m+1)) queries to find ... more >>>


TR22-177 | 7th December 2022
Vahid Reza Asadi, Alexander Golovnev, Tom Gur, Igor Shinkar, Sathyawageeswar Subramanian

Quantum Worst-Case to Average-Case Reductions for All Linear Problems

We study the problem of designing worst-case to average-case reductions for quantum algorithms. For all linear problems, we provide an explicit and efficient transformation of quantum algorithms that are only correct on a small (even sub-constant) fraction of their inputs into ones that are correct on all inputs. This stands ... more >>>


TR12-136 | 26th October 2012
Dan Boneh, Mark Zhandry

Quantum-Secure Message Authentication Codes

Revisions: 2

We construct the first Message Authentication Codes (MACs) that are existentially unforgeable against a quantum chosen message attack. These chosen message attacks model a quantum adversary’s ability to obtain the MAC on a superposition of messages of its choice. We begin by showing that a quantum secure PRF is sufficient ... more >>>


TR16-001 | 9th January 2016
Eli Ben-Sasson, Alessandro Chiesa, Ariel Gabizon, Madars Virza

Quasi-Linear Size Zero Knowledge from Linear-Algebraic PCPs

Revisions: 1

The seminal result that every language having an interactive proof also has a zero-knowledge interactive proof assumes the existence of one-way functions. Ostrovsky and Wigderson (ISTCS 1993) proved that this assumption is necessary: if one-way functions do not exist, then only languages in BPP have zero-knowledge interactive proofs.

Ben-Or et ... more >>>


TR17-135 | 10th September 2017
Ramprasad Saptharishi, Anamay Tengse

Quasi-polynomial Hitting Sets for Circuits with Restricted Parse Trees

Revisions: 1

We study the class of non-commutative Unambiguous circuits or Unique-Parse-Tree (UPT) circuits, and a related model of Few-Parse-Trees (FewPT) circuits (which were recently introduced by Lagarde, Malod and Perifel [LMP16] and Lagarde, Limaye and Srinivasan [LLS17]) and give the following constructions:
• An explicit hitting set of quasipolynomial size for ... more >>>


TR12-113 | 7th September 2012
Manindra Agrawal, Chandan Saha, Nitin Saxena

Quasi-polynomial Hitting-set for Set-depth-$\Delta$ Formulas

We call a depth-$4$ formula $C$ $\textit{ set-depth-4}$ if there exists a (unknown) partition $X_1\sqcup\cdots\sqcup X_d$ of the variable indices $[n]$ that the top product layer respects, i.e. $C(\mathbf{x})=\sum_{i=1}^k {\prod_{j=1}^{d} {f_{i,j}(\mathbf{x}_{X_j})}}$ $ ,$ where $f_{i,j}$ is a $\textit{sparse}$ polynomial in $\mathbb{F}[\mathbf{x}_{X_j}]$. Extending this definition to any depth - we call ... more >>>


TR19-090 | 27th June 2019
Ronen Shaltiel, Swastik Kopparty, Jad Silbak

Quasilinear time list-decodable codes for space bounded channels

Revisions: 2

We consider codes for space bounded channels. This is a model for communication under noise that was studied by Guruswami and Smith (J. ACM 2016) and lies between the Shannon (random) and Hamming (adversarial) models. In this model, a channel is a space bounded procedure that reads the codeword in ... more >>>


TR12-115 | 11th September 2012
Michael Forbes, Amir Shpilka

Quasipolynomial-time Identity Testing of Non-Commutative and Read-Once Oblivious Algebraic Branching Programs

Revisions: 1

We study the problem of obtaining efficient, deterministic, black-box polynomial identity testing (PIT) algorithms for read-once oblivious algebraic branching programs (ABPs). This class has an efficient, deterministic, white-box polynomial identity testing algorithm (due to Raz and Shpilka), but prior to this work had no known such black-box algorithm. Here we ... more >>>


TR22-091 | 2nd July 2022
Harm Derksen, Emanuele Viola

Quasirandom groups enjoy interleaved mixing

Let $G$ be a group such that any non-trivial representation has dimension
at least $d$. Let $X=(X_{1},X_{2},\ldots,X_{t})$ and $Y=(Y_{1},Y_{2},\ldots,Y_{t})$
be distributions over $G^{t}$. Suppose that $X$ is independent from
$Y$. We show that for any $g\in G$ we have
\[
\left|\mathbb{P}[X_{1}Y_{1}X_{2}Y_{2}\cdots X_{t}Y_{t}=g]-1/|G|\right|\le\frac{|G|^{2t-1}}{d^{t-1}}\sqrt{\mathbb{E}_{h\in G^{t}}X(h)^{2}}\sqrt{\mathbb{E}_{h\in G^{t}}Y(h)^{2}}.
\]
Our results generalize, improve, and ... more >>>


TR12-002 | 4th January 2012
Akinori Kawachi, Benjamin Rossman, Osamu Watanabe

Query Complexity and Error Tolerance of Witness Finding Algorithms

Revisions: 3

We propose an abstract framework for studying search-to-decision reductions for NP. Specifically, we study the following witness finding problem: for a hidden nonempty set $W\subseteq\{0,1\}^n$, the goal is to output a witness in $W$ with constant probability by making randomized queries of the form ``is $Q\cap W$ nonempty?''\ where $Q\subseteq\{0,1\}^n$. ... more >>>


TR10-126 | 12th August 2010
Thomas Watson

Query Complexity in Errorless Hardness Amplification

Revisions: 2

An errorless circuit for a boolean function is one that outputs the correct answer or ``don't know'' on each input (and never outputs the wrong answer). The goal of errorless hardness amplification is to show that if $f$ has no size $s$ errorless circuit that outputs ``don't know'' on at ... more >>>


TR20-133 | 8th September 2020
Noga Ron-Zewi, Ronen Shaltiel, Nithin Varma

Query complexity lower bounds for local list-decoding and hard-core predicates (even for small rate and huge lists)

A binary code $\text{Enc}:\{0,1\}^k \rightarrow \{0,1\}^n$ is $(\frac{1}{2}-\varepsilon,L)$-list decodable if for every $w \in \{0,1\}^n$, there exists a set $\text{List}(w)$ of size at most $L$, containing all messages $m \in \{0,1\}^k$ such that the relative Hamming distance between $\text{Enc}(m)$ and $w$ is at most $\frac{1}{2}-\varepsilon$.
A $q$-query local list-decoder is ... more >>>


TR10-067 | 14th April 2010
Sourav Chakraborty, Eldar Fischer, Arie Matsliah

Query Complexity Lower Bounds for Reconstruction of Codes

We investigate the problem of {\em local reconstruction}, as defined by Saks and Seshadhri (2008), in the context of error correcting codes.

The first problem we address is that of {\em message reconstruction}, where given oracle access to a corrupted encoding $w \in \zo^n$ of some message $x \in \zo^k$ ... more >>>


TR20-108 | 19th July 2020
Arijit Bishnu, Arijit Ghosh, Gopinath Mishra, Manaswi Paraashar

Query Complexity of Global Minimum Cut

Revisions: 1

In this work, we resolve the query complexity of global minimum cut problem for a graph by designing a randomized algorithm for approximating the size of minimum cut in a graph, where the graph can be accessed through local queries like \textsc{Degree}, \textsc{Neighbor}, and \textsc{Adjacency} queries.

Given $\epsilon \in (0,1)$, ... more >>>


TR22-158 | 18th November 2022
Ivan Hu, Andrew Morgan, Dieter van Melkebeek

Query Complexity of Inversion Minimization on Trees

Revisions: 1

We consider the following computational problem: Given a rooted tree and a ranking of its leaves, what is the minimum number of inversions of the leaves that can be attained by ordering the tree? This variation of the well-known problem of counting inversions in arrays originated in mathematical psychology. It ... more >>>


TR12-063 | 17th May 2012
Raghav Kulkarni, Miklos Santha

Query complexity of matroids

Let $\mathcal{M}$ be a bridgeless matroid on ground set $\{1,\ldots, n\}$ and $f_{\mathcal{M}}: \{0,1\}^n \to \{0, 1\}$ be the indicator function of its independent sets. A folklore fact is that $f_\mathcal{M}$ is ``evasive," i.e., $D(f_\mathcal{M}) = n$ where $D(f)$ denotes the deterministic decision tree complexity of $f.$ Here we prove ... more >>>


TR23-039 | 28th March 2023
Arkadev Chattopadhyay, Yogesh Dahiya, Meena Mahajan

Query Complexity of Search Problems

Revisions: 1

We relate various complexity measures like sensitivity, block sensitivity, certificate complexity for multi-output functions to the query complexities of such functions. Using these relations, we improve upon the known relationship between pseudo-deterministic query complexity and deterministic query complexity for total search problems: We show that pseudo-deterministic query complexity is at ... more >>>


TR10-173 | 9th November 2010
Yeow Meng Chee, Tao Feng, San Ling, Huaxiong Wang, Liang Feng Zhang

Query-Efficient Locally Decodable Codes

A $k$-query locally decodable code (LDC)
$\textbf{C}:\Sigma^{n}\rightarrow \Gamma^{N}$ encodes each message $x$ into
a codeword $\textbf{C}(x)$ such that each symbol of $x$ can be probabilistically
recovered by querying only $k$ coordinates of $\textbf{C}(x)$, even after a
constant fraction of the coordinates have been corrupted.
Yekhanin (2008)
constructed a $3$-query LDC ... more >>>


TR17-053 | 22nd March 2017
Mika Göös, Toniann Pitassi, Thomas Watson

Query-to-Communication Lifting for BPP

Revisions: 1

For any $n$-bit boolean function $f$, we show that the randomized communication complexity of the composed function $f\circ g^n$, where $g$ is an index gadget, is characterized by the randomized decision tree complexity of $f$. In particular, this means that many query complexity separations involving randomized models (e.g., classical vs.\ ... more >>>


TR17-024 | 16th February 2017
Mika Göös, Pritish Kamath, Toniann Pitassi, Thomas Watson

Query-to-Communication Lifting for P^NP

Revisions: 1

We prove that the $\text{P}^{\small\text{NP}}$-type query complexity (alternatively, decision list width) of any boolean function $f$ is quadratically related to the $\text{P}^{\small\text{NP}}$-type communication complexity of a lifted version of $f$. As an application, we show that a certain "product" lower bound method of Impagliazzo and Williams (CCC 2010) fails to ... more >>>


TR19-103 | 7th August 2019
Arkadev Chattopadhyay, Yuval Filmus, Sajin Koroth, Or Meir, Toniann Pitassi

Query-to-Communication Lifting Using Low-Discrepancy Gadgets

Revisions: 2

Lifting theorems are theorems that relate the query complexity of a function $f:\left\{ 0,1 \right\}^n\to \left\{ 0,1 \right\}$ to the communication complexity of the composed function $f\circ g^n$, for some “gadget” $g:\left\{ 0,1 \right\}^b\times \left\{ 0,1 \right\}^b\to \left\{ 0,1 \right\}$. Such theorems allow transferring lower bounds from query complexity to ... more >>>




ISSN 1433-8092 | Imprint