×

Found 61 Documents (Results 1–61)

Parameterized complexity classes defined by threshold circuits: using sorting networks to show collapses with W-hierarchy classes. (English) Zbl 07550536

Du, Ding-Zhu (ed.) et al., Combinatorial optimization and applications. 15th international conference, COCOA 2021, Tianjin, China, December 17–19, 2021. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 13135, 348-363 (2021).
MSC:  68T20 90C27
PDFBibTeX XMLCite
Full Text: DOI

Size, depth and energy of threshold circuits computing parity function. (English) Zbl 07765412

Cao, Yixin (ed.) et al., 31st international symposium on algorithms and computation, ISAAC 2020, Hong Kong, China, virtual conference, December 14–18, 2020. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 181, Article 54, 13 p. (2020).
MSC:  68Wxx
PDFBibTeX XMLCite
Full Text: DOI

String matching: communication, circuits, and learning. (English) Zbl 07650123

Achlioptas, Dimitris (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques, 22nd international conference, APPROX 2019, and 23rd international conference, RANDOM 2019, Massachusetts Institute of Technology, Cambridge, MA, USA, September 20–22, 2019. Proceedings. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 145, Article 56, 20 p. (2019).
MSC:  68W20 68W25 90C27
PDFBibTeX XMLCite
Full Text: DOI arXiv

Stronger connections between circuit analysis and circuit lower bounds, via PCPs of proximity. (English) Zbl 07564419

Shpilka, Amir (ed.), 34th computational complexity conference, CCC 2019, New Brunswick, NJ, USA, July 18–20, 2019. Proceedings. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 137, Article 19, 43 p. (2019).
MSC:  68Q25
PDFBibTeX XMLCite
Full Text: DOI

Expander-based cryptography meets natural proofs. (English) Zbl 07559061

Blum, Avrim (ed.), 10th innovations in theoretical computer science conference, ITCS 2019, January 10–12, 2019, San Diego, CA, USA. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 124, Article 18, 14 p. (2019).
MSC:  68Qxx
PDFBibTeX XMLCite
Full Text: DOI

Approximate degree and the complexity of depth three circuits. (English) Zbl 1522.68195

Blais, Eric (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques. 21st international workshop, APPROX 2018, and 22nd international workshop, RANDOM 2018 August 20–22, 2018, Princeton, USA. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 116, Article 35, 18 p. (2018).
MSC:  68Q06
PDFBibTeX XMLCite
Full Text: DOI

Local reductions. (English) Zbl 1394.68183

Halldórsson, Magnús M. (ed.) et al., Automata, languages, and programming. 42nd international colloquium, ICALP 2015, Kyoto, Japan, July 6–10, 2015. Proceedings. Part I. Berlin: Springer (ISBN 978-3-662-47671-0/pbk; 978-3-662-47672-7/ebook). Lecture Notes in Computer Science 9134, 749-760 (2015).
MSC:  68Q25 68Q15
PDFBibTeX XMLCite
Full Text: DOI arXiv

Randomized OBDDs for the most significant bit of multiplication need exponential size. (English) Zbl 1298.68109

Černá, Ivana (ed.) et al., SOFSEM 2011: Theory and practice of computer science. 37th conference on current trends in theory and practice of computer science, Nový Smokovec, Slovakia, January 22–28, 2011. Proceedings. Berlin: Springer (ISBN 978-3-642-18380-5/pbk). Lecture Notes in Computer Science 6543, 135-145 (2011).
MSC:  68Q25 68P05
PDFBibTeX XMLCite
Full Text: DOI

A small decrease in the degree of a polynomial with a given sign function can exponentially increase its weight and length. (English. Russian original) Zbl 1317.94168

Math. Notes 87, No. 6, 860-873 (2010); translation from Mat. Zametki 87, No. 6, 886-900 (2010).
MSC:  94C10 06E30
PDFBibTeX XMLCite
Full Text: DOI

Parallel complexity of iterated morphisms and the arithmetic of small numbers. (English) Zbl 1493.68186

Havel, Ivan M. (ed.) et al., Mathematical foundations of computer science 1992. 17th international symposium, Prague, Czechoslovakia, August 24–28, 1992. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 629, 227-235 (1992).
MSC:  68Q45 68Q25 68Q42
PDFBibTeX XMLCite
Full Text: DOI

Filter Results by …

Document Type

all top 5

Author

all top 5

Year of Publication

all top 3

Main Field

all top 3

Software