×

Found 182 Documents (Results 1–100)

100
MathJax

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
PDF BibTeX XML Cite
Full Text: DOI

Multiparty Karchmer-Wigderson games and threshold circuits. (English) Zbl 07561752

Saraf, Shubhangi (ed.), 35th computational complexity conference, CCC 2020, July 28–31, 2020, Saarbrücken, Germany, virtual conference. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 169, Article 24, 23 p. (2020).
MSC:  68Q25
PDF BibTeX XML Cite
Full Text: DOI

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
PDF BibTeX XML Cite
Full Text: DOI

Lower bounds on balancing sets and depth-2 threshold circuits. (English) Zbl 07561565

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 72, 14 p. (2019).
MSC:  68Nxx 68Qxx
PDF BibTeX XML Cite
Full Text: DOI

A #SAT algorithm for small constant-depth circuits with PTF gates. (English) Zbl 07559051

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 8, 20 p. (2019).
MSC:  68Qxx
PDF BibTeX XML Cite
Full Text: DOI

Near-optimal lower bounds on the threshold degree and sign-rank of \(\mathrm{AC}^0\). (English) Zbl 1433.68153

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). 401-412 (2019).
PDF BibTeX XML Cite
Full Text: DOI

Bootstrapping results for threshold circuits “just beyond” known lower bounds. (English) Zbl 1433.68137

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). 34-41 (2019).
MSC:  68Q06 68Q17
PDF BibTeX XML Cite
Full Text: DOI

Satisfiability and derandomization for small polynomial threshold circuits. (English) Zbl 07378658

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 46, 19 p. (2018).
MSC:  68W20 68W25 90C27
PDF BibTeX XML Cite
Full Text: DOI

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

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:  68W20 68W25 90C27
PDF BibTeX XML Cite
Full Text: DOI

Limits on representing Boolean functions by linear combinations of simple functions: thresholds, ReLUs, and low-degree polynomials. (English) Zbl 1441.68047

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 6, 24 p. (2018).
MSC:  68Q06 68Q17
PDF BibTeX XML Cite
Full Text: DOI arXiv

A PRG for Boolean PTF of degree 2 with seed length subpolynomial in \(\epsilon\) and logarithmic in \(n\). (English) Zbl 1441.68151

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 2, 24 p. (2018).
MSC:  68Q87 68Q06
PDF BibTeX XML Cite
Full Text: DOI

Quantified derandomization of linear threshold circuits. (English) Zbl 1428.68169

Diakonikolas, Ilias (ed.) et al., Proceedings of the 50th annual ACM SIGACT symposium on theory of computing, STOC ’18, Los Angeles, CA, USA, June 25–29, 2018. New York, NY: Association for Computing Machinery (ACM). 855-865 (2018).
PDF BibTeX XML Cite
Full Text: DOI arXiv

More consequences of falsifying SETH and the orthogonal vectors conjecture. (English) Zbl 1427.68099

Diakonikolas, Ilias (ed.) et al., Proceedings of the 50th annual ACM SIGACT symposium on theory of computing, STOC ’18, Los Angeles, CA, USA, June 25–29, 2018. New York, NY: Association for Computing Machinery (ACM). 253-266 (2018).
MSC:  68Q17 68Q25 94C11
PDF BibTeX XML Cite
Full Text: DOI arXiv

Formal verification of masked hardware implementations in the presence of glitches. (English) Zbl 1428.94062

Nielsen, Jesper Buus (ed.) et al., Advances in cryptology – EUROCRYPT 2018. 37th annual international conference on the theory and applications of cryptographic techniques, Tel Aviv, Israel, April 29 – May 3, 2018. Proceedings. Part II. Cham: Springer. Lect. Notes Comput. Sci. 10821, 321-353 (2018).
MSC:  94A60 68P25
PDF BibTeX XML Cite
Full Text: DOI

PAC learning depth-3 \(\mathrm{AC}^0\) circuits of bounded top fanin. (English) Zbl 1403.68091

Hanneke, Steve (ed.) et al., International conference on algorithmic learning theory. Proceedings of the 28th conference (ALT 2017), Kyoto University, Kyoto, Japan, October 15–17, 2017. [s.l.]: Proceedings of Machine Learning Research PMLR. Proceedings of Machine Learning Research (PMLR) 76, 667-680 (2017).
MSC:  68Q32 94C10
PDF BibTeX XML Cite
Full Text: Link

A polynomial restriction lemma with applications. (English) Zbl 1370.68223

Hatami, Hamed (ed.) et al., Proceedings of the 49th annual ACM SIGACT symposium on theory of computing, STOC ’17, Montreal, QC, Canada, June 19–23, 2017. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-4528-6). 615-628 (2017).
MSC:  68Q87 68Q10 68Q17 94C10
PDF BibTeX XML Cite
Full Text: DOI

An efficient side-channel protected AES implementation with arbitrary protection order. (English) Zbl 1383.94020

Handschuh, Helena (ed.), Topics in cryptology – CT-RSA 2017. The cryptographers’ track at the RSA conference 2017, San Francisco, CA, USA, February 14–17, 2017. Proceedings. Cham: Springer (ISBN 978-3-319-52152-7/pbk; 978-3-319-52153-4/ebook). Lecture Notes in Computer Science 10159, 95-112 (2017).
MSC:  94A60 68P25
PDF BibTeX XML Cite
Full Text: DOI Link

Super-linear gate and super-quadratic wire lower bounds for depth-two and depth-three threshold circuits. (English) Zbl 1373.68220

Wichs, Daniel (ed.) et al., Proceedings of the 48th annual ACM SIGACT symposium on theory of computing, STOC ’16, Cambridge, MA, USA, June 19–21, 2016. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-4132-5). 633-643 (2016).
MSC:  68Q05 68Q17 94C10
PDF BibTeX XML Cite
Full Text: DOI arXiv

Consolidating masking schemes. (English) Zbl 1375.94156

Gennaro, Rosario (ed.) et al., Advances in cryptology – CRYPTO 2015. 35th annual cryptology conference, Santa Barbara, CA, USA, August 16–20, 2015. Proceedings. Part I. Berlin: Springer (ISBN 978-3-662-47988-9/pbk; 978-3-662-47989-6/ebook). Lecture Notes in Computer Science 9215, 764-783 (2015).
MSC:  94A60
PDF BibTeX XML Cite
Full Text: DOI Link

Upper bounds on Fourier entropy. (English) Zbl 1468.94350

Xu, Dachuan (ed.) et al., Computing and combinatorics. 21st international conference, COCOON 2015, Beijing, China, August 4–6, 2015. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 9198, 771-782 (2015).
MSC:  94A17 42A38 94C11
PDF BibTeX XML Cite
Full Text: DOI

Rational arguments: single round delegation with sublinear verification. (English) Zbl 1364.68199

Proceedings of the 5th conference on innovations in theoretical computer science, ITCS’14, Princeton, NJ, USA, January 11–14, 2014. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-2243-0). 523-539 (2014).
MSC:  68Q05 68M12 68Q10 68Q15 94A60
PDF BibTeX XML Cite
Full Text: DOI

Superimposed codes and threshold group testing. (English) Zbl 1309.94185

Aydinian, Harout (ed.) et al., Information theory, combinatorics, and search theory. In memory of Rudolf Ahlswede. Berlin: Springer (ISBN 978-3-642-36898-1/pbk). Lecture Notes in Computer Science 7777, 509-533 (2013).
PDF BibTeX XML Cite
Full Text: DOI arXiv Link

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
PDF BibTeX XML Cite
Full Text: DOI

Boolean functions. Theory, algorithms, and applications. (English) Zbl 1237.06001

Encyclopedia of Mathematics and its Applications 142. Cambridge: Cambridge University Press (ISBN 978-0-521-84751-3/hbk; 978-1-139-06424-8/ebook). xxi, 687 p. (2011).
MSC:  06-00 06E30
PDF BibTeX XML Cite

Computing rational radical sums in uniform \(\mathrm{TC}^0\). (English) Zbl 1245.68238

Lodaya, Kamal (ed.) et al., IARCS annual conference on foundations of software technology and theoretical computer science (FSTTCS 2010), December 15–18, 2010, Chennai, India. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-939897-23-1). LIPIcs – Leibniz International Proceedings in Informatics 8, 308-316, electronic only (2010).
MSC:  68U05 68Q25
PDF BibTeX XML Cite
Full Text: DOI Link

Influence of the driver and active load threshold voltage in design of pseudo-NMOS logic. (English) Zbl 1231.94099

Mastorakis, N. (ed.) et al., Latest trends on circuits. Papers based on the presentations at the 14th WSEAS international conference on circuits (Part of the 14th WSEAS CSCC multiconference), Corfu Island, Greece, July 22–24, 2010. Athens: World Scientific and Engineering Academy and Society (WSEAS) (ISBN 978-960-474-206-6/CD-ROM; 978-960-474-198-4). 110-115 (2010).
MSC:  94C10 94C30
PDF BibTeX XML Cite

Optimization of neuro-fuzzy structures in technical diagnostics systems. (English) Zbl 1170.93302

Lecture Notes in Control and Computer Science 9. Zielona Góra: University of Zielona Góra Press (ISBN 83-89712-88-1/pbk). 113 p. (2005).
PDF BibTeX XML Cite

Non-perfect secret sharing over general access structures. (English) Zbl 1033.94540

Menezes, Alfred (ed.) et al., Progress in cryptology – INDOCRYPT 2002. Third international conference on cryptology in India, Hyderabad, India, December 16–18, 2002. Proceedings. Berlin: Springer (ISBN 3-540-00263-4/pbk). Lect. Notes Comput. Sci. 2551, 409-421 (2002).
MSC:  94A60 94C05
PDF BibTeX XML Cite
Full Text: Link

Bounded depth arithmetic circuits: Counting and closure. (English) Zbl 1020.94543

Wiedermann, Jiří (ed.) et al., Automata, languages and programming. 26th international colloquium, ICALP ‘99. Prague, Czech Republic, July 11-15, 1999. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 1644, 149-158 (1999).
MSC:  94C10 68Q15 94C15
PDF BibTeX XML Cite

Applications of combinatorial designs to communications, cryptography, and networking. (English) Zbl 0972.94052

Lamb, John D. (ed.) et al., Surveys in combinatorics, 1999. Proceedings of the 17th British combinatorial conference, University of Kent at Canterbury, UK, 1999. Cambridge: Cambridge University Press. Lond. Math. Soc. Lect. Note Ser. 267, 37-100 (1999).
PDF BibTeX XML Cite

Filter Results by …

Document Type

Reviewing State

all top 5

Author

all top 5

Serial

all top 5

Year of Publication

all top 3

Classification

all top 3

Software