Articles under category:
Note
Note
Vol 18, Article 17 (pp 1-11)
[NOTE]
A Stochastic Calculus Approach to the Oracle Separation of $\mathsf{BQP}$ and $\mathsf{PH}$
by Xinyu Wu
A Stochastic Calculus Approach to the Oracle Separation of $\mathsf{BQP}$ and $\mathsf{PH}$
by Xinyu Wu
Vol 16, Article 14 (pp 1-8)
[NOTE]
On the Hardness of Approximating the $k$-Way Hypergraph Cut problem
by Chandra Chekuri and Shi Li
On the Hardness of Approximating the $k$-Way Hypergraph Cut problem
by Chandra Chekuri and Shi Li
Vol 16, Article 11 (pp 1-8)
[NOTE]
On the Classical Hardness of Spoofing Linear Cross-Entropy Benchmarking
by Scott Aaronson and Sam Gunn
On the Classical Hardness of Spoofing Linear Cross-Entropy Benchmarking
by Scott Aaronson and Sam Gunn
Vol 15, Article 8 (pp 1-7)
[NOTE]
Matrix Rigidity and the Croot-Lev-Pach Lemma
by Zeev Dvir and Benjamin L. Edelman
Matrix Rigidity and the Croot-Lev-Pach Lemma
by Zeev Dvir and Benjamin L. Edelman
Vol 12, Article 6 (pp 1-11)
[NOTE]
Simple Proof of Hardness of Feedback Vertex Set
by Venkatesan Guruswami and Euiwoong Lee
Simple Proof of Hardness of Feedback Vertex Set
by Venkatesan Guruswami and Euiwoong Lee
Vol 11, Article 16 (pp 403-412)
[NOTE]
Quantum Algorithm for Monotonicity Testing on the Hypercube
by Aleksandrs Belovs and Eric Blais
Quantum Algorithm for Monotonicity Testing on the Hypercube
by Aleksandrs Belovs and Eric Blais
Vol 11, Article 15 (pp 395-401)
[NOTE]
Groups with Identical $k$-Profiles
by George Glauberman and Łukasz Grabowski
Groups with Identical $k$-Profiles
by George Glauberman and Łukasz Grabowski
Vol 9, Article 29 (pp 889-896)
[NOTE]
[Boolean Spec Issue]
Hypercontractivity Via the Entropy Method
by Eric Blais and Li-Yang Tan
Hypercontractivity Via the Entropy Method
by Eric Blais and Li-Yang Tan
Vol 9, Article 17 (pp 587-592)
[NOTE]
[Boolean Spec Issue]
A Monotone Function Given By a Low-Depth Decision Tree That Is Not an Approximate Junta
by Daniel Kane
A Monotone Function Given By a Low-Depth Decision Tree That Is Not an Approximate Junta
by Daniel Kane
Vol 9, Article 6 (pp 273-282)
[NOTE]
The Complexity of the Fermionant and Immanants of Constant Width
by Stephan Mertens and Cristopher Moore
The Complexity of the Fermionant and Immanants of Constant Width
by Stephan Mertens and Cristopher Moore
Vol 8, Article 16 (pp 369-374)
[NOTE]
Quantum Private Information Retrieval with Sublinear Communication Complexity
by François Le Gall
Quantum Private Information Retrieval with Sublinear Communication Complexity
by François Le Gall
Vol 8, Article 10 (pp 231-238)
[NOTE]
Monotone Circuits: One-Way Functions versus Pseudorandom Generators
by Oded Goldreich and Rani Izsak
Monotone Circuits: One-Way Functions versus Pseudorandom Generators
by Oded Goldreich and Rani Izsak
Vol 7, Article 13 (pp 185-188)
[NOTE]
Computing Polynomials with Few Multiplications
by Shachar Lovett
Computing Polynomials with Few Multiplications
by Shachar Lovett
Vol 7, Article 12 (pp 177-184)
[NOTE]
On Circuit Lower Bounds from Derandomization
by Scott Aaronson and Dieter van Melkebeek
On Circuit Lower Bounds from Derandomization
by Scott Aaronson and Dieter van Melkebeek
Vol 7, Article 10 (pp 147-153)
[NOTE]
The Influence Lower Bound Via Query Elimination
by Rahul Jain and Shengyu Zhang
The Influence Lower Bound Via Query Elimination
by Rahul Jain and Shengyu Zhang
Vol 7, Article 4 (pp 45-48)
[NOTE]
Tight Bounds on the Average Sensitivity of k-CNF
by Kazuyuki Amano
Tight Bounds on the Average Sensitivity of k-CNF
by Kazuyuki Amano
Vol 7, Article 2 (pp 19-25)
[NOTE]
Inverting a Permutation is as Hard as Unordered Search
by Ashwin Nayak
Inverting a Permutation is as Hard as Unordered Search
by Ashwin Nayak
Vol 6, Article 4 (pp 81-84)
[NOTE]
Decision Trees and Influence: an Inductive Proof of the OSSS Inequality
by Homin K. Lee
Decision Trees and Influence: an Inductive Proof of the OSSS Inequality
by Homin K. Lee
Vol 5, Article 5 (pp 119-123)
[NOTE]
Discrete-Query Quantum Algorithm for NAND Trees
by Andrew M. Childs, Richard Cleve, Stephen P. Jordan, and David Yonge-Mallo
Discrete-Query Quantum Algorithm for NAND Trees
by Andrew M. Childs, Richard Cleve, Stephen P. Jordan, and David Yonge-Mallo