Chillara, Suryajith Functional lower bounds for restricted arithmetic circuits of depth four. (English) Zbl 07799592 Bojańczyk, Mikołaj (ed.) et al., 41st IARCS annual conference on foundations of software technology and theoretical computer science, FSTTCS 2021, virtual conference, December 15–17, 2021. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 213, Article 14, 15 p. (2021). MSC: 68N30 68Qxx PDFBibTeX XMLCite \textit{S. Chillara}, LIPIcs -- Leibniz Int. Proc. Inform. 213, Article 14, 15 p. (2021; Zbl 07799592) Full Text: DOI arXiv
Aaronson, Scott BQP after 28 years (Invited Talk). (English) Zbl 07799579 Bojańczyk, Mikołaj (ed.) et al., 41st IARCS annual conference on foundations of software technology and theoretical computer science, FSTTCS 2021, virtual conference, December 15–17, 2021. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 213, Article 1, 1 p. (2021). MSC: 68N30 68Qxx PDFBibTeX XMLCite \textit{S. Aaronson}, LIPIcs -- Leibniz Int. Proc. Inform. 213, Article 1, 1 p. (2021; Zbl 07799579) Full Text: DOI
Hasegawa, Atsuya; Le Gall, François Quantum advantage with shallow circuits under arbitrary corruption. (English) Zbl 07788647 Ahn, Hee-Kap (ed.) et al., 32nd international symposium on algorithms and computation, ISAAC 2021, Fukuoka, Japan, December 6–8, 2021. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 212, Article 74, 16 p. (2021). MSC: 68Wxx PDFBibTeX XMLCite \textit{A. Hasegawa} and \textit{F. Le Gall}, LIPIcs -- Leibniz Int. Proc. Inform. 212, Article 74, 16 p. (2021; Zbl 07788647) Full Text: DOI arXiv
Allender, Eric; Gouwar, John; Hirahara, Shuichi; Robelle, Caleb Cryptographic hardness under projections for time-bounded Kolmogorov complexity. (English) Zbl 07788627 Ahn, Hee-Kap (ed.) et al., 32nd international symposium on algorithms and computation, ISAAC 2021, Fukuoka, Japan, December 6–8, 2021. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 212, Article 54, 17 p. (2021). MSC: 68Wxx PDFBibTeX XMLCite \textit{E. Allender} et al., LIPIcs -- Leibniz Int. Proc. Inform. 212, Article 54, 17 p. (2021; Zbl 07788627) Full Text: DOI
Santhanam, Rahul; Tzameret, Iddo Iterated lower bound formulas: a diagonalization-based approach to proof complexity. (English) Zbl 07765167 Khuller, Samir (ed.) et al., Proceedings of the 53rd annual ACM SIGACT symposium on theory of computing, STOC ’21, virtual, Italy, June 21–25, 2021. New York, NY: Association for Computing Machinery (ACM). 234-247 (2021). MSC: 68Qxx PDFBibTeX XMLCite \textit{R. Santhanam} and \textit{I. Tzameret}, in: Proceedings of the 53rd annual ACM SIGACT symposium on theory of computing, STOC '21, virtual, Italy, June 21--25, 2021. New York, NY: Association for Computing Machinery (ACM). 234--247 (2021; Zbl 07765167) Full Text: DOI
Pich, Ján; Santhanam, Rahul Strong co-nondeterministic lower bounds for NP cannot be proved feasibly. (English) Zbl 07765166 Khuller, Samir (ed.) et al., Proceedings of the 53rd annual ACM SIGACT symposium on theory of computing, STOC ’21, virtual, Italy, June 21–25, 2021. New York, NY: Association for Computing Machinery (ACM). 223-233 (2021). MSC: 68Qxx PDFBibTeX XMLCite \textit{J. Pich} and \textit{R. Santhanam}, in: Proceedings of the 53rd annual ACM SIGACT symposium on theory of computing, STOC '21, virtual, Italy, June 21--25, 2021. New York, NY: Association for Computing Machinery (ACM). 223--233 (2021; Zbl 07765166) Full Text: DOI
Bhandari, Siddharth; Harsha, Prahladh; Molli, Tulasimohan; Srinivasan, Srikanth On the probabilistic degree of OR over the reals. (English) Zbl 1524.68132 Random Struct. Algorithms 59, No. 1, 53-67 (2021). MSC: 68Q06 06E30 68Q87 PDFBibTeX XMLCite \textit{S. Bhandari} et al., Random Struct. Algorithms 59, No. 1, 53--67 (2021; Zbl 1524.68132) Full Text: DOI
Soto, José Manuel Gómez; Wuensche, Andrew The Ameyalli-rule: logical universality in a 2D cellular automaton. (English) Zbl 07733660 J. Cell. Autom. 16, No. 3-4, 197-212 (2021). MSC: 68Q80 68Q06 PDFBibTeX XMLCite \textit{J. M. G. Soto} and \textit{A. Wuensche}, J. Cell. Autom. 16, No. 3--4, 197--212 (2021; Zbl 07733660) Full Text: arXiv Link
Mattes, Caroline; Weiß, Armin Parallel algorithms for power circuits and the word problem of the Baumslag group. (English) Zbl 07724247 Bonchi, Filippo (ed.) et al., 46th international symposium on mathematical foundations of computer science, MFCS 2021, August 23–27, 2021, Tallinn, Estonia. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 202, Article 74, 24 p. (2021). MSC: 68Qxx PDFBibTeX XMLCite \textit{C. Mattes} and \textit{A. Weiß}, LIPIcs -- Leibniz Int. Proc. Inform. 202, Article 74, 24 p. (2021; Zbl 07724247) Full Text: DOI arXiv
Chapman, Brynmor K.; Williams, R. Ryan Black-box hypotheses and lower bounds. (English) Zbl 07724202 Bonchi, Filippo (ed.) et al., 46th international symposium on mathematical foundations of computer science, MFCS 2021, August 23–27, 2021, Tallinn, Estonia. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 202, Article 29, 22 p. (2021). MSC: 68Qxx PDFBibTeX XMLCite \textit{B. K. Chapman} and \textit{R. R. Williams}, LIPIcs -- Leibniz Int. Proc. Inform. 202, Article 29, 22 p. (2021; Zbl 07724202) Full Text: DOI
Mihajlin, Ivan; Smal, Alexander Toward better depth lower bounds: the XOR-KRW conjecture. (English) Zbl 07711620 Kabanets, Valentine (ed.), 36th computational complexity conference, CCC 2021, Toronto, Ontario, Canada, virtual conference, July 20–23, 2021. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 200, Article 38, 24 p. (2021). MSC: 68Q25 PDFBibTeX XMLCite \textit{I. Mihajlin} and \textit{A. Smal}, LIPIcs -- Leibniz Int. Proc. Inform. 200, Article 38, 24 p. (2021; Zbl 07711620) Full Text: DOI
Hrubeš, Pavel; Yehudayoff, Amir Shadows of Newton polytopes. (English) Zbl 07711591 Kabanets, Valentine (ed.), 36th computational complexity conference, CCC 2021, Toronto, Ontario, Canada, virtual conference, July 20–23, 2021. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 200, Article 9, 23 p. (2021). MSC: 68Q25 PDFBibTeX XMLCite \textit{P. Hrubeš} and \textit{A. Yehudayoff}, LIPIcs -- Leibniz Int. Proc. Inform. 200, Article 9, 23 p. (2021; Zbl 07711591) Full Text: DOI
Golovnev, Alexander; Haviv, Ishay The (Generalized) orthogonality dimension of (Generalized) Kneser graphs: bounds and applications. (English) Zbl 07711590 Kabanets, Valentine (ed.), 36th computational complexity conference, CCC 2021, Toronto, Ontario, Canada, virtual conference, July 20–23, 2021. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 200, Article 8, 15 p. (2021). MSC: 68Q25 PDFBibTeX XMLCite \textit{A. Golovnev} and \textit{I. Haviv}, LIPIcs -- Leibniz Int. Proc. Inform. 200, Article 8, 15 p. (2021; Zbl 07711590) Full Text: DOI
Kamath, Chethan; Klein, Karen; Pietrzak, Krzysztof On treewidth, separators and Yao’s garbling. (English) Zbl 1520.94059 Nissim, Kobbi (ed.) et al., Theory of cryptography. 19th international conference, TCC 2021, Raleigh, NC, USA, November 8–11, 2021. Proceedings. Part II. Cham: Springer. Lect. Notes Comput. Sci. 13043, 486-517 (2021). MSC: 94A60 PDFBibTeX XMLCite \textit{C. Kamath} et al., Lect. Notes Comput. Sci. 13043, 486--517 (2021; Zbl 1520.94059) Full Text: DOI
Borgna, Agustín; Perdrix, Simon; Valiron, Benoît Hybrid quantum-classical circuit simplification with the ZX-calculus. (English) Zbl 1507.68114 Oh, Hakjoo (ed.), Programming languages and systems. 19th Asian symposium, APLAS 2021, Chicago, IL, USA, October 17–18, 2021. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 13008, 121-139 (2021). MSC: 68Q06 68Q12 81P65 94C11 PDFBibTeX XMLCite \textit{A. Borgna} et al., Lect. Notes Comput. Sci. 13008, 121--139 (2021; Zbl 1507.68114) Full Text: DOI arXiv
Popescu, Claudiu Marius Learning bounds for quantum circuits in the agnostic setting. (English) Zbl 1509.81297 Quantum Inf. Process. 20, No. 9, Paper No. 286, 24 p. (2021). MSC: 81P68 68Q06 PDFBibTeX XMLCite \textit{C. M. Popescu}, Quantum Inf. Process. 20, No. 9, Paper No. 286, 24 p. (2021; Zbl 1509.81297) Full Text: DOI
Chetia, R.; Boruah, S. M. B.; Sahu, P. P. Quantum image edge detection using improved Sobel mask based on NEQR. (English) Zbl 1509.81153 Quantum Inf. Process. 20, No. 1, Paper No. 21, 25 p. (2021). MSC: 81P45 81P68 94A08 PDFBibTeX XMLCite \textit{R. Chetia} et al., Quantum Inf. Process. 20, No. 1, Paper No. 21, 25 p. (2021; Zbl 1509.81153) Full Text: DOI
Tzameret, Iddo; Cook, Stephen A. Uniform, integral, and feasible proofs for the determinant identities. (English) Zbl 1499.03057 J. ACM 68, No. 2, Paper No. 12, 80 p. (2021). MSC: 03F20 03F30 15A15 68Q06 PDFBibTeX XMLCite \textit{I. Tzameret} and \textit{S. A. Cook}, J. ACM 68, No. 2, Paper No. 12, 80 p. (2021; Zbl 1499.03057) Full Text: DOI arXiv
Dawar, Anuj; Wilsenach, Gregory Symmetric circuits for rank logic. (English) Zbl 1508.68101 ACM Trans. Comput. Log. 23, No. 1, Article No. 6, 35 p. (2021). MSC: 68Q06 03B70 68Q19 94C11 PDFBibTeX XMLCite \textit{A. Dawar} and \textit{G. Wilsenach}, ACM Trans. Comput. Log. 23, No. 1, Article No. 6, 35 p. (2021; Zbl 1508.68101) Full Text: DOI
Lozhkin, S. A.; Khzmalyan, D. E. The complexity of the standard multiplexer function in a class of switching circuits. (English. Russian original) Zbl 1519.94255 Comput. Math. Model. 32, No. 4, 478-489 (2021); translation from Prikl. Mat. Inf. 68, 59-74 (2021). MSC: 94C05 94C11 PDFBibTeX XMLCite \textit{S. A. Lozhkin} and \textit{D. E. Khzmalyan}, Comput. Math. Model. 32, No. 4, 478--489 (2021; Zbl 1519.94255); translation from Prikl. Mat. Inf. 68, 59--74 (2021) Full Text: DOI
Chillara, Suryajith On computing multilinear polynomials using multi-\(r\)-ic depth four circuits. (English) Zbl 1495.68061 ACM Trans. Comput. Theory 13, No. 3, Paper No. 16, 21 p. (2021). MSC: 68Q06 PDFBibTeX XMLCite \textit{S. Chillara}, ACM Trans. Comput. Theory 13, No. 3, Paper No. 16, 21 p. (2021; Zbl 1495.68061) Full Text: DOI
Silva, Janio Carlos Nascimento; Souza, Uéverton S.; Ochi, Luiz Satoru Energy complexity of satisfying assignments in monotone circuits: on the complexity of computing the best case. (English) Zbl 1498.68107 Wu, Weili (ed.) et al., Algorithmic aspects in information and management. 15th international conference, AAIM 2021, virtual event, December 20–22, 2021. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 13153, 380-391 (2021). MSC: 68Q06 68Q17 68Q27 PDFBibTeX XMLCite \textit{J. C. N. Silva} et al., Lect. Notes Comput. Sci. 13153, 380--391 (2021; Zbl 1498.68107) Full Text: DOI
Barlag, Timon; Vollmer, Heribert A logical characterization of constant-depth circuits over the reals. (English) Zbl 07547731 Silva, Alexandra (ed.) et al., Logic, language, information, and computation. 27th international workshop, WoLLIC 2021, virtual event, October 5–8, 2021. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 13038, 16-30 (2021). MSC: 03B70 PDFBibTeX XMLCite \textit{T. Barlag} and \textit{H. Vollmer}, Lect. Notes Comput. Sci. 13038, 16--30 (2021; Zbl 07547731) Full Text: DOI arXiv
Jia, Kai; Rinard, Martin Verifying low-dimensional input neural networks via input quantization. (English) Zbl 1497.68310 Drăgoi, Cezara (ed.) et al., Static analysis. 28th international symposium, SAS 2021, Chicago, IL, USA, October 17–19, 2021. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12913, 206-214 (2021). MSC: 68Q60 65G50 68Q06 68T07 PDFBibTeX XMLCite \textit{K. Jia} and \textit{M. Rinard}, Lect. Notes Comput. Sci. 12913, 206--214 (2021; Zbl 1497.68310) Full Text: DOI arXiv
Jia, Kai; Rinard, Martin Exploiting verified neural networks via floating point numerical error. (English) Zbl 1497.68309 Drăgoi, Cezara (ed.) et al., Static analysis. 28th international symposium, SAS 2021, Chicago, IL, USA, October 17–19, 2021. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12913, 191-205 (2021). MSC: 68Q60 65G50 68Q06 68T07 PDFBibTeX XMLCite \textit{K. Jia} and \textit{M. Rinard}, Lect. Notes Comput. Sci. 12913, 191--205 (2021; Zbl 1497.68309) Full Text: DOI arXiv
Goubault, Eric; Palumby, Sébastien; Putot, Sylvie; Rustenholz, Louis; Sankaranarayanan, Sriram Static analysis of ReLU neural networks with tropical polyhedra. (English) Zbl 1497.68304 Drăgoi, Cezara (ed.) et al., Static analysis. 28th international symposium, SAS 2021, Chicago, IL, USA, October 17–19, 2021. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12913, 166-190 (2021). MSC: 68Q60 14T90 52B12 68Q06 PDFBibTeX XMLCite \textit{E. Goubault} et al., Lect. Notes Comput. Sci. 12913, 166--190 (2021; Zbl 1497.68304) Full Text: DOI arXiv
Broadbent, Anne; Kazmi, Raza Ali Constructions for quantum indistinguishability obfuscation. (English) Zbl 1497.81039 Longa, Patrick (ed.) et al., Progress in cryptology – LATINCRYPT 2021. 7th international conference on cryptology and information security in Latin America, Bogotá, Colombia, October 6–8, 2021. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12912, 24-43 (2021). MSC: 81P94 94A60 68Q10 68Q06 PDFBibTeX XMLCite \textit{A. Broadbent} and \textit{R. A. Kazmi}, Lect. Notes Comput. Sci. 12912, 24--43 (2021; Zbl 1497.81039) Full Text: DOI arXiv
Koucký, Michal Sorting short integers: the exposition. (English) Zbl 1484.68058 Bull. Eur. Assoc. Theor. Comput. Sci. EATCS 135, 44-57 (2021). MSC: 68P10 68Q06 68Q10 PDFBibTeX XMLCite \textit{M. Koucký}, Bull. Eur. Assoc. Theor. Comput. Sci. EATCS 135, 44--57 (2021; Zbl 1484.68058) Full Text: Link
Kombarov, Yu. A. Lower bound of circuit complexity of parity function in a basis of unbounded fan-in. (English. Russian original) Zbl 1497.94199 Mosc. Univ. Math. Bull. 76, No. 6, 266-270 (2021); translation from Vestn. Mosk. Univ., Ser. I 76, No. 6, 48-51 (2021). MSC: 94C11 94D10 PDFBibTeX XMLCite \textit{Yu. A. Kombarov}, Mosc. Univ. Math. Bull. 76, No. 6, 266--270 (2021; Zbl 1497.94199); translation from Vestn. Mosk. Univ., Ser. I 76, No. 6, 48--51 (2021) Full Text: DOI
Alon, Bar; Chung, Hao; Chung, Kai-Min; Huang, Mi-Ying; Lee, Yi; Shen, Yu-Ching Round efficient secure multiparty quantum computation with identifiable abort. (English) Zbl 1487.81034 Malkin, Tal (ed.) et al., Advances in cryptology – CRYPTO 2021. 41st annual international cryptology conference, CRYPTO 2021, virtual event, August 16–20, 2021. Proceedings. Part I. Cham: Springer. Lect. Notes Comput. Sci. 12825, 436-466 (2021). MSC: 81P68 81P94 81P70 94A60 68P25 81P45 68Q06 68M25 PDFBibTeX XMLCite \textit{B. Alon} et al., Lect. Notes Comput. Sci. 12825, 436--466 (2021; Zbl 1487.81034) Full Text: DOI
Kabanets, Valentine; Koroth, Sajin; Lu, Zhenjian; Myrisiotis, Dimitrios; Oliveira, Igor C. Algorithms and lower bounds for De Morgan formulas of low-communication leaf gates. (English) Zbl 1495.68064 ACM Trans. Comput. Theory 13, No. 4, Article No. 23, 37 p. (2021). MSC: 68Q06 68Q11 68W20 PDFBibTeX XMLCite \textit{V. Kabanets} et al., ACM Trans. Comput. Theory 13, No. 4, Article No. 23, 37 p. (2021; Zbl 1495.68064) Full Text: DOI arXiv
Chaugule, Prasad; Limaye, Nutan; Varre, Aditya Variants of homomorphism polynomials complete for algebraic complexity classes. (English) Zbl 1495.68060 ACM Trans. Comput. Theory 13, No. 4, Article No. 21, 26 p. (2021). MSC: 68Q06 68Q15 PDFBibTeX XMLCite \textit{P. Chaugule} et al., ACM Trans. Comput. Theory 13, No. 4, Article No. 21, 26 p. (2021; Zbl 1495.68060) Full Text: DOI
Goles, Eric; Montealegre, Pedro; Ríos Wilson, Martín; Theyssier, Guillaume On the impact of treewidth in the computational complexity of freezing dynamics. (English) Zbl 07495174 De Mol, Liesbeth (ed.) et al., Connecting with computability. 17th conference on computability in Europe, CiE 2021, virtual event, Ghent, Belgium, July 5–9, 2021. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12813, 260-272 (2021). MSC: 68Q45 37B10 68Q06 68Q17 68Q25 68W10 PDFBibTeX XMLCite \textit{E. Goles} et al., Lect. Notes Comput. Sci. 12813, 260--272 (2021; Zbl 07495174) Full Text: DOI arXiv
Parrot, Rémi; Briday, Mikaël; Roux, Olivier H. Timed Petri nets with reset for pipelined synchronous circuit design. (English) Zbl 1489.68166 Buchs, Didier (ed.) et al., Application and theory of Petri nets and concurrency. 42nd international conference, PETRI NETS 2021, virtual event, June 23–25, 2021. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12734, 55-75 (2021). MSC: 68Q85 68Q06 68Q45 68Q60 PDFBibTeX XMLCite \textit{R. Parrot} et al., Lect. Notes Comput. Sci. 12734, 55--75 (2021; Zbl 1489.68166) Full Text: DOI HAL
Viola, Emanuele AC0 unpredictability. (English) Zbl 1495.68068 ACM Trans. Comput. Theory 13, No. 1, Article No. 5, 8 p. (2021). MSC: 68Q06 94A17 PDFBibTeX XMLCite \textit{E. Viola}, ACM Trans. Comput. Theory 13, No. 1, Article No. 5, 8 p. (2021; Zbl 1495.68068) Full Text: DOI
Fei, Li-Juan; Lee, Jia; Huang, Xin; Peper, Ferdinand Effect of random fluctuations on minimizing the complexity of universal asynchronous cellular automata. (English) Zbl 1515.68191 Physica D 428, Article ID 133052, 9 p. (2021). MSC: 68Q80 68Q06 PDFBibTeX XMLCite \textit{L.-J. Fei} et al., Physica D 428, Article ID 133052, 9 p. (2021; Zbl 1515.68191) Full Text: DOI
Filom, Khashayar; Farhoodi, Roozbeh; Kording, Konrad Paul On PDE characterization of smooth hierarchical functions computed by neural networks. (English) Zbl 1522.68197 Neural Comput. 33, No. 12, 3204-3263 (2021). MSC: 68Q06 26B40 35Q68 41A30 68Q07 PDFBibTeX XMLCite \textit{K. Filom} et al., Neural Comput. 33, No. 12, 3204--3263 (2021; Zbl 1522.68197) Full Text: DOI arXiv
Oliveira, Igor C.; Pich, Ján; Santhanam, Rahul Hardness magnification near state-of-the-art lower bounds. (English) Zbl 1496.68156 Theory Comput. 17, Paper No. 11, 38 p. (2021). MSC: 68Q17 68Q06 68Q30 PDFBibTeX XMLCite \textit{I. C. Oliveira} et al., Theory Comput. 17, Paper No. 11, 38 p. (2021; Zbl 1496.68156) Full Text: DOI
Forbes, Michael A.; Shpilka, Amir; Tzameret, Iddo; Wigderson, Avi Proof complexity lower bounds from algebraic circuit complexity. (English) Zbl 07471587 Theory Comput. 17, Paper No. 10, 88 p. (2021). MSC: 68Q06 03F20 68Q15 68Q17 PDFBibTeX XMLCite \textit{M. A. Forbes} et al., Theory Comput. 17, Paper No. 10, 88 p. (2021; Zbl 07471587) Full Text: DOI
Koucký, Michal Circuit complexity of regular languages. (English) Zbl 1510.68037 Pin, Jean-Éric (ed.), Handbook of automata theory. Volume I. Theoretical foundations. Berlin: European Mathematical Society (EMS). 493-523 (2021). Reviewer: Klaus D. Kiermeier (Berlin) MSC: 68Q45 68Q06 68Q70 PDFBibTeX XMLCite \textit{M. Koucký}, in: Handbook of automata theory. Volume I. Theoretical foundations. Berlin: European Mathematical Society (EMS). 493--523 (2021; Zbl 1510.68037) Full Text: DOI
Dassow, Jürgen; Truthe, Bianca Accepting networks of evolutionary processors with resources restricted and structure limited filters. (English) Zbl 1508.68188 RAIRO, Theor. Inform. Appl. 55, Paper No. 8, 27 p. (2021). MSC: 68Q45 68Q06 68Q07 68Q42 PDFBibTeX XMLCite \textit{J. Dassow} and \textit{B. Truthe}, RAIRO, Theor. Inform. Appl. 55, Paper No. 8, 27 p. (2021; Zbl 1508.68188) Full Text: DOI
Fijalkow, Nathanaël; Lagarde, Guillaume; Ohlmann, Pierre; Serre, Olivier Lower bounds for arithmetic circuits via the Hankel matrix. (English) Zbl 1519.68079 Comput. Complexity 30, No. 2, Paper No. 14, 60 p. (2021). MSC: 68Q06 68Q17 PDFBibTeX XMLCite \textit{N. Fijalkow} et al., Comput. Complexity 30, No. 2, Paper No. 14, 60 p. (2021; Zbl 1519.68079) Full Text: DOI HAL
Stanimirović, Predrag S.; Katsikis, Vasilios N.; Jin, Long; Mosić, Dijana Properties and computation of continuous-time solutions to linear systems. (English) Zbl 1510.65062 Appl. Math. Comput. 405, Article ID 126242, 16 p. (2021). MSC: 65F10 15A06 15A09 65F45 68Q06 PDFBibTeX XMLCite \textit{P. S. Stanimirović} et al., Appl. Math. Comput. 405, Article ID 126242, 16 p. (2021; Zbl 1510.65062) Full Text: DOI
Chen, Qian; Livine, Etera R. Loop quantum gravity’s boundary maps. (English) Zbl 1482.83079 Classical Quantum Gravity 38, No. 15, Article ID 155019, 31 p. (2021). MSC: 83C57 83C60 57R15 81T35 58J32 81P16 68Q12 81P68 PDFBibTeX XMLCite \textit{Q. Chen} and \textit{E. R. Livine}, Classical Quantum Gravity 38, No. 15, Article ID 155019, 31 p. (2021; Zbl 1482.83079) Full Text: DOI arXiv
Rashno, Meysam; Haghparast, Majid; Mosleh, Mohammad Designing of parity preserving reversible Vedic multiplier. (English) Zbl 1522.68199 Int. J. Theor. Phys. 60, No. 8, 3024-3040 (2021). MSC: 68Q06 81P68 PDFBibTeX XMLCite \textit{M. Rashno} et al., Int. J. Theor. Phys. 60, No. 8, 3024--3040 (2021; Zbl 1522.68199) Full Text: DOI
Dong, Yumin; Liu, Zhixin; Zhang, Jinlei Quantum search algorithm for exceptional vertexes in regular graphs and its circuit implementation. (English) Zbl 1522.68234 Int. J. Theor. Phys. 60, No. 8, 2723-2732 (2021). MSC: 68Q12 68R10 81P65 PDFBibTeX XMLCite \textit{Y. Dong} et al., Int. J. Theor. Phys. 60, No. 8, 2723--2732 (2021; Zbl 1522.68234) Full Text: DOI
Limei, Guo; Yingbin, Zhu; Duan, Huang A fingerprint minutiae extraction method in quantum thinned binary image. (English) Zbl 1522.68236 Int. J. Theor. Phys. 60, No. 5, 1883-1894 (2021). MSC: 68Q12 68U10 81P65 81P68 PDFBibTeX XMLCite \textit{G. Limei} et al., Int. J. Theor. Phys. 60, No. 5, 1883--1894 (2021; Zbl 1522.68236) Full Text: DOI
Sergioli, Giuseppe A matrix representation of quantum circuits over non-adjacent qudits. (English) Zbl 1523.81047 Int. J. Theor. Phys. 60, No. 2, 515-533 (2021). MSC: 81P68 68Q06 81P10 81P65 PDFBibTeX XMLCite \textit{G. Sergioli}, Int. J. Theor. Phys. 60, No. 2, 515--533 (2021; Zbl 1523.81047) Full Text: DOI arXiv
Takahashi, Yasuhiro; Takeuchi, Yuki; Tani, Seiichiro Classically simulating quantum circuits with local depolarizing noise. (English) Zbl 1514.81100 Theor. Comput. Sci. 893, 117-132 (2021). MSC: 81P68 68Q12 81P65 PDFBibTeX XMLCite \textit{Y. Takahashi} et al., Theor. Comput. Sci. 893, 117--132 (2021; Zbl 1514.81100) Full Text: DOI arXiv
Wallin, Mathias; Dalklint, Anna; Tortorelli, Daniel Topology optimization of bistable elastic structures – an application to logic gates. (English) Zbl 1506.74302 Comput. Methods Appl. Mech. Eng. 383, Article ID 113912, 18 p. (2021). MSC: 74P15 68Q06 PDFBibTeX XMLCite \textit{M. Wallin} et al., Comput. Methods Appl. Mech. Eng. 383, Article ID 113912, 18 p. (2021; Zbl 1506.74302) 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
Hatano, Naoya; Ikeda, Masahiro; Ishikawa, Isao; Sawano, Yoshihiro A global universality of two-layer neural networks with ReLU activations. (English) Zbl 1480.41006 J. Funct. Spaces 2021, Article ID 6637220, 3 p. (2021). MSC: 41A30 68Q06 68T05 PDFBibTeX XMLCite \textit{N. Hatano} et al., J. Funct. Spaces 2021, Article ID 6637220, 3 p. (2021; Zbl 1480.41006) Full Text: DOI arXiv
Fiorini, Samuel; Huynh, Tony; Weltge, Stefan Strengthening convex relaxations of 0/1-sets using Boolean formulas. (English) Zbl 1478.90060 Math. Program. 190, No. 1-2 (A), 467-482 (2021). MSC: 90C10 90C25 68Q06 PDFBibTeX XMLCite \textit{S. Fiorini} et al., Math. Program. 190, No. 1--2 (A), 467--482 (2021; Zbl 1478.90060) Full Text: DOI arXiv
Mahzoon, Alireza; Große, Daniel; Drechsler, Rolf Genmul: generating architecturally complex multipliers to challenge formal verification tools. (English) Zbl 07410746 Drechsler, Rolf (ed.) et al., Recent findings in Boolean techniques. Selected papers from the 14th international workshop on Boolean problems, IWSBP, virtual, September 24–25, 2020. Cham: Springer. 177-191 (2021). MSC: 68Q60 68Q06 94C11 PDFBibTeX XMLCite \textit{A. Mahzoon} et al., in: Recent findings in Boolean techniques. Selected papers from the 14th international workshop on Boolean problems, IWSBP, virtual, September 24--25, 2020. Cham: Springer. 177--191 (2021; Zbl 07410746) Full Text: DOI
Moraga, Claudio Hybrid control of Toffoli and Peres gates. (English) Zbl 07410745 Drechsler, Rolf (ed.) et al., Recent findings in Boolean techniques. Selected papers from the 14th international workshop on Boolean problems, IWSBP, virtual, September 24–25, 2020. Cham: Springer. 167-175 (2021). MSC: 68Q06 94C11 PDFBibTeX XMLCite \textit{C. Moraga}, in: Recent findings in Boolean techniques. Selected papers from the 14th international workshop on Boolean problems, IWSBP, virtual, September 24--25, 2020. Cham: Springer. 167--175 (2021; Zbl 07410745) Full Text: DOI
Miller, D. Michael; Dueck, Gerhard W. Translation techniques for reversible circuit synthesis with positive and negative controls. (English) Zbl 07410744 Drechsler, Rolf (ed.) et al., Recent findings in Boolean techniques. Selected papers from the 14th international workshop on Boolean problems, IWSBP, virtual, September 24–25, 2020. Cham: Springer. 143-165 (2021). MSC: 68Q06 94C11 PDFBibTeX XMLCite \textit{D. M. Miller} and \textit{G. W. Dueck}, in: Recent findings in Boolean techniques. Selected papers from the 14th international workshop on Boolean problems, IWSBP, virtual, September 24--25, 2020. Cham: Springer. 143--165 (2021; Zbl 07410744) Full Text: DOI
Kaufmann, Daniela Formal verification of integer multiplier circuits using algebraic reasoning: a survey. (English) Zbl 07410738 Drechsler, Rolf (ed.) et al., Recent findings in Boolean techniques. Selected papers from the 14th international workshop on Boolean problems, IWSBP, virtual, September 24–25, 2020. Cham: Springer. 1-27 (2021). MSC: 68V15 68Q06 PDFBibTeX XMLCite \textit{D. Kaufmann}, in: Recent findings in Boolean techniques. Selected papers from the 14th international workshop on Boolean problems, IWSBP, virtual, September 24--25, 2020. Cham: Springer. 1--27 (2021; Zbl 07410738) Full Text: DOI
Aluf-Medina, Michelle; Korten, Till; Raviv, Avraham; Nicolau, Dan V. jun.; Kugler, Hillel Formal semantics and verification of network-based biocomputation circuits. (English) Zbl 1472.68057 Henglein, Fritz (ed.) et al., Verification, model checking, and abstract interpretation. 22nd international conference, VMCAI 2021, Copenhagen, Denmark, January 17–19, 2021. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12597, 464-485 (2021). MSC: 68Q07 68Q06 68Q55 68Q60 PDFBibTeX XMLCite \textit{M. Aluf-Medina} et al., Lect. Notes Comput. Sci. 12597, 464--485 (2021; Zbl 1472.68057) Full Text: DOI
Korneev, S. A. The complexity of implementation of a system of monomials in two variables by composition circuits. (Russian. English summary) Zbl 1528.68106 Prikl. Diskretn. Mat. 2021, No. 53, 103-119 (2021). MSC: 68Q06 PDFBibTeX XMLCite \textit{S. A. Korneev}, Prikl. Diskretn. Mat. 2021, No. 53, 103--119 (2021; Zbl 1528.68106) Full Text: DOI MNR
Alves, Mateus Rodrigues; de Oliveira Oliveira, Mateus; Nascimento Silva, Janio Carlos; dos Santos Souza, Uéverton Succinct certification of monotone circuits. (English) Zbl 1514.68075 Theor. Comput. Sci. 889, 1-13 (2021). MSC: 68Q06 68Q27 94C11 PDFBibTeX XMLCite \textit{M. R. Alves} et al., Theor. Comput. Sci. 889, 1--13 (2021; Zbl 1514.68075) Full Text: DOI
Morizumi, Hiroki On the power of nondeterministic circuits and co-nondeterministic circuits. (English) Zbl 07405981 Leporati, Alberto (ed.) et al., Language and automata theory and applications. 15th international conference, LATA 2021, Milan, Italy, March 1–5, 2021. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12638, 109-117 (2021). MSC: 68Q45 PDFBibTeX XMLCite \textit{H. Morizumi}, Lect. Notes Comput. Sci. 12638, 109--117 (2021; Zbl 07405981) Full Text: DOI
Pathak, Jaideep; Ott, Edward Reservoir computing for forecasting large spatiotemporal dynamical systems. (English) Zbl 1482.68203 Nakajima, Kohei (ed.) et al., Reservoir computing. Theory, physical implementations, and applications. Singapore: Springer. Nat. Comput. Ser., 117-138 (2021). MSC: 68T05 37D45 68Q06 PDFBibTeX XMLCite \textit{J. Pathak} and \textit{E. Ott}, in: Reservoir computing. Theory, physical implementations, and applications. Singapore: Springer. 117--138 (2021; Zbl 1482.68203) Full Text: DOI
Inubushi, Masanobu; Yoshimura, Kazuyuki; Ikeda, Yoshiaki; Nagasawa, Yuto On the characteristics and structures of dynamical systems suitable for reservoir computing. (English) Zbl 1482.68201 Nakajima, Kohei (ed.) et al., Reservoir computing. Theory, physical implementations, and applications. Singapore: Springer. Nat. Comput. Ser., 97-116 (2021). MSC: 68T05 37N99 68Q06 PDFBibTeX XMLCite \textit{M. Inubushi} et al., in: Reservoir computing. Theory, physical implementations, and applications. Singapore: Springer. 97--116 (2021; Zbl 1482.68201) Full Text: DOI
Gallicchio, Claudio; Micheli, Alessio Deep reservoir computing. (English) Zbl 1482.68212 Nakajima, Kohei (ed.) et al., Reservoir computing. Theory, physical implementations, and applications. Singapore: Springer. Nat. Comput. Ser., 77-95 (2021). MSC: 68T07 68Q06 PDFBibTeX XMLCite \textit{C. Gallicchio} and \textit{A. Micheli}, in: Reservoir computing. Theory, physical implementations, and applications. Singapore: Springer. 77--95 (2021; Zbl 1482.68212) Full Text: DOI
Subramoney, Anand; Scherr, Franz; Maass, Wolfgang Reservoirs learn to learn. (English) Zbl 1482.68206 Nakajima, Kohei (ed.) et al., Reservoir computing. Theory, physical implementations, and applications. Singapore: Springer. Nat. Comput. Ser., 59-76 (2021). MSC: 68T05 68Q06 PDFBibTeX XMLCite \textit{A. Subramoney} et al., in: Reservoir computing. Theory, physical implementations, and applications. Singapore: Springer. 59--76 (2021; Zbl 1482.68206) Full Text: DOI arXiv
Allender, Eric Vaughan Jones, Kolmogorov complexity, and the new complexity landscape around circuit minimization. (English) Zbl 1528.68150 N. Z. J. Math. 52, 585-604 (2021). MSC: 68Q30 68Q06 PDFBibTeX XMLCite \textit{E. Allender}, N. Z. J. Math. 52, 585--604 (2021; Zbl 1528.68150) Full Text: DOI
Koiran, Pascal; Skomra, Mateusz Derandomization and absolute reconstruction for sums of powers of linear forms. (English) Zbl 1483.13044 Theor. Comput. Sci. 887, 63-84 (2021). Reviewer: Alessandro Gimigliano (Bologna) MSC: 13P05 68Q06 12D05 12-08 15A69 68W30 68Q25 PDFBibTeX XMLCite \textit{P. Koiran} and \textit{M. Skomra}, Theor. Comput. Sci. 887, 63--84 (2021; Zbl 1483.13044) Full Text: DOI arXiv
Srinivasan, Srikanth; Tripathi, Utkarsh; Venkitesh, S. On the probabilistic degrees of symmetric Boolean functions. (English) Zbl 1527.68088 SIAM J. Discrete Math. 35, No. 3, 2070-2092 (2021). MSC: 68Q25 06E30 68Q06 68Q10 68Q17 PDFBibTeX XMLCite \textit{S. Srinivasan} et al., SIAM J. Discrete Math. 35, No. 3, 2070--2092 (2021; Zbl 1527.68088) Full Text: DOI arXiv
Dornemann, Jorin; Schrader, Rainer Cross-series-parallel digraphs. (English) Zbl 1477.05083 Discrete Appl. Math. 303, 57-65 (2021). Reviewer: Wai-Kai Chen (Fremont) MSC: 05C20 68Q06 06A99 PDFBibTeX XMLCite \textit{J. Dornemann} and \textit{R. Schrader}, Discrete Appl. Math. 303, 57--65 (2021; Zbl 1477.05083) Full Text: DOI
Bogdanov, Andrej; Ishai, Yuval; Srinivasan, Akshayaram Unconditionally secure computation against low-complexity leakage. (English) Zbl 1508.68112 J. Cryptology 34, No. 4, Paper No. 38, 28 p. (2021); correction ibid. 35, No. 1, Paper No. 2, 1 p. (2022); correction ibid. 35, No. 2, Paper No. 7, 34 p. (2022). MSC: 68Q10 68Q06 94A60 PDFBibTeX XMLCite \textit{A. Bogdanov} et al., J. Cryptology 34, No. 4, Paper No. 38, 28 p. (2021; Zbl 1508.68112) Full Text: DOI
Limaye, Nutan; Sreenivasaiah, Karteek; Srinivasan, Srikanth; Tripathi, Utkarsh; Venkitesh, S. A fixed-depth size-hierarchy theorem for \(\mathrm{AC}^0[\oplus]\) via the coin problem. (English) Zbl 1525.68045 SIAM J. Comput. 50, No. 4, 1461-1499 (2021). MSC: 68Q06 68Q15 68Q17 PDFBibTeX XMLCite \textit{N. Limaye} et al., SIAM J. Comput. 50, No. 4, 1461--1499 (2021; Zbl 1525.68045) Full Text: DOI
Sherstov, Alexander A.; Wu, Pei Near-optimal lower bounds on the threshold degree and sign-rank of \(\mathrm{AC}^0\). (English) Zbl 1528.68139 SIAM J. Comput. 50, No. 4, STOC19-1-STOC19-86 (2021). MSC: 68Q15 68Q06 68Q11 68Q17 PDFBibTeX XMLCite \textit{A. A. Sherstov} and \textit{P. Wu}, SIAM J. Comput. 50, No. 4, STOC19--1-STOC19--86 (2021; Zbl 1528.68139) Full Text: DOI arXiv
Atiyah, Michael; Marcolli, Matilde Anyon networks from geometric models of matter. (English) Zbl 1471.81107 Q. J. Math. 72, No. 1-2, 717-733 (2021). MSC: 81V27 57R18 18M15 93B27 68Q06 PDFBibTeX XMLCite \textit{M. Atiyah} and \textit{M. Marcolli}, Q. J. Math. 72, No. 1--2, 717--733 (2021; Zbl 1471.81107) Full Text: DOI
Xu, Zhiwei; Zhang, Jialin Computational thinking: a perspective on computer science. (English) Zbl 1490.68001 Singapore: Springer (ISBN 978-981-16-3847-3/hbk; 978-981-16-3848-0/ebook). xxvi, 319 p. (2021). Reviewer: Dieter Riebesehl (Lüneburg) MSC: 68-01 68M01 68M11 68N15 68P05 68P10 68Q04 68Q06 68Q15 68Q25 PDFBibTeX XMLCite \textit{Z. Xu} and \textit{J. Zhang}, Computational thinking: a perspective on computer science. Singapore: Springer (2021; Zbl 1490.68001) Full Text: DOI
Red’kin, N. P. Minimal contact circuits for a sequence of Boolean functions. (English. Russian original) Zbl 1497.94202 Math. Notes 110, No. 1, 156-158 (2021); translation from Mat. Zametki 110, No. 1, 155-157 (2021). Reviewer: Nikolay Kyurkchiev (Plovdiv) MSC: 94C11 68Q06 PDFBibTeX XMLCite \textit{N. P. Red'kin}, Math. Notes 110, No. 1, 156--158 (2021; Zbl 1497.94202); translation from Mat. Zametki 110, No. 1, 155--157 (2021) Full Text: DOI
Yusipov, I. I.; Volokitin, V. D.; Liniov, A. V.; Ivanchenko, M. V.; Meyerov, I. B.; Denisov, S. V. Machine learning versus semidefinite programming approach to a particular problem of the theory of open quantum systems. (English) Zbl 1470.81039 Lobachevskii J. Math. 42, No. 7, 1622-1629 (2021). MSC: 81S22 68T05 68T07 65Y20 68Q06 PDFBibTeX XMLCite \textit{I. I. Yusipov} et al., Lobachevskii J. Math. 42, No. 7, 1622--1629 (2021; Zbl 1470.81039) 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
Jeřábek, Emil On the complexity of the clone membership problem. (English) Zbl 1522.68240 Theory Comput. Syst. 65, No. 5, 839-868 (2021). MSC: 68Q25 06E30 08A40 68Q06 68Q17 PDFBibTeX XMLCite \textit{E. Jeřábek}, Theory Comput. Syst. 65, No. 5, 839--868 (2021; Zbl 1522.68240) Full Text: DOI arXiv
Allender, Eric; Ilango, Rahul; Vafa, Neekon The non-hardness of approximating circuit size. (English) Zbl 1522.68194 Theory Comput. Syst. 65, No. 3, 559-578 (2021). MSC: 68Q06 68Q17 68Q30 68W25 PDFBibTeX XMLCite \textit{E. Allender} et al., Theory Comput. Syst. 65, No. 3, 559--578 (2021; Zbl 1522.68194) Full Text: DOI Link
Rosenthal, Gregory Beating treewidth for average-case subgraph isomorphism. (English) Zbl 1515.68254 Algorithmica 83, No. 8, 2521-2551 (2021). MSC: 68R10 05C60 68Q06 68Q25 68Q27 PDFBibTeX XMLCite \textit{G. Rosenthal}, Algorithmica 83, No. 8, 2521--2551 (2021; Zbl 1515.68254) Full Text: DOI arXiv Link
Akbari-Nodehi, Hanzaleh; Maddah-Ali, Mohammad Ali Secure coded multi-party computation for massive matrix operations. (English) Zbl 1473.94036 IEEE Trans. Inf. Theory 67, No. 4, 2379-2398 (2021). MSC: 94A29 68Q06 PDFBibTeX XMLCite \textit{H. Akbari-Nodehi} and \textit{M. A. Maddah-Ali}, IEEE Trans. Inf. Theory 67, No. 4, 2379--2398 (2021; Zbl 1473.94036) Full Text: DOI arXiv
Slimen, Iyed Ben; Gueddana, Amor; Lakshminarayanan, Vasudevan Discrete-time quantum walk on circular graph: simulations and effect of gate depth and errors. (English) Zbl 1468.81028 Int. J. Quantum Inf. 19, No. 2, Article ID 2150008, 18 p. (2021). MSC: 81P65 81P68 68Q06 05C81 60G50 81P73 PDFBibTeX XMLCite \textit{I. B. Slimen} et al., Int. J. Quantum Inf. 19, No. 2, Article ID 2150008, 18 p. (2021; Zbl 1468.81028) Full Text: DOI
Bisht, Pranav; Saxena, Nitin Blackbox identity testing for sum of special ROABPs and its border class. (English) Zbl 1522.68239 Comput. Complexity 30, No. 1, Paper No. 8, 48 p. (2021). MSC: 68Q25 68Q06 68W20 68W30 PDFBibTeX XMLCite \textit{P. Bisht} and \textit{N. Saxena}, Comput. Complexity 30, No. 1, Paper No. 8, 48 p. (2021; Zbl 1522.68239) Full Text: DOI
Volk, Ben Lee; Kumar, Mrinal Lower bounds for matrix factorization. (English) Zbl 1518.68097 Comput. Complexity 30, No. 1, Paper No. 6, 40 p. (2021). MSC: 68Q06 15A23 68Q15 68Q17 PDFBibTeX XMLCite \textit{B. L. Volk} and \textit{M. Kumar}, Comput. Complexity 30, No. 1, Paper No. 6, 40 p. (2021; Zbl 1518.68097) Full Text: DOI arXiv
Sergeev, I. S. Formula complexity of a linear function in a \(k\)-ary basis. (English. Russian original) Zbl 1484.94046 Math. Notes 109, No. 3, 445-458 (2021); translation from Mat. Zametki 109, No. 3, 419-435 (2021). MSC: 94D10 68Q06 PDFBibTeX XMLCite \textit{I. S. Sergeev}, Math. Notes 109, No. 3, 445--458 (2021; Zbl 1484.94046); translation from Mat. Zametki 109, No. 3, 419--435 (2021) Full Text: DOI
Red’kin, N. P. Asymptotics for the complexity of Boolean functions with small number of ones. (English. Russian original) Zbl 1495.94173 Math. Notes 109, No. 2, 256-261 (2021); translation from Mat. Zametki 109, No. 2, 257-263 (2021). MSC: 94D10 94C11 PDFBibTeX XMLCite \textit{N. P. Red'kin}, Math. Notes 109, No. 2, 256--261 (2021; Zbl 1495.94173); translation from Mat. Zametki 109, No. 2, 257--263 (2021) Full Text: DOI
Arunachalam, Srinivasan; Grilo, Alex Bredariol; Sundaram, Aarthi Quantum hardness of learning shallow classical circuits. (English) Zbl 1516.68037 SIAM J. Comput. 50, No. 3, 972-1013 (2021). MSC: 68Q12 68Q06 68T05 81P68 81P94 PDFBibTeX XMLCite \textit{S. Arunachalam} et al., SIAM J. Comput. 50, No. 3, 972--1013 (2021; Zbl 1516.68037) Full Text: DOI arXiv
Korneev, Sergey A. On the complexity of implementation of a system of two monomials by composition circuits. (English. Russian original) Zbl 1499.68105 Discrete Math. Appl. 31, No. 2, 113-125 (2021); translation from Diskretn. Mat. 32, No. 2, 15-31 (2020). MSC: 68Q06 68R05 PDFBibTeX XMLCite \textit{S. A. Korneev}, Discrete Math. Appl. 31, No. 2, 113--125 (2021; Zbl 1499.68105); translation from Diskretn. Mat. 32, No. 2, 15--31 (2020)
Han, Xinyu; Zhao, Yi; Small, Michael Revisiting the memory capacity in reservoir computing of directed acyclic network. (English) Zbl 1459.68061 Chaos 31, No. 3, 033106, 10 p. (2021). MSC: 68Q06 68T05 PDFBibTeX XMLCite \textit{X. Han} et al., Chaos 31, No. 3, 033106, 10 p. (2021; Zbl 1459.68061) Full Text: DOI
Jukna, Stasys Notes on hazard-free circuits. (English) Zbl 1476.68084 SIAM J. Discrete Math. 35, No. 2, 770-787 (2021). MSC: 68Q06 68Q17 94C11 PDFBibTeX XMLCite \textit{S. Jukna}, SIAM J. Discrete Math. 35, No. 2, 770--787 (2021; Zbl 1476.68084) Full Text: DOI arXiv
Coudron, Matthew; Stark, Jalex; Vidick, Thomas Trading locality for time: certifiable randomness from low-depth circuits. (English) Zbl 1509.81249 Commun. Math. Phys. 382, No. 1, 49-86 (2021). MSC: 81P68 68Q12 68Q04 03D32 68Q06 81Q35 90C33 PDFBibTeX XMLCite \textit{M. Coudron} et al., Commun. Math. Phys. 382, No. 1, 49--86 (2021; Zbl 1509.81249) Full Text: DOI arXiv
Cantu, Angel A.; Luchsinger, Austin; Schweller, Robert; Wylie, Tim Covert computation in self-assembled circuits. (English) Zbl 1512.68091 Algorithmica 83, No. 2, 531-552 (2021). MSC: 68Q06 68Q07 68Q09 68Q17 PDFBibTeX XMLCite \textit{A. A. Cantu} et al., Algorithmica 83, No. 2, 531--552 (2021; Zbl 1512.68091) Full Text: DOI arXiv Link
Wäldchen, Stephan; Macdonald, Jan; Hauch, Sascha; Kutyniok, Gitta The computational complexity of understanding binary classifier decisions. (English) Zbl 1512.68116 J. Artif. Intell. Res. (JAIR) 70, 351-387 (2021). MSC: 68Q25 68Q06 68Q15 68T05 68W25 PDFBibTeX XMLCite \textit{S. Wäldchen} et al., J. Artif. Intell. Res. (JAIR) 70, 351--387 (2021; Zbl 1512.68116) Full Text: DOI arXiv
Drechsler, Rolf (ed.); Große, Daniel (ed.) Recent findings in Boolean techniques. Selected papers from the 14th international workshop on Boolean problems, IWSBP, virtual, September 24–25, 2020. (English) Zbl 1470.94002 Cham: Springer (ISBN 978-3-030-68070-1/hbk; 978-3-030-68073-2/pbk; 978-3-030-68071-8/ebook). vii, 197 p. (2021). MSC: 94-06 68-06 68Q06 94C11 94D10 00B25 PDFBibTeX XMLCite \textit{R. Drechsler} (ed.) and \textit{D. Große} (ed.), Recent findings in Boolean techniques. Selected papers from the 14th international workshop on Boolean problems, IWSBP, virtual, September 24--25, 2020. Cham: Springer (2021; Zbl 1470.94002) Full Text: DOI
Zakablukov, Dmitry V. On the dependence of the complexity and depth of reversible circuits consisting of NOT, CNOT, and 2-CNOT gates on the number of additional inputs. (English. Russian original) Zbl 1499.68107 Discrete Math. Appl. 31, No. 1, 61-75 (2021); translation from Diskretn. Mat. 32, No. 1, 8-26 (2020). MSC: 68Q06 PDFBibTeX XMLCite \textit{D. V. Zakablukov}, Discrete Math. Appl. 31, No. 1, 61--75 (2021; Zbl 1499.68107); translation from Diskretn. Mat. 32, No. 1, 8--26 (2020) Full Text: DOI
Deligkas, Argyrios; Fearnley, John; Melissourgos, Themistoklis; Spirakis, Paul G. Computing exact solutions of consensus halving and the Borsuk-Ulam theorem. (English) Zbl 1477.68115 J. Comput. Syst. Sci. 117, 75-98 (2021). MSC: 68Q17 55M20 68Q15 91B32 PDFBibTeX XMLCite \textit{A. Deligkas} et al., J. Comput. Syst. Sci. 117, 75--98 (2021; Zbl 1477.68115) Full Text: DOI arXiv Link
Takahashi, Yasuhiro; Tani, Seiichiro Power of uninitialized qubits in shallow quantum circuits. (English) Zbl 1480.81031 Theor. Comput. Sci. 851, 129-153 (2021). MSC: 81P68 68Q06 PDFBibTeX XMLCite \textit{Y. Takahashi} and \textit{S. Tani}, Theor. Comput. Sci. 851, 129--153 (2021; Zbl 1480.81031) Full Text: DOI Link
Durand, Arnaud; Haak, Anselm; Kontinen, Juha; Vollmer, Heribert Descriptive complexity of #P functions: a new perspective. (English) Zbl 1467.68060 J. Comput. Syst. Sci. 116, 40-54 (2021). MSC: 68Q19 68Q06 PDFBibTeX XMLCite \textit{A. Durand} et al., J. Comput. Syst. Sci. 116, 40--54 (2021; Zbl 1467.68060) Full Text: DOI Link
Li, Yaqiao Conflict complexity is lower bounded by block sensitivity. (English) Zbl 1477.68107 Theor. Comput. Sci. 856, 169-172 (2021). MSC: 68Q06 06E30 PDFBibTeX XMLCite \textit{Y. Li}, Theor. Comput. Sci. 856, 169--172 (2021; Zbl 1477.68107) Full Text: DOI arXiv
Shinagawa, Kazumasa; Nuida, Koji A single shuffle is enough for secure card-based computation of any Boolean circuit. (English) Zbl 1476.68086 Discrete Appl. Math. 289, 248-261 (2021). MSC: 68Q06 68Q09 94A60 PDFBibTeX XMLCite \textit{K. Shinagawa} and \textit{K. Nuida}, Discrete Appl. Math. 289, 248--261 (2021; Zbl 1476.68086) Full Text: DOI