相关参考文献
注意:仅列出部分参考文献,下载原文获取全部文献信息。Algorithmic Polynomials
Alexander A. Sherstov
STOC'18: PROCEEDINGS OF THE 50TH ANNUAL ACM SIGACT SYMPOSIUM ON THEORY OF COMPUTING (2018)
The Polynomial Method Strikes Back: Tight Quantum Query Bounds via Dual Polynomials
Mark Bun et al.
STOC'18: PROCEEDINGS OF THE 50TH ANNUAL ACM SIGACT SYMPOSIUM ON THEORY OF COMPUTING (2018)
Formula Lower Bounds via the Quantum Method
Avishay Tal
STOC'17: PROCEEDINGS OF THE 49TH ANNUAL ACM SIGACT SYMPOSIUM ON THEORY OF COMPUTING (2017)
A Nearly Optimal Lower Bound on the Approximate Degree of AC0
Mark Bun et al.
2017 IEEE 58TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS) (2017)
The Complexity of DNF of Parities
Gil Cohen et al.
ITCS'16: PROCEEDINGS OF THE 2016 ACM CONFERENCE ON INNOVATIONS IN THEORETICAL COMPUTER SCIENCE (2016)
The Power of Asymmetry in Constant-Depth Circuits
Alexander A. Sherstov
2015 IEEE 56TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (2015)
THE INTERSECTION OF TWO HALFSPACES HAS HIGH THRESHOLD DEGREE
Alexander A. Sherstov
SIAM JOURNAL ON COMPUTING (2013)
Constructing hard functions from learning algorithms
Adam Klivans et al.
2013 IEEE CONFERENCE ON COMPUTATIONAL COMPLEXITY (CCC) (2013)
THE PATTERN MATRIX METHOD
Alexander A. Sherstov
SIAM JOURNAL ON COMPUTING (2011)
ANY AND-OR FORMULA OF SIZE N CAN BE EVALUATED IN TIME N1/2+o(1) ON A QUANTUM COMPUTER
A. Ambainis et al.
SIAM JOURNAL ON COMPUTING (2010)
THE SIGN-RANK OF AC(0)
Alexander A. Razborov et al.
SIAM JOURNAL ON COMPUTING (2010)
Circuit Complexity of Regular Languages
Michal Koucky
THEORY OF COMPUTING SYSTEMS (2009)
Agnostically learning halfspaces
Adam Tauman Kalai et al.
SIAM JOURNAL ON COMPUTING (2008)
Robust polynomials and quantum algorithms
Harry Buhrman et al.
THEORY OF COMPUTING SYSTEMS (2007)
Learning DNF in time 2(0)over-tilde(n1/3)
AR Klivans et al.
JOURNAL OF COMPUTER AND SYSTEM SCIENCES (2004)
Complexity measures and decision tree complexity: a survey
H Buhrman et al.
THEORETICAL COMPUTER SCIENCE (2002)
Quantum lower bounds by polynomials
R Beals et al.
JOURNAL OF THE ACM (2001)