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 |
|
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 |
|
Vol 16, Article 11 (pp 1-8)
[NOTE]
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 |
|
Vol 12, Article 6 (pp 1-11)
[NOTE]
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 |
|
Vol 11, Article 15 (pp 395-401)
[NOTE]
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 |
|
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 |
|
Vol 9, Article 6 (pp 273-282)
[NOTE]
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 |
|
Vol 8, Article 10 (pp 231-238)
[NOTE]
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 |
|
Vol 7, Article 12 (pp 177-184)
[NOTE]
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 |
|
Vol 7, Article 4 (pp 45-48)
[NOTE]
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 |
|
Vol 6, Article 4 (pp 81-84)
[NOTE]
Decision Trees and Influence: an Inductive Proof of the OSSS Inequality by Homin K. Lee |
|
Vol 5, Article 7 (pp 135-140)
[NOTE]
A Simple Proof of Toda's Theorem by Lance Fortnow |
|
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 |