×

Found 34 Documents (Results 1–34)

100
MathJax

Oracle separation of BQP and PH. (English) Zbl 1433.68152

Charikar, Moses (ed.) et al., Proceedings of the 51st annual ACM SIGACT symposium on theory of computing, STOC ’19, Phoenix, AZ, USA, June 23–26, 2019. New York, NY: Association for Computing Machinery (ACM). 13-23 (2019).
MSC:  68Q15 68Q06 68Q12
PDF BibTeX XML Cite
Full Text: DOI

Tight bounds on the Fourier spectrum of \(\mathsf{AC}^0\). (English) Zbl 1440.68084

O’Donnell, Ryan (ed.), 32nd computational complexity conference, CCC 2017, July 6–9, 2017, Riga, Latvia. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 79, Article 15, 31 p. (2017).
MSC:  68Q06 68Q15 94C11
PDF BibTeX XML Cite
Full Text: DOI

Two sides of the coin problem. (English) Zbl 1360.68460

Jansen, Klaus (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques. Proceedings of the 17th international workshop on approximation algorithms for combinatorial optimization problems (APPROX 2014) and the 18th international workshop on randomization and computation (RANDOM 2014), Universitat Politècnica de Catalunya, Barcelona, Spain, September 4–6, 2014. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-939897-74-3). LIPIcs – Leibniz International Proceedings in Informatics 28, 618-629 (2014).
MSC:  68Q05 68Q17 68Q87
PDF BibTeX XML Cite
Full Text: DOI

Tight bounds on computing error-correcting codes by bounded-depth circuits with arbitrary gates. (English) Zbl 1286.94108

Karloff, Howard J. (ed.) et al., Proceedings of the 44th annual ACM symposium on theory of computing, STOC 2012. New York, NY, USA, May 19–22, 2012. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-1245-5). 479-494 (2012).
MSC:  94B25 94C15
PDF BibTeX XML Cite
Full Text: DOI Link

Black-box identity testing of depth-4 multilinear circuits. (English) Zbl 1288.68137

Proceedings of the 43rd annual ACM symposium on theory of computing, STOC ’11. San Jose, CA, USA, June 6–8, 2011. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-0691-1). 421-430 (2011).
MSC:  68Q25 12Y05 94C10
PDF BibTeX XML Cite
Full Text: DOI

Deterministic identity testing of depth-\(4\) multilinear circuits with bounded top fan-in. (English) Zbl 1293.90040

Proceedings of the 42nd annual ACM symposium on theory of computing, STOC ’10. Cambridge, MA, USA, June 5–8, 2010. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-60558-817-9). 649-658 (2010).
MSC:  90C05
PDF BibTeX XML Cite
Full Text: DOI

The polynomial and linear hierarchies in \(\text{V}^{0}\). (English) Zbl 1151.03350

Cooper, S. Barry (ed.) et al., Computation and logic in the real world. Third conference on computability in Europe, CiE 2007, Siena, Italy, June 18–23, 2007. Proceedings. Berlin: Springer (ISBN 978-3-540-73000-2/pbk). Lecture Notes in Computer Science 4497, 408-415 (2007).
MSC:  03F30 68Q15 94C10
PDF BibTeX XML Cite
Full Text: DOI

Filter Results by …

Document Type

all top 5

Year of Publication

all top 3

Classification