×

Found 23 Documents (Results 1–23)

\(\mathrm{AC}^0[p]\) lower bounds against MCSP via the coin problem. (English) Zbl 1524.68133

Baier, Christel (ed.) et al., 46th international colloquium on automata, languages, and programming, ICALP 2019, Patras, Greece, July 9–12, 2019. Proceedings. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 132, Article 66, 15 p. (2019).
MSC:  68Q06 68Q17
PDFBibTeX XMLCite
Full Text: DOI

Circuit lower bounds for MCSP from local pseudorandom generators. (English) Zbl 1499.68101

Baier, Christel (ed.) et al., 46th international colloquium on automata, languages, and programming, ICALP 2019, Patras, Greece, July 9–12, 2019. Proceedings. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 132, Article 39, 14 p. (2019).
MSC:  68Q06 68Q17
PDFBibTeX XMLCite
Full Text: DOI

The power of natural properties as oracles. (English) Zbl 1441.68060

Servedio, Rocco A. (ed.), 33rd computational complexity conference, CCC 2018, June 22–24, 2018, San Diego, California, USA. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 102, Article 7, 20 p. (2018).
PDFBibTeX XMLCite
Full Text: DOI

Agnostic learning from tolerant natural proofs. (English) Zbl 1467.68076

Jansen, Klaus (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques. 20th international workshop, APPROX 2017 and 21st international workshop, RANDOM 2017, Berkeley, CA, USA, August 16–18, 2017. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 81, Article 35, 19 p. (2017).
MSC:  68Q32 68Q06 68Q17
PDFBibTeX XMLCite
Full Text: DOI

Learning algorithms from natural proofs. (English) Zbl 1380.68242

Raz, Ran (ed.), 31st conference on computational complexity, CCC’16, Tokyo, Japan, May 29 – June 1, 2016. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-95977-008-8). LIPIcs – Leibniz International Proceedings in Informatics 50, Article 10, 24 p. (2016).
MSC:  68Q32 68Q05 68Q15 68Q17
PDFBibTeX XMLCite
Full Text: DOI

Pseudorandomness when the odds are against you. (English) Zbl 1380.68434

Raz, Ran (ed.), 31st conference on computational complexity, CCC’16, Tokyo, Japan, May 29 – June 1, 2016. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-95977-008-8). LIPIcs – Leibniz International Proceedings in Informatics 50, Article 9, 35 p. (2016).
MSC:  68W20 68Q17 68Q25
PDFBibTeX XMLCite
Full Text: DOI

The minimum oracle circuit size problem. (English) Zbl 1355.68104

Mayr, Ernst W. (ed.) et al., 32nd international symposium on theoretical aspects of computer science, STACS’15, Garching, Germany, March 4–7, 2015. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-939897-78-1). LIPIcs – Leibniz International Proceedings in Informatics 30, 21-33 (2015).
MSC:  68Q17 68Q30
PDFBibTeX XMLCite
Full Text: DOI

Lower bounds against weakly uniform circuits. (English) Zbl 1364.68217

Gudmundsson, Joachim (ed.) et al., Computing and combinatorics. 18th annual international conference, COCOON 2012, Sydney, Australia, August 20–22, 2012. Proceedings. Berlin: Springer (ISBN 978-3-642-32240-2/pbk). Lecture Notes in Computer Science 7434, 408-419 (2012).
MSC:  68Q17 68Q05 68Q15 94C10
PDFBibTeX XMLCite
Full Text: DOI

Circuit minimization problem. (English) Zbl 1296.94182

Proceedings of the thirty-second annual ACM symposium on theory of computing (STOC 2000), Portland, Oregon, USA, May 21–23, 2000. New York, NY: ACM Press (ISBN 1-58113-184-4). 73-79 (2000).
MSC:  94C10 68Q15 68Q17 68Q25
PDFBibTeX XMLCite
Full Text: DOI

Filter Results by …

Document Type

all top 5

Year of Publication

all top 3

Main Field