Jeřábek, Emil Models of \(\mathsf{VTC^0}\) as exponential integer parts. (English) Zbl 07738004 Math. Log. Q. 69, No. 2, 244-260 (2023). MSC: 03-XX PDFBibTeX XMLCite \textit{E. Jeřábek}, Math. Log. Q. 69, No. 2, 244--260 (2023; Zbl 07738004) Full Text: DOI arXiv OA License
Jeřábek, Emil Elementary analytic functions in \(\mathsf{VT}\mathsf{C}^0\). (English) Zbl 07680011 Ann. Pure Appl. Logic 174, No. 6, Article ID 103269, 50 p. (2023). MSC: 03F20 03F30 33B10 PDFBibTeX XMLCite \textit{E. Jeřábek}, Ann. Pure Appl. Logic 174, No. 6, Article ID 103269, 50 p. (2023; Zbl 07680011) Full Text: DOI arXiv
Sun, Xiaoming; Sun, Yuan; Wu, Kewen; Xia, Zhiyu On the relationship between energy complexity and other Boolean function measures. (English) Zbl 1495.90163 J. Comb. Optim. 43, No. 5, 1470-1492 (2022). MSC: 90C27 90C90 PDFBibTeX XMLCite \textit{X. Sun} et al., J. Comb. Optim. 43, No. 5, 1470--1492 (2022; Zbl 1495.90163) Full Text: DOI arXiv
Jeřábek, Emil Iterated multiplication in \(VTC^0\). (English) Zbl 1500.03017 Arch. Math. Logic 61, No. 5-6, 705-767 (2022). Reviewer: Roman Murawski (Poznań) MSC: 03F30 03F20 03D15 03C62 PDFBibTeX XMLCite \textit{E. Jeřábek}, Arch. Math. Logic 61, No. 5--6, 705--767 (2022; Zbl 1500.03017) Full Text: DOI arXiv
Chattopadhyay, Arkadev; Mande, Nikhil S. A short list of equalities induces large sign-rank. (English) Zbl 1502.68124 SIAM J. Comput. 51, No. 3, 820-848 (2022). MSC: 68Q11 68Q06 68Q15 68Q17 PDFBibTeX XMLCite \textit{A. Chattopadhyay} and \textit{N. S. Mande}, SIAM J. Comput. 51, No. 3, 820--848 (2022; Zbl 1502.68124) Full Text: DOI
Chen, Lijie; Ren, Hanlin Strong average-case circuit lower bounds from nontrivial derandomization. (English) Zbl 07534654 SIAM J. Comput. 51, No. 3, STOC20-115-STOC20-173 (2022). MSC: 68Q05 68Q17 PDFBibTeX XMLCite \textit{L. Chen} and \textit{H. Ren}, SIAM J. Comput. 51, No. 3, STOC20--115-STOC20--173 (2022; Zbl 07534654) Full Text: DOI
Oliveira, Igor C.; Santhanam, Rahul; Tell, Roei Expander-based cryptography meets natural proofs. (English) Zbl 07506816 Comput. Complexity 31, No. 1, Paper No. 4, 60 p. (2022). MSC: 68Q06 94A60 PDFBibTeX XMLCite \textit{I. C. Oliveira} et al., Comput. Complexity 31, No. 1, Paper No. 4, 60 p. (2022; Zbl 07506816) Full Text: DOI
Paranhos, Raffael M.; Nascimento Silva, Janio Carlos; Souza, Uéverton S.; Ochi, Luiz Satoru 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 \textit{R. M. Paranhos} et al., Lect. Notes Comput. Sci. 13135, 348--363 (2021; Zbl 07550536) Full Text: DOI
Babai, László; Hansen, Kristoffer A.; Podolskii, Vladimir V.; Sun, Xiaoming Weights of exact threshold functions. (English. Russian original) Zbl 1492.94224 Izv. Math. 85, No. 6, 1039-1059 (2021); translation from Izv. Ross. Akad. Nauk, Ser. Mat. 85, No. 6, 5-26 (2021). MSC: 94C11 94D10 68Q15 PDFBibTeX XMLCite \textit{L. Babai} et al., Izv. Math. 85, No. 6, 1039--1059 (2021; Zbl 1492.94224); translation from Izv. Ross. Akad. Nauk, Ser. Mat. 85, No. 6, 5--26 (2021) Full Text: DOI MNR
Long, Philip M. Superlinear integrality gaps for the minimum majority problem. (English) Zbl 07453660 SIAM J. Discrete Math. 35, No. 4, 3004-3016 (2021). MSC: 68W25 68Q17 68Q25 68T05 90C10 90C57 PDFBibTeX XMLCite \textit{P. M. Long}, SIAM J. Discrete Math. 35, No. 4, 3004--3016 (2021; Zbl 07453660) Full Text: DOI
Bun, Mark; Thaler, Justin The large-error approximate degree of \(\mathrm{AC}^0\). (English) Zbl 1528.68135 Theory Comput. 17, Paper No. 7, 46 p. (2021). MSC: 68Q15 68Q06 68Q17 PDFBibTeX XMLCite \textit{M. Bun} and \textit{J. Thaler}, Theory Comput. 17, Paper No. 7, 46 p. (2021; Zbl 1528.68135) Full Text: DOI
Williams, R. Ryan From circuit complexity to faster all-pairs shortest paths. (English) Zbl 1470.05139 SIAM Rev. 63, No. 3, 559-582 (2021). MSC: 05C76 05C82 05C85 68Q25 94C05 68W25 PDFBibTeX XMLCite \textit{R. R. Williams}, SIAM Rev. 63, No. 3, 559--582 (2021; Zbl 1470.05139) Full Text: DOI
Uchizawa, Kei 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 \textit{K. Uchizawa}, LIPIcs -- Leibniz Int. Proc. Inform. 181, Article 54, 13 p. (2020; Zbl 07765412) Full Text: DOI
Dzindzalieta, D.; Götze, F. Half-spaces with influential variable. (English) Zbl 1434.68196 Theory Probab. Appl. 65, No. 1, 114-120 (2020) and Teor. Veroyatn. Primen. 65, No. 1, 142-150 (2020). MSC: 68Q25 06E30 60E15 68W20 PDFBibTeX XMLCite \textit{D. Dzindzalieta} and \textit{F. Götze}, Theory Probab. Appl. 65, No. 1, 114--120 (2020; Zbl 1434.68196) Full Text: DOI
Golovnev, Alexander; Göös, Mika; Reichman, Daniel; Shinkar, Igor 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 \textit{A. Golovnev} et al., LIPIcs -- Leibniz Int. Proc. Inform. 145, Article 56, 20 p. (2019; Zbl 07650123) Full Text: DOI arXiv
Chen, Lijie; Williams, R. Ryan 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 \textit{L. Chen} and \textit{R. R. Williams}, LIPIcs -- Leibniz Int. Proc. Inform. 137, Article 19, 43 p. (2019; Zbl 07564419) Full Text: DOI
Carboni, Oliveira Igor; Santhanam, Rahul; Tell, Roei 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 \textit{O. I. Carboni} et al., LIPIcs -- Leibniz Int. Proc. Inform. 124, Article 18, 14 p. (2019; Zbl 07559061) Full Text: DOI
Amano, Kazuyuki; Tate, Shoma On XOR lemmas for the weight of polynomial threshold functions. (English) Zbl 1435.68220 Inf. Comput. 269, Article ID 104439, 11 p. (2019). MSC: 68R05 06E30 68Q25 90C10 94D10 PDFBibTeX XMLCite \textit{K. Amano} and \textit{S. Tate}, Inf. Comput. 269, Article ID 104439, 11 p. (2019; Zbl 1435.68220) Full Text: DOI
Sakai, Takayuki; Seto, Kazuhisa; Tamaki, Suguru; Teruyama, Junichi Bounded depth circuits with weighted symmetric gates: satisfiability, lower bounds and compression. (English) Zbl 1423.68218 J. Comput. Syst. Sci. 105, 87-103 (2019). MSC: 68Q25 68Q17 94C10 PDFBibTeX XMLCite \textit{T. Sakai} et al., J. Comput. Syst. Sci. 105, 87--103 (2019; Zbl 1423.68218) Full Text: DOI Link
Chen, Shiteng; Papakonstantinou, Periklis A. Depth reduction for composites. (English) Zbl 1421.68054 SIAM J. Comput. 48, No. 2, 668-686 (2019). MSC: 68Q15 68Q17 94C10 PDFBibTeX XMLCite \textit{S. Chen} and \textit{P. A. Papakonstantinou}, SIAM J. Comput. 48, No. 2, 668--686 (2019; Zbl 1421.68054) Full Text: DOI
Bun, Mark; Thaler, Justin 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 \textit{M. Bun} and \textit{J. Thaler}, LIPIcs -- Leibniz Int. Proc. Inform. 116, Article 35, 18 p. (2018; Zbl 1522.68195) Full Text: DOI
Williams, R. Ryan Faster all-pairs shortest paths via circuit complexity. (English) Zbl 1400.05075 SIAM J. Comput. 47, No. 5, 1965-1985 (2018). MSC: 05C12 05C38 05C20 05C76 05C85 68Q25 PDFBibTeX XMLCite \textit{R. R. Williams}, SIAM J. Comput. 47, No. 5, 1965--1985 (2018; Zbl 1400.05075) Full Text: DOI
Cheraghchi, Mahdi; Grigorescu, Elena; Juba, Brendan; Wimmer, Karl; Xie, Ning \(\mathrm{AC}^{0}\circ \mathrm{MOD}_{2}\) lower bounds for the Boolean inner product. (English) Zbl 1398.68159 J. Comput. Syst. Sci. 97, 45-59 (2018). MSC: 68Q05 68Q17 94C10 PDFBibTeX XMLCite \textit{M. Cheraghchi} et al., J. Comput. Syst. Sci. 97, 45--59 (2018; Zbl 1398.68159) Full Text: DOI
Jahanjou, Hamidreza; Miles, Eric; Viola, Emanuele Local reduction. (English) Zbl 1394.68184 Inf. Comput. 261, Part 2, 281-295 (2018). MSC: 68Q25 68Q15 PDFBibTeX XMLCite \textit{H. Jahanjou} et al., Inf. Comput. 261, Part 2, 281--295 (2018; Zbl 1394.68184) Full Text: DOI
Kawachi, Akinori Circuit lower bounds from learning-theoretic approaches. (English) Zbl 1393.68152 Theor. Comput. Sci. 733, 83-98 (2018). MSC: 68T05 68Q17 94C10 PDFBibTeX XMLCite \textit{A. Kawachi}, Theor. Comput. Sci. 733, 83--98 (2018; Zbl 1393.68152) Full Text: DOI
Ding, Ning; Ren, Yanli; Gu, Dawu Learning \(\mathrm{AC}^0\) under \(k\)-dependent distributions. (English) Zbl 1485.68121 Gopal, T. V. (ed.) et al., Theory and applications of models of computation. 14th annual conference, TAMC 2017, Bern, Switzerland, April 20–22, 2017. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 10185, 187-200 (2017). MSC: 68Q32 68Q25 PDFBibTeX XMLCite \textit{N. Ding} et al., Lect. Notes Comput. Sci. 10185, 187--200 (2017; Zbl 1485.68121) Full Text: DOI
Jahanjou, Hamid; Miles, Eric; Viola, Emanuele 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 \textit{H. Jahanjou} et al., Lect. Notes Comput. Sci. 9134, 749--760 (2015; Zbl 1394.68183) Full Text: DOI arXiv
Jeřábek, Emil Open induction in a bounded arithmetic for \(\mathrm{TC}^{0}\). (English) Zbl 1371.03090 Arch. Math. Logic 54, No. 3-4, 359-394 (2015). MSC: 03F20 03F30 12Y05 12J10 PDFBibTeX XMLCite \textit{E. Jeřábek}, Arch. Math. Logic 54, No. 3--4, 359--394 (2015; Zbl 1371.03090) Full Text: DOI arXiv
Hansen, Kristoffer Arnsfelt; Podolskii, Vladimir V. Polynomial threshold functions and Boolean threshold circuits. (English) Zbl 1312.68089 Inf. Comput. 240, 56-73 (2015). MSC: 68Q15 94C10 PDFBibTeX XMLCite \textit{K. A. Hansen} and \textit{V. V. Podolskii}, Inf. Comput. 240, 56--73 (2015; Zbl 1312.68089) Full Text: DOI
Annampedu, Viswanath; Wagh, Meghanad D. Decomposition of threshold functions into bounded fan-in threshold functions. (English) Zbl 1358.94114 Inf. Comput. 227, 84-101 (2013). MSC: 94C10 PDFBibTeX XMLCite \textit{V. Annampedu} and \textit{M. D. Wagh}, Inf. Comput. 227, 84--101 (2013; Zbl 1358.94114) Full Text: DOI
Gál, Anna; Trifonov, Vladimir On the correlation between parity and modular polynomials. (English) Zbl 1279.68098 Theory Comput. Syst. 50, No. 3, 516-536 (2012). MSC: 68Q15 68Q25 PDFBibTeX XMLCite \textit{A. Gál} and \textit{V. Trifonov}, Theory Comput. Syst. 50, No. 3, 516--536 (2012; Zbl 1279.68098) Full Text: DOI
Jeřábek, Emil Root finding with threshold circuits. (English) Zbl 1282.68116 Theor. Comput. Sci. 462, 59-69 (2012). MSC: 68Q15 68Q10 PDFBibTeX XMLCite \textit{E. Jeřábek}, Theor. Comput. Sci. 462, 59--69 (2012; Zbl 1282.68116) Full Text: DOI arXiv
Podolskii, Vladimir V. Exponential lower bound for bounded depth circuits with few threshold gates. (English) Zbl 1237.68091 Inf. Process. Lett. 112, No. 7, 267-271 (2012). MSC: 68Q17 68Q15 PDFBibTeX XMLCite \textit{V. V. Podolskii}, Inf. Process. Lett. 112, No. 7, 267--271 (2012; Zbl 1237.68091) Full Text: DOI
Podolskii, Vladimir V. Degree-uniform lower bound on the weights of polynomials with given sign function. (English. Russian original) Zbl 1358.94116 Proc. Steklov Inst. Math. 274, 231-246 (2011); translation from Tr. Mat. Inst. Steklova 274, 252-268 (2011). MSC: 94C10 68Q17 PDFBibTeX XMLCite \textit{V. V. Podolskii}, Proc. Steklov Inst. Math. 274, 231--246 (2011; Zbl 1358.94116); translation from Tr. Mat. Inst. Steklova 274, 252--268 (2011) Full Text: DOI
Lu, Chi-Jen; Tsai, Shi-Chun; Wu, Hsin-Lung Complexity of hard-core set proofs. (English) Zbl 1255.68067 Comput. Complexity 20, No. 1, 145-171 (2011). MSC: 68Q05 68Q17 68Q10 PDFBibTeX XMLCite \textit{C.-J. Lu} et al., Comput. Complexity 20, No. 1, 145--171 (2011; Zbl 1255.68067) Full Text: DOI
Sherstov, Alexander A. The unbounded-error communication complexity of symmetric functions. (English) Zbl 1265.03035 Combinatorica 31, No. 5, 583-614 (2011). Reviewer: Cristian S. Calude (Bucuresti) MSC: 03D15 68Q17 PDFBibTeX XMLCite \textit{A. A. Sherstov}, Combinatorica 31, No. 5, 583--614 (2011; Zbl 1265.03035) Full Text: DOI
Van den Nest, Maarten Quantum matchgate computations and linear threshold gates. (English) Zbl 1207.81016 Proc. R. Soc. Lond., Ser. A, Math. Phys. Eng. Sci. 467, No. 2127, 821-840 (2011). MSC: 81P68 68Q12 81T80 PDFBibTeX XMLCite \textit{M. Van den Nest}, Proc. R. Soc. Lond., Ser. A, Math. Phys. Eng. Sci. 467, No. 2127, 821--840 (2011; Zbl 1207.81016) Full Text: DOI arXiv
Bollig, Beate; Gillé, Marc 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 \textit{B. Bollig} and \textit{M. Gillé}, Lect. Notes Comput. Sci. 6543, 135--145 (2011; Zbl 1298.68109) Full Text: DOI
Podolskii, V. V.; Sherstov, A. A. 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 \textit{V. V. Podolskii} and \textit{A. A. Sherstov}, Math. Notes 87, No. 6, 860--873 (2010; Zbl 1317.94168); translation from Mat. Zametki 87, No. 6, 886--900 (2010) Full Text: DOI
O’Donnell, Ryan; Servedio, Rocco A. New degree bounds for polynomial threshold functions. (English) Zbl 1240.05303 Combinatorica 30, No. 3, 327-358 (2010). Reviewer: Jörg Desel (Hagen) MSC: 05E99 68Q99 68Q17 68Q32 PDFBibTeX XMLCite \textit{R. O'Donnell} and \textit{R. A. Servedio}, Combinatorica 30, No. 3, 327--358 (2010; Zbl 1240.05303) Full Text: DOI
Matulef, Kevin; O’Donnell, Ryan; Rubinfeld, Ronitt; Servedio, Rocco Testing (subclasses of) halfspaces. (English) Zbl 1309.68226 Goldreich, Oded (ed.), Property testing. Current research and surveys. Berlin: Springer (ISBN 978-3-642-16366-1/pbk). Lecture Notes in Computer Science 6390, 334-340 (2010). MSC: 68W20 68Q25 PDFBibTeX XMLCite \textit{K. Matulef} et al., Lect. Notes Comput. Sci. 6390, 334--340 (2010; Zbl 1309.68226) Full Text: DOI Link
Green, Frederic; Roy, Amitabha Uniqueness of optimal mod 3 polynomials for parity. (English) Zbl 1200.11059 J. Number Theory 130, No. 4, 961-975 (2010). Reviewer: Andrew Ledoan (Boston College) MSC: 11L07 PDFBibTeX XMLCite \textit{F. Green} and \textit{A. Roy}, J. Number Theory 130, No. 4, 961--975 (2010; Zbl 1200.11059) Full Text: DOI
Uchizawa, Kei; Takimoto, Eiji Exponential lower bounds on the size of constant-depth threshold circuits with small energy complexity. (English) Zbl 1152.68047 Theor. Comput. Sci. 407, No. 1-3, 474-487 (2008). MSC: 68T05 68Q17 92B20 94C10 PDFBibTeX XMLCite \textit{K. Uchizawa} and \textit{E. Takimoto}, Theor. Comput. Sci. 407, No. 1--3, 474--487 (2008; Zbl 1152.68047) Full Text: DOI
Atıcı, Alp; Servedio, Rocco A. Learning unions of \(\omega(1)\)-dimensional rectangles. (English) Zbl 1181.68159 Theor. Comput. Sci. 405, No. 3, 209-222 (2008). MSC: 68Q32 PDFBibTeX XMLCite \textit{A. Atıcı} and \textit{R. A. Servedio}, Theor. Comput. Sci. 405, No. 3, 209--222 (2008; Zbl 1181.68159) Full Text: DOI
Sherstov, Alexander A. Powering requires threshold depth 3. (English) Zbl 1184.68269 Inf. Process. Lett. 102, No. 2-3, 104-107 (2007). MSC: 68Q17 PDFBibTeX XMLCite \textit{A. A. Sherstov}, Inf. Process. Lett. 102, No. 2--3, 104--107 (2007; Zbl 1184.68269) Full Text: DOI
Uchizawa, Kei; Douglas, Rodney; Maass, Wolfgang On the computational power of threshold circuits with sparse activity. (English) Zbl 1104.92003 Neural Comput. 18, No. 12, 2994-3008 (2006). MSC: 92B20 94C99 92C20 68T05 PDFBibTeX XMLCite \textit{K. Uchizawa} et al., Neural Comput. 18, No. 12, 2994--3008 (2006; Zbl 1104.92003) Full Text: DOI
Kiltz, Eike; Simon, Hans Ulrich Threshold circuit lower bounds on cryptographic functions. (English) Zbl 1078.68033 J. Comput. Syst. Sci. 71, No. 2, 185-212 (2005). MSC: 68P25 94A60 PDFBibTeX XMLCite \textit{E. Kiltz} and \textit{H. U. Simon}, J. Comput. Syst. Sci. 71, No. 2, 185--212 (2005; Zbl 1078.68033) Full Text: DOI
Bourgain, Jean Estimation of certain exponential sums arising in complexity theory. (English. Abridged French version) Zbl 1112.11038 C. R., Math., Acad. Sci. Paris 340, No. 9, 627-631 (2005). MSC: 11L07 68Q15 94C10 PDFBibTeX XMLCite \textit{J. Bourgain}, C. R., Math., Acad. Sci. Paris 340, No. 9, 627--631 (2005; Zbl 1112.11038) Full Text: DOI
Klivans, Adam R.; O’Donnell, Ryan; Servedio, Rocco A. Learning intersections and thresholds of halfspaces. (English) Zbl 1074.68026 J. Comput. Syst. Sci. 68, No. 4, 808-840 (2004). MSC: 68Q32 PDFBibTeX XMLCite \textit{A. R. Klivans} et al., J. Comput. Syst. Sci. 68, No. 4, 808--840 (2004; Zbl 1074.68026) Full Text: DOI
Šíma, Jiří; Orponen, Pekka General-purpose computation with neural networks: a survey of complexity theoretic results. (English) Zbl 1097.68589 Neural Comput. 15, No. 12, 2727-2778 (2003). MSC: 68T05 PDFBibTeX XMLCite \textit{J. Šíma} and \textit{P. Orponen}, Neural Comput. 15, No. 12, 2727--2778 (2003; Zbl 1097.68589) Full Text: DOI Link
Shpilka, Amir Affine projections of symmetric polynomials. (English) Zbl 1059.68042 J. Comput. Syst. Sci. 65, No. 4, 639-659 (2002). MSC: 68Q10 PDFBibTeX XMLCite \textit{A. Shpilka}, J. Comput. Syst. Sci. 65, No. 4, 639--659 (2002; Zbl 1059.68042) Full Text: DOI
Reischuk, R. Can large fanin circuits perform reliable computations in the presence of faults? (English) Zbl 0945.68017 Theor. Comput. Sci. 240, No. 2, 319-335 (2000). MSC: 68M20 PDFBibTeX XMLCite \textit{R. Reischuk}, Theor. Comput. Sci. 240, No. 2, 319--335 (2000; Zbl 0945.68017) Full Text: DOI
Maciel, Alexis; Thérien, Denis Efficient threshold circuits for power series. (English) Zbl 1009.68061 Inf. Comput. 152, No. 1, 62-73 (1999). MSC: 68Q25 94C10 68Q15 PDFBibTeX XMLCite \textit{A. Maciel} and \textit{D. Thérien}, Inf. Comput. 152, No. 1, 62--73 (1999; Zbl 1009.68061) Full Text: DOI
Grolmusz, Vince A lower bound for depth-3 circuits with MOD \(m\) gates. (English) Zbl 1338.68106 Inf. Process. Lett. 67, No. 2, 87-90 (1998). MSC: 68Q25 68Q05 68W20 94C10 PDFBibTeX XMLCite \textit{V. Grolmusz}, Inf. Process. Lett. 67, No. 2, 87--90 (1998; Zbl 1338.68106) Full Text: DOI Link
Maciel, Alexis; Thérien, Denis Threshold circuits of small majority-depth. (English) Zbl 0916.68060 Inf. Comput. 146, No. 1, 55-83 (1998). MSC: 68Q15 PDFBibTeX XMLCite \textit{A. Maciel} and \textit{D. Thérien}, Inf. Comput. 146, No. 1, 55--83 (1998; Zbl 0916.68060) Full Text: DOI Link
Turán, György; Vatan, Farrokh On the computation of Boolean functions by analog circuits of bounded fan-in. (English) Zbl 0869.68050 J. Comput. Syst. Sci. 54, No. 1, 199-212 (1997). MSC: 68Q15 PDFBibTeX XMLCite \textit{G. Turán} and \textit{F. Vatan}, J. Comput. Syst. Sci. 54, No. 1, 199--212 (1997; Zbl 0869.68050) Full Text: DOI
Grolmusz, Vince On the power of circuits with gates of low \(L_{1}\) norms. (English) Zbl 1053.68575 Theor. Comput. Sci. 188, No. 1-2, 117-128 (1997). MSC: 68Q15 68Q25 PDFBibTeX XMLCite \textit{V. Grolmusz}, Theor. Comput. Sci. 188, No. 1--2, 117--128 (1997; Zbl 1053.68575) Full Text: DOI
Beigel, Richard; Maciel, Alexis Upper and lower bounds for some depth-3 circuit classes. (English) Zbl 0890.68063 Comput. Complexity 6(1996-97), No. 3, 235-255 (1997). MSC: 68Q15 PDFBibTeX XMLCite \textit{R. Beigel} and \textit{A. Maciel}, Comput. Complexity 6, No. 3, 235--255 (1997; Zbl 0890.68063) Full Text: DOI
Razborov, Alexander A. On small depth threshold circuits. (English) Zbl 1502.68121 Nurmi, Otto (ed.) et al., Algorithm theory – SWAT ’92. Third Scandinavian workshop on algorithm theory, Helsinki, Finland, July 8–10, 1992. Proceedings. Berlin: Springer-Verlag. Lect. Notes Comput. Sci. 621, 42-52 (1992). MSC: 68Q06 PDFBibTeX XMLCite \textit{A. A. Razborov}, Lect. Notes Comput. Sci. 621, 42--52 (1992; Zbl 1502.68121) Full Text: DOI
Damm, Carsten; Holzer, Markus; Lange, Klaus-Jörn 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 \textit{C. Damm} et al., Lect. Notes Comput. Sci. 629, 227--235 (1992; Zbl 1493.68186) Full Text: DOI
Orponen, Pekka Neural networks and complexity theory. (English) Zbl 1493.68140 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, 50-61 (1992). MSC: 68Q06 68Q25 68T05 PDFBibTeX XMLCite \textit{P. Orponen}, Lect. Notes Comput. Sci. 629, 50--61 (1992; Zbl 1493.68140) Full Text: DOI