Fetching the paper…
Reading the bibliography…
We give new quantum algorithms for evaluating composed functions whose inputs may be shared between bottom-level gates.
A theory of the learnable
Leslie G. Valiant · 1972
Earlier work this paper cites.
A theorem on probabilistic constant depth computations
Miklos Ajtai and Michael Ben-Or · 1984
Earlier work this paper cites.
Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
Alexander A Razborov · 1987
Earlier work this paper cites.
Linear-size constant-depth polylog-threshold circuits
Prabhakar Ragde and Avi Wigderson · 1991
Earlier work this paper cites.
Polynomial threshold functions, AC 0 functions, and spectral norms
Jehoshua Bruck and Roman Smolensky · 1992
Earlier work this paper cites.
Toward efficient agnostic learning
Michael J. Kearns, Robert E. Schapire, and Linda M. Sellie · 1994
Earlier work this paper cites.
On the degree of Boolean functions as real polynomials
Noam Nisan and Mario Szegedy · 1994
Earlier work this paper cites.
On efficient agnostic learning of linear combinations of basis functions
Wee Sun Lee, Peter L. Bartlett, and Robert C. Williamson · 1995
Earlier work this paper cites.
Deterministic restrictions in circuit complexity
Shiva Chaudhuri and Jaikumar Radhakrishnan · 1996
Earlier work this paper cites.
A fast quantum mechanical algorithm for database search
Lov K. Grover · 1996
Earlier work this paper cites.
Strengths and weaknesses of quantum computing
Charles H. Bennett, Ethan Bernstein, Gilles Brassard, and Umesh Vazirani · 1997
Earlier work this paper cites.
Tight bounds on quantum searching
Michel Boyer, Gilles Brassard, Peter Høyer, and Alain Tapp · 1998
Earlier work this paper cites.
Bounds for small-error and zero-error quantum algorithms
Harry Buhrman, Richard Cleve, Ronald de Wolf, and Christof Zalka · 1999
Earlier work this paper cites.
Quantum lower bounds by polynomials
Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, and Ronald de Wolf · 2001
Earlier work this paper cites.
Complexity measures and decision tree complexity: a survey
Harry Buhrman and Ronald de Wolf · 2002
Earlier work this paper cites.
Learning DNF in time 2 O ~ ( n 1 / 3 ) 2^{{\tilde{O}}(n^{1/3})}
Adam R. Klivans and Rocco A. Servedio · 2003
Earlier work this paper cites.
Circuit lower bounds via Ehrenfeucht-Fraisse games
Michal Koucký, Clemens Lautemann, Sebastian Poloczek, and Denis Therien · 2006
Earlier work this paper cites.
Robust polynomials and quantum algorithms
Harry Buhrman, Ilan Newman, Hein Röhrig, and Ronald de Wolf · 2007
Earlier work this paper cites.
Negative weights make adversaries stronger
Peter Høyer, Troy Lee, and Robert Špalek · 2007
Earlier work this paper cites.
A quantum algorithm for the Hamiltonian NAND tree
Edward Farhi, Jeffrey Goldstone, and Sam Gutmann · 2008
Earlier work this paper cites.
Agnostically learning halfspaces
Adam Tauman Kalai, Adam R. Klivans, Yishay Mansour, and Rocco A. Servedio · 2008
Cited alongside, same era.
Discrete-query quantum algorithm for NAND trees
Andrew M. Childs, Richard Cleve, Stephen P. Jordan, and David Yonge-Mallo · 2009
Cited alongside, same era.
The complexity of satisfiability of small depth circuits
Chris Calabro, Russell Impagliazzo, and Ramamohan Paturi · 2009
Cited alongside, same era.
Circuit complexity of regular languages
Michal Koucký · 2009
Cited alongside, same era.
Lower bounds in communication complexity
Troy Lee and Adi Shraibman · 2009
Cited alongside, same era.
Any AND-OR formula of size N N can be evaluated in time N 1 / 2 + o ( 1 ) N^{1/2+o(1)} on a quantum computer
Andris Ambainis, Andrew M. Childs, Ben W. Reichardt, Robert Špalek, and Shengyu Zhang · 2010
Cited alongside, same era.
Making polynomials robust to noise
Alexander A. Sherstov · 2013
Later among the works it cites.
Candidate weak pseudorandom functions in AC 0 ∘ 𝖬𝖮𝖣 2 {}^{0}\circ\mathsf{MOD}_{2}
Adi Akavia, Andrej Bogdanov, Siyao Guo, Akshay Kamath, and Alon Rosen · 2014
Later among the works it cites.
Real analysis in computer science: A collection of open problems, 2014
Yuval Filmus, Hamed Hatami, Steven Heilman, Elchanan Mossel, Ryan O’Donnell, Sushant Sachdeva, Andrew Wan, and Karl Wimmer · 2014
Later among the works it cites.
The power of asymmetry in constant-depth circuits
Alexander A. Sherstov · 2015
Later among the works it cites.
AC 0 ∘ \circ MOD 2 lower bounds for the Boolean inner product
Mahdi Cheraghchi, Elena Grigorescu, Brendan Juba, Karl Wimmer, and Ning Xie · 2016
Later among the works it cites.
The complexity of DNF of parities
Gil Cohen and Igor Shinkar · 2016
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
The sign-rank of AC 0
Alexander A. Razborov and Alexander A. Sherstov · 2010
Cited alongside, same era.
Shortest formula for an n n -term monotone CNF
Noam Nisan · 2011
Cited alongside, same era.
Reflections for quantum query algorithms
Ben Reichardt · 2011
Cited alongside, same era.
The pattern matrix method
Alexander A. Sherstov · 2011
Cited alongside, same era.
Strong direct product theorems for quantum communication and query complexity
Alexander A. Sherstov · 2011
Cited alongside, same era.
The quantum query complexity of AC 0
Paul Beame and Widad Machmouchi · 2012
Cited alongside, same era.
The bipartite formula complexity of inner-product is quadratic
Avishay Tal · 2016
Later among the works it cites.
On the power of statistical zero knowledge
Adam Bouland, Lijie Chen, Dhiraj Holden, Justin Thaler, and Prashant Nalini Vasudevan · 2017
Later among the works it cites.
A nearly optimal lower bound on the approximate degree of AC 0
Mark Bun and Justin Thaler · 2017
Later among the works it cites.
PAC learning depth-3 AC 0 \textrm{AC}^{0} circuits of bounded top fanin
Ning Ding, Yanli Ren, and Dawu Gu · 2017
Later among the works it cites.
Conspiracies Between Learning Algorithms, Circuit Lower Bounds, and Pseudorandomness
Igor C. Carboni Oliveira and Rahul Santhanam · 2017
Later among the works it cites.
What Circuit Classes Can Be Learned with Non-Trivial Savings?
Rocco A. Servedio and Li-Yang Tan · 2017
Later among the works it cites.
Formula lower bounds via the quantum method
Avishay Tal · 2017
Later among the works it cites.
The polynomial method strikes back: Tight quantum query bounds via dual polynomials
Mark Bun, Robin Kothari, and Justin Thaler · 2018
Closest in time.
Algorithmic polynomials
Alexander A. Sherstov · 2018
Closest in time.
Personal communication, 2018
Avishay Tal · 2018
Closest in time.
Quantum algorithms and approximating polynomials for composed functions with shared inputs
Mark Bun, Robin Kothari, and Justin Thaler · 2019
Closest in time.
Guest column: Approximate degree in classical and quantum computing
Mark Bun and Justin Thaler · 2021
Closest in time.
Small circuits imply efficient Arthur-Merlin protocols
Michael Ezra and Ron D. Rothblum · 2021
Closest in time.