Lackenby, Marc; Yazdi, Mehdi The computational complexity of knot genus in a fixed 3-manifold. (English) Zbl 07740440 Proc. Lond. Math. Soc. (3) 126, No. 3, 837-879 (2023). MSC: 57K31 57K30 68Q15 68Q17 57K10 PDF BibTeX XML Cite \textit{M. Lackenby} and \textit{M. Yazdi}, Proc. Lond. Math. Soc. (3) 126, No. 3, 837--879 (2023; Zbl 07740440) Full Text: DOI arXiv
Bournez, Olivier; Durand, Arnaud A characterization of functions over the integers computable in polynomial time using discrete ordinary differential equations. (English) Zbl 07727625 Comput. Complexity 32, No. 2, Paper No. 7, 49 p. (2023). MSC: 03D15 03D20 68Q01 68Q15 65Q10 65L99 PDF BibTeX XML Cite \textit{O. Bournez} and \textit{A. Durand}, Comput. Complexity 32, No. 2, Paper No. 7, 49 p. (2023; Zbl 07727625) Full Text: DOI arXiv
Impagliazzo, Russell; Kabanets, Valentine; Volkovich, Ilya The power of natural properties as oracles. (English) Zbl 07727624 Comput. Complexity 32, No. 2, Paper No. 6, 40 p. (2023). MSC: 68Q06 68Q15 68Q17 68Q25 68Q32 PDF BibTeX XML Cite \textit{R. Impagliazzo} et al., Comput. Complexity 32, No. 2, Paper No. 6, 40 p. (2023; Zbl 07727624) Full Text: DOI
Yamada, Kaito; Ito, Noboru Automatic computation of crosscap number of alternating knots. (English) Zbl 07727223 JP J. Geom. Topol. 29, No. 1, 35-45 (2023). MSC: 57K10 68Q15 68Q17 PDF BibTeX XML Cite \textit{K. Yamada} and \textit{N. Ito}, JP J. Geom. Topol. 29, No. 1, 35--45 (2023; Zbl 07727223) Full Text: DOI arXiv
Müller, Moritz [Krajìček, Jan] Book review of: J. Krajìček, Proof complexity. (English) Zbl 07725107 Bull. Symb. Log. 29, No. 2, 296-297 (2023). MSC: 00A17 03-02 03F20 68Q15 PDF BibTeX XML Cite \textit{M. Müller}, Bull. Symb. Log. 29, No. 2, 296--297 (2023; Zbl 07725107) Full Text: DOI
Ogihara, M.; Uchizawa, K. Synchronous Boolean finite dynamical systems on directed graphs over XOR functions. (English) Zbl 07719398 Theory Comput. Syst. 67, No. 3, 569-591 (2023). MSC: 68Q15 68Q25 PDF BibTeX XML Cite \textit{M. Ogihara} and \textit{K. Uchizawa}, Theory Comput. Syst. 67, No. 3, 569--591 (2023; Zbl 07719398) Full Text: DOI
Nandakumar, Satyadev; Pulari, Subin Ergodic theorems and converses for PSPACE functions. (English) Zbl 07719395 Theory Comput. Syst. 67, No. 3, 491-520 (2023). MSC: 03D32 68Q30 68Q15 PDF BibTeX XML Cite \textit{S. Nandakumar} and \textit{S. Pulari}, Theory Comput. Syst. 67, No. 3, 491--520 (2023; Zbl 07719395) Full Text: DOI
Gazdag, Zsolt; Hajagos, Károly A characterisation of P by DLOGTIME-uniform families of polarizationless P systems using only dissolution rules. (English) Zbl 1512.68094 Theor. Comput. Sci. 965, Article ID 113974, 18 p. (2023). MSC: 68Q07 68Q15 PDF BibTeX XML Cite \textit{Z. Gazdag} and \textit{K. Hajagos}, Theor. Comput. Sci. 965, Article ID 113974, 18 p. (2023; Zbl 1512.68094) Full Text: DOI
Dobbins, Michael Gene; Kleist, Linda; Miltzow, Tillmann; Rzążewski, Paweł Completeness for the complexity class \(\forall \exists \mathbb{R}\) and area-universality. (English) Zbl 07694927 Discrete Comput. Geom. 70, No. 1, 154-188 (2023). MSC: 68Q15 05C62 05C10 14P99 68R10 68Q17 PDF BibTeX XML Cite \textit{M. G. Dobbins} et al., Discrete Comput. Geom. 70, No. 1, 154--188 (2023; Zbl 07694927) Full Text: DOI arXiv
Grochow, Joshua; Qiao, Youming On the complexity of isomorphism problems for tensors, groups, and polynomials. I: Tensor isomorphism-completeness. (English) Zbl 07680601 SIAM J. Comput. 52, No. 2, 568-617 (2023). MSC: 68Q15 81P45 68Q17 PDF BibTeX XML Cite \textit{J. Grochow} and \textit{Y. Qiao}, SIAM J. Comput. 52, No. 2, 568--617 (2023; Zbl 07680601) Full Text: DOI
Sherstov, Alexander A.; Storozhenko, Andrey A.; Wu, Pei An optimal separation of randomized and quantum query complexity. (English) Zbl 07680600 SIAM J. Comput. 52, No. 2, 525-567 (2023). MSC: 68Q12 68Q17 68Q15 81P45 PDF BibTeX XML Cite \textit{A. A. Sherstov} et al., SIAM J. Comput. 52, No. 2, 525--567 (2023; Zbl 07680600) Full Text: DOI arXiv
Filos-Ratsikas, Aris; Hollender, Alexandros; Sotiraki, Katerina; Zampetakis, Manolis Consensus-halving: does it ever get easier? (English) Zbl 07680597 SIAM J. Comput. 52, No. 2, 412-451 (2023). MSC: 68Q25 68Q15 91B32 PDF BibTeX XML Cite \textit{A. Filos-Ratsikas} et al., SIAM J. Comput. 52, No. 2, 412--451 (2023; Zbl 07680597) Full Text: DOI arXiv
Kush, Deepanshu; Rossman, Benjamin Tree-depth and the formula complexity of subgraph isomorphism. (English) Zbl 07672230 SIAM J. Comput. 52, No. 1, 273-325 (2023). MSC: 68Q06 68Q15 68Q17 PDF BibTeX XML Cite \textit{D. Kush} and \textit{B. Rossman}, SIAM J. Comput. 52, No. 1, 273--325 (2023; Zbl 07672230) Full Text: DOI arXiv
Bok, Jan; Brewster, Richard; Feder, Tomás; Hell, Pavol; Jedličková, Nikola List homomorphism problems for signed trees. (English) Zbl 1506.05082 Discrete Math. 346, No. 3, Article ID 113257, 24 p. (2023). MSC: 05C22 05C05 68Q15 05C60 PDF BibTeX XML Cite \textit{J. Bok} et al., Discrete Math. 346, No. 3, Article ID 113257, 24 p. (2023; Zbl 1506.05082) Full Text: DOI
Cardona, Robert; Miranda, Eva; Peralta-Salas, Daniel Computability and Beltrami fields in Euclidean space. (English. French summary) Zbl 1504.35246 J. Math. Pures Appl. (9) 169, 50-81 (2023). MSC: 35Q31 76B03 68Q04 68Q15 35A10 35G60 35A01 37B40 58C40 PDF BibTeX XML Cite \textit{R. Cardona} et al., J. Math. Pures Appl. (9) 169, 50--81 (2023; Zbl 1504.35246) Full Text: DOI arXiv
Ito, Tetsuya A quantitative Birman-Menasco finiteness theorem and its application to crossing number. (English) Zbl 07738264 J. Topol. 15, No. 4, 1794-1806 (2022). MSC: 57K10 57K31 68Q15 PDF BibTeX XML Cite \textit{T. Ito}, J. Topol. 15, No. 4, 1794--1806 (2022; Zbl 07738264) Full Text: DOI arXiv
Alhazov, Artiom; Leporati, Alberto; Manzoni, Luca; Mauri, Giancarlo; Zandron, Claudio Evaluating space measures in P systems. (English) Zbl 07732469 J. Membr. Comput. 4, No. 3, 251-260 (2022). MSC: 68Q07 68Q15 68Q25 PDF BibTeX XML Cite \textit{A. Alhazov} et al., J. Membr. Comput. 4, No. 3, 251--260 (2022; Zbl 07732469) Full Text: DOI
Riscos-Núñez, Agustín; Valencia-Cabrera, Luis From SAT to SAT-UNSAT using P systems with dissolution rules. (English) Zbl 07731866 J. Membr. Comput. 4, No. 2, 97-106 (2022). MSC: 68Q07 68Q15 68R07 PDF BibTeX XML Cite \textit{A. Riscos-Núñez} and \textit{L. Valencia-Cabrera}, J. Membr. Comput. 4, No. 2, 97--106 (2022; Zbl 07731866) Full Text: DOI
De Brito, Vasco Boavida; Costa, José Félix; Poças, Diogo The power of machines that control experiments. (English) Zbl 07726975 Int. J. Found. Comput. Sci. 33, No. 2, 91-118 (2022). MSC: 68Q09 68Q04 68Q15 PDF BibTeX XML Cite \textit{V. B. De Brito} et al., Int. J. Found. Comput. Sci. 33, No. 2, 91--118 (2022; Zbl 07726975) Full Text: DOI
Waters, Brent; Wu, David J. Batch arguments for NP and more from standard bilinear group assumptions. (English) Zbl 1515.68143 Dodis, Yevgeniy (ed.) et al., Advances in cryptology – CRYPTO 2022. 42nd annual international cryptology conference, CRYPTO 2022, Santa Barbara, CA, USA, August 15–18, 2022. Proceedings. Part II. Cham: Springer. Lect. Notes Comput. Sci. 13508, 433-463 (2022). MSC: 68Q10 68Q15 94A60 PDF BibTeX XML Cite \textit{B. Waters} and \textit{D. J. Wu}, Lect. Notes Comput. Sci. 13508, 433--463 (2022; Zbl 1515.68143) Full Text: DOI
Landsberg, J. M. Secant varieties and the complexity of matrix multiplication. (English) Zbl 07689792 Rend. Ist. Mat. Univ. Trieste 54, Paper No. 11, 21 p. (2022). MSC: 68Q15 15A69 14L35 PDF BibTeX XML Cite \textit{J. M. Landsberg}, Rend. Ist. Mat. Univ. Trieste 54, Paper No. 11, 21 p. (2022; Zbl 07689792) Full Text: DOI arXiv Link
Komargodski, Ilan; Moran, Tal; Naor, Moni; Pass, Rafael; Rosen, Alon; Yogev, Eylon One-way functions and (im)perfect obfuscation. (English) Zbl 1512.68084 SIAM J. Comput. 51, No. 6, 1769-1795 (2022). MSC: 68P25 68N30 68Q15 68Q17 94A60 PDF BibTeX XML Cite \textit{I. Komargodski} et al., SIAM J. Comput. 51, No. 6, 1769--1795 (2022; Zbl 1512.68084) Full Text: DOI
Dal Lago, U. Implicit computation complexity in higher-order programming languages. A survey in memory of Martin Hofmann. (English) Zbl 1517.68075 Math. Struct. Comput. Sci. 32, No. 6, 760-776 (2022). MSC: 68N30 03B40 03F52 68N18 68Q15 68-02 PDF BibTeX XML Cite \textit{U. Dal Lago}, Math. Struct. Comput. Sci. 32, No. 6, 760--776 (2022; Zbl 1517.68075) Full Text: DOI
Lackenby, Marc Algorithms in 3-manifold theory. (English) Zbl 07647903 Agol, Ian (ed.) et al., Surveys in 3-manifold topology and geometry. Somerville, MA: International Press. Surv. Differ. Geom. 25, 163-213 (2022). Reviewer: Kristóf Huszár (Lyon) MSC: 57K30 68Q15 68Q17 57-02 PDF BibTeX XML Cite \textit{M. Lackenby}, Surv. Differ. Geom. 25, 163--213 (2022; Zbl 07647903) Full Text: arXiv
Koberda, Thomas Geometry and combinatorics via right-angled Artin groups. (English) Zbl 07632757 Ohshika, Ken’ichi (ed.) et al., In the tradition of Thurston II. Geometry and groups. Cham: Springer. 475-518 (2022). MSC: 20F36 20F65 05C50 05C45 05C48 05C60 68Q15 03D15 PDF BibTeX XML Cite \textit{T. Koberda}, in: In the tradition of Thurston II. Geometry and groups. Cham: Springer. 475--518 (2022; Zbl 07632757) Full Text: DOI arXiv
Kołodziejczyk, Leszek Aleksander; Thapen, Neil Approximate counting and NP search problems. (English) Zbl 07632519 J. Math. Log. 22, No. 3, Article ID 2250012, 31 p. (2022). MSC: 03F30 03D15 68Q15 68Q17 03F20 PDF BibTeX XML Cite \textit{L. A. Kołodziejczyk} and \textit{N. Thapen}, J. Math. Log. 22, No. 3, Article ID 2250012, 31 p. (2022; Zbl 07632519) Full Text: DOI arXiv
Downey, Rod; Harrison-Trainor, Matthew A minimal set low for speed. (English) Zbl 07620706 J. Symb. Log. 87, No. 4, 1693-1728 (2022). MSC: 03D28 68Q15 PDF BibTeX XML Cite \textit{R. Downey} and \textit{M. Harrison-Trainor}, J. Symb. Log. 87, No. 4, 1693--1728 (2022; Zbl 07620706) Full Text: DOI arXiv
Gharibian, Sevag; Santha, Miklos; Sikora, Jamie; Sundaram, Aarthi; Yirka, Justin Quantum generalizations of the polynomial hierarchy with applications to \(\mathrm{QMA(2)}\). (English) Zbl 1512.68101 Comput. Complexity 31, No. 2, Paper No. 13, 52 p. (2022). MSC: 68Q12 68Q15 81P68 90C22 PDF BibTeX XML Cite \textit{S. Gharibian} et al., Comput. Complexity 31, No. 2, Paper No. 13, 52 p. (2022; Zbl 1512.68101) Full Text: DOI
Kumar, Mrinal; Volk, Ben Lee A lower bound on determinantal complexity. (English) Zbl 07605015 Comput. Complexity 31, No. 2, Paper No. 12, 20 p. (2022). MSC: 68Q06 68Q15 68Q17 PDF BibTeX XML Cite \textit{M. Kumar} and \textit{B. L. Volk}, Comput. Complexity 31, No. 2, Paper No. 12, 20 p. (2022; Zbl 07605015) Full Text: DOI arXiv
Dal Lago, Ugo; Kahle, Reinhard; Oitavem, Isabel Implicit recursion-theoretic characterizations of counting classes. (English) Zbl 1506.03096 Arch. Math. Logic 61, No. 7-8, 1129-1144 (2022). Reviewer: Marat M. Arslanov (Kazan) MSC: 03D15 68Q15 PDF BibTeX XML Cite \textit{U. Dal Lago} et al., Arch. Math. Logic 61, No. 7--8, 1129--1144 (2022; Zbl 1506.03096) Full Text: DOI
Bootle, Jonathan; Chiesa, Alessandro; Liu, Siqi Zero-knowledge IOPs with linear-time prover and polylogarithmic-time verifier. (English) Zbl 1496.94028 Dunkelman, Orr (ed.) et al., Advances in cryptology – EUROCRYPT 2022. 41st annual international conference on the theory and applications of cryptographic techniques, Trondheim, Norway, May 30 – June 3, 2022. Proceedings. Part II. Cham: Springer. Lect. Notes Comput. Sci. 13276, 275-304 (2022). MSC: 94A60 68P25 68Q15 PDF BibTeX XML Cite \textit{J. Bootle} et al., Lect. Notes Comput. Sci. 13276, 275--304 (2022; Zbl 1496.94028) Full Text: DOI
Arnon, Gal; Chiesa, Alessandro; Yogev, Eylon A PCP theorem for interactive proofs and applications. (English) Zbl 1497.68207 Dunkelman, Orr (ed.) et al., Advances in cryptology – EUROCRYPT 2022. 41st annual international conference on the theory and applications of cryptographic techniques, Trondheim, Norway, May 30 – June 3, 2022. Proceedings. Part II. Cham: Springer. Lect. Notes Comput. Sci. 13276, 64-94 (2022). MSC: 68Q10 68Q11 68Q15 94A60 PDF BibTeX XML Cite \textit{G. Arnon} et al., Lect. Notes Comput. Sci. 13276, 64--94 (2022; Zbl 1497.68207) Full Text: DOI
Khaniki, Erfan New relations and separations of conjectures about incompleteness in the finite domain. (English) Zbl 07576892 J. Symb. Log. 87, No. 3, 912-937 (2022). MSC: 03F20 03D15 68Q15 03F30 03F40 68Q17 PDF BibTeX XML Cite \textit{E. Khaniki}, J. Symb. Log. 87, No. 3, 912--937 (2022; Zbl 07576892) Full Text: DOI arXiv
Chatterjee, Prerona; Kumar, Mrinal; She, Adrian; Lee Volk, Ben Quadratic lower bounds for algebraic branching programs and formulas. (English) Zbl 07565467 Comput. Complexity 31, No. 2, Paper No. 8, 54 p. (2022). MSC: 68Q06 68Q15 68Q17 PDF BibTeX XML Cite \textit{P. Chatterjee} et al., Comput. Complexity 31, No. 2, Paper No. 8, 54 p. (2022; Zbl 07565467) Full Text: DOI arXiv Backlinks: MO
Wu, Xinyu A stochastic calculus approach to the oracle separation of \(\mathsf{BQP}\) and \(\mathsf{PH} \). (English) Zbl 07563819 Theory Comput. 18, Paper No. 17, 11 p. (2022). MSC: 68Qxx 68Q15 81P68 PDF BibTeX XML Cite \textit{X. Wu}, Theory Comput. 18, Paper No. 17, 11 p. (2022; Zbl 07563819) Full Text: DOI arXiv
Leshkowitz, Maya Round complexity versus randomness complexity in interactive proofs. (English) Zbl 07563815 Theory Comput. 18, Paper No. 13, 65 p. (2022). MSC: 68Qxx 68Q10 68Q15 68Q87 PDF BibTeX XML Cite \textit{M. Leshkowitz}, Theory Comput. 18, Paper No. 13, 65 p. (2022; Zbl 07563815) Full Text: DOI
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 PDF BibTeX XML Cite \textit{A. Chattopadhyay} and \textit{N. S. Mande}, SIAM J. Comput. 51, No. 3, 820--848 (2022; Zbl 1502.68124) Full Text: DOI
Kaiser, Marcus Computation of dynamic equilibria in series-parallel networks. (English) Zbl 1491.90026 Math. Oper. Res. 47, No. 1, 50-71 (2022). MSC: 90B10 90B15 90B22 68Q15 05C21 PDF BibTeX XML Cite \textit{M. Kaiser}, Math. Oper. Res. 47, No. 1, 50--71 (2022; Zbl 1491.90026) Full Text: DOI arXiv
Ikenmeyer, Christian; Sanyal, Abhiroop A note on VNP-completeness and border complexity. (English) Zbl 07504765 Inf. Process. Lett. 176, Article ID 106243, 8 p. (2022). MSC: 68Q15 PDF BibTeX XML Cite \textit{C. Ikenmeyer} and \textit{A. Sanyal}, Inf. Process. Lett. 176, Article ID 106243, 8 p. (2022; Zbl 07504765) Full Text: DOI arXiv
Gillibert, Pierre; Jonušas, Julius; Kompatscher, Michael; Mottet, Antoine; Pinsker, Michael When symmetries are not enough: a hierarchy of hard constraint satisfaction problems. (English) Zbl 1483.68141 SIAM J. Comput. 51, No. 2, 175-213 (2022). MSC: 68Q15 03C05 03C35 08A40 08A70 68R07 PDF BibTeX XML Cite \textit{P. Gillibert} et al., SIAM J. Comput. 51, No. 2, 175--213 (2022; Zbl 1483.68141) Full Text: DOI arXiv
Wu, Huishan The computational complexity of module socles. (English) Zbl 07501983 Ann. Pure Appl. Logic 173, No. 5, Article ID 103089, 11 p. (2022). MSC: 03D15 03D80 68Q15 68Q17 PDF BibTeX XML Cite \textit{H. Wu}, Ann. Pure Appl. Logic 173, No. 5, Article ID 103089, 11 p. (2022; Zbl 07501983) Full Text: DOI
Carvalho, Catarina; Martin, Barnaby The lattice and semigroup structure of multipermutations. (English) Zbl 07492582 Int. J. Algebra Comput. 32, No. 2, 211-235 (2022). MSC: 06B05 68Q15 20M10 03C05 PDF BibTeX XML Cite \textit{C. Carvalho} and \textit{B. Martin}, Int. J. Algebra Comput. 32, No. 2, 211--235 (2022; Zbl 07492582) Full Text: DOI arXiv
Filos-Ratsikas, Aris; Goldberg, Paul W. The complexity of necklace splitting, consensus-halving, and discrete ham sandwich. (English) Zbl 07488094 SIAM J. Comput. 51, No. 1, STOC19-200-STOC19-268 (2022). MSC: 68Q15 68Q17 68R05 PDF BibTeX XML Cite \textit{A. Filos-Ratsikas} and \textit{P. W. Goldberg}, SIAM J. Comput. 51, No. 1, STOC19--200-STOC19--268 (2022; Zbl 07488094) Full Text: DOI
Oitavem, Isabel The polynomial hierarchy of functions and its levels. (English) Zbl 07450579 Theor. Comput. Sci. 900, 25-34 (2022). MSC: 68Q15 03D15 PDF BibTeX XML Cite \textit{I. Oitavem}, Theor. Comput. Sci. 900, 25--34 (2022; Zbl 07450579) Full Text: DOI
Modanese, Augusto Sublinear-time language recognition and decision by one-dimensional cellular automata. (English) Zbl 07726954 Int. J. Found. Comput. Sci. 32, No. 6, 713-731 (2021). MSC: 68Q80 68Q15 68Q25 68Q45 PDF BibTeX XML Cite \textit{A. Modanese}, Int. J. Found. Comput. Sci. 32, No. 6, 713--731 (2021; Zbl 07726954) Full Text: DOI
Dachman-Soled, Dana; Gong, Huijing; Kippen, Hunter; Shahverdi, Aria BKW meets Fourier new algorithms for LPN with sparse parities. (English) Zbl 1511.94083 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, 658-688 (2021). MSC: 94A60 68Q15 PDF BibTeX XML Cite \textit{D. Dachman-Soled} et al., Lect. Notes Comput. Sci. 13043, 658--688 (2021; Zbl 1511.94083) Full Text: DOI
Bürgisser, Peter (ed.); Dinur, Irit (ed.); Vadhan, Salil (ed.) Complexity theory. Abstracts from the workshop held November 14–20, 2021 (hybrid meeting). (English) Zbl 1506.00050 Oberwolfach Rep. 18, No. 4, 2955-3005 (2021). MSC: 00B05 00B25 68-06 68Q01 68Q17 68Q15 PDF BibTeX XML Cite \textit{P. Bürgisser} (ed.) et al., Oberwolfach Rep. 18, No. 4, 2955--3005 (2021; Zbl 1506.00050) Full Text: DOI
Ji, Zhengfeng; Natarajan, Anand; Vidick, Thomas; Wright, John; Yuen, Henry \(\mathrm{MIP}^*=\mathrm{RE}\). (English) Zbl 1503.68075 Commun. ACM 64, No. 11, 131-138 (2021). MSC: 68Q15 03D15 46L06 46L07 81P15 81P40 PDF BibTeX XML Cite \textit{Z. Ji} et al., Commun. ACM 64, No. 11, 131--138 (2021; Zbl 1503.68075) Full Text: DOI arXiv
Arenas, Marcelo; Croquevielle, Luis Alberto; Jayaram, Rajesh; Riveros, Cristian #NFA admits an FPRAS: efficient enumeration, counting, and uniform generation for logspace classes. (English) Zbl 1499.68124 J. ACM 68, No. 6, Paper No. 48, 40 p. (2021). MSC: 68Q15 68P15 68Q04 68Q25 68Q45 68W20 68W25 PDF BibTeX XML Cite \textit{M. Arenas} et al., J. ACM 68, No. 6, Paper No. 48, 40 p. (2021; Zbl 1499.68124) Full Text: DOI arXiv
Massar, Serge; Santha, Miklos Characterising the intersection of QMA and coQMA. (English) Zbl 1508.81501 Quantum Inf. Process. 20, No. 12, Paper No. 396, 48 p. (2021). MSC: 81P68 68Q15 PDF BibTeX XML Cite \textit{S. Massar} and \textit{M. Santha}, Quantum Inf. Process. 20, No. 12, Paper No. 396, 48 p. (2021; Zbl 1508.81501) Full Text: DOI
Choudhuri, Arka Rai; Jain, Abhishek; Jin, Zhengzhong Non-interactive batch arguments for NP from standard assumptions. (English) Zbl 1486.68079 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 IV. Cham: Springer. Lect. Notes Comput. Sci. 12828, 394-423 (2021). MSC: 68Q15 68Q10 94A60 PDF BibTeX XML Cite \textit{A. R. Choudhuri} et al., Lect. Notes Comput. Sci. 12828, 394--423 (2021; Zbl 1486.68079) Full Text: DOI
Chang, Jou-Ming; Kloks, Ton; Wang, Hung-Lung Gray codes for AT-free orders. (English) Zbl 07511525 Ars Comb. 155, 273-284 (2021). Reviewer: Geir Agnarsson (Fairfax) MSC: 05C75 06A05 68Q15 05C38 05C62 PDF BibTeX XML Cite \textit{J.-M. Chang} et al., Ars Comb. 155, 273--284 (2021; Zbl 07511525) Full Text: arXiv
Fogarasi, Kinga; Nagy, Benedek Notes of the NP-completeness of the membership problem of ET0L languages. (English) Zbl 1499.68161 C. R. Acad. Bulg. Sci. 74, No. 7, 964-971 (2021). Reviewer: Angela Slavova (Sofia) MSC: 68Q42 68Q10 68Q15 68Q17 68Q45 PDF BibTeX XML Cite \textit{K. Fogarasi} and \textit{B. Nagy}, C. R. Acad. Bulg. Sci. 74, No. 7, 964--971 (2021; Zbl 1499.68161) Full Text: DOI
Bünz, Benedikt; Chiesa, Alessandro; Lin, William; Mishra, Pratyush; Spooner, Nicholas Proof-carrying data without succinct arguments. (English) Zbl 1485.94066 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, 681-710 (2021). MSC: 94A60 68Q15 PDF BibTeX XML Cite \textit{B. Bünz} et al., Lect. Notes Comput. Sci. 12825, 681--710 (2021; Zbl 1485.94066) Full Text: DOI
Liu, Yanyi; Pass, Rafael On the possibility of basing cryptography on \(\mathsf{EXP}\ne \mathsf{BPP} \). (English) Zbl 1512.68120 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, 11-40 (2021). MSC: 68Q30 68P25 68Q15 68Q25 94A60 PDF BibTeX XML Cite \textit{Y. Liu} and \textit{R. Pass}, Lect. Notes Comput. Sci. 12825, 11--40 (2021; Zbl 1512.68120) Full Text: DOI
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 PDF BibTeX XML Cite \textit{P. Chaugule} et al., ACM Trans. Comput. Theory 13, No. 4, Article No. 21, 26 p. (2021; Zbl 1495.68060) Full Text: DOI
Krylatov, Alexander Equilibrium traffic flow assignment in a multi-subnet urban road network. (English) Zbl 1485.90020 Pardalos, Panos (ed.) et al., Mathematical optimization theory and operations research. 20th international conference, MOTOR 2021, Irkutsk, Russia, July 5–10, 2021. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12755, 3-16 (2021). MSC: 90B20 90B10 68Q15 90C30 90C35 PDF BibTeX XML Cite \textit{A. Krylatov}, Lect. Notes Comput. Sci. 12755, 3--16 (2021; Zbl 1485.90020) Full Text: DOI
Jonsson, Peter; Lagerkvist, Victor; Roy, Biman Fine-grained time complexity of constraint satisfaction problems. (English) Zbl 1495.68101 ACM Trans. Comput. Theory 13, No. 1, Article No. 2, 32 p. (2021). MSC: 68Q25 08A70 68Q15 68Q17 68Q27 68T20 PDF BibTeX XML Cite \textit{P. Jonsson} et al., ACM Trans. Comput. Theory 13, No. 1, Article No. 2, 32 p. (2021; Zbl 1495.68101) Full Text: DOI Link
Hitchcock, John M.; Sekoni, Adewale; Shafei, Hadi Polynomial-time random oracles and separating complexity classes. (English) Zbl 1495.68089 ACM Trans. Comput. Theory 13, No. 1, Article No. 1, 16 p. (2021). MSC: 68Q15 PDF BibTeX XML Cite \textit{J. M. Hitchcock} et al., ACM Trans. Comput. Theory 13, No. 1, Article No. 1, 16 p. (2021; Zbl 1495.68089) Full Text: DOI arXiv
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 PDF BibTeX XML Cite \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
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: 68Q17 68Q15 03F20 PDF BibTeX XML Cite \textit{M. A. Forbes} et al., Theory Comput. 17, Paper No. 10, 88 p. (2021; Zbl 07471587) Full Text: DOI
Kupriyanov, B. V.; Lazarev, A. A. Optimization of a recursive conveyor by reduction to a constraint satisfaction problem. (English. Russian original) Zbl 1481.90173 Autom. Remote Control 82, No. 11, 1892-1906 (2021); translation from Avtom. Telemekh. 2021, No. 11, 75-93 (2021). MSC: 90B35 68T20 91B32 68Q15 PDF BibTeX XML Cite \textit{B. V. Kupriyanov} and \textit{A. A. Lazarev}, Autom. Remote Control 82, No. 11, 1892--1906 (2021; Zbl 1481.90173); translation from Avtom. Telemekh. 2021, No. 11, 75--93 (2021) Full Text: DOI
Whyman, Richard Physical computational complexity and first-order logic. (English) Zbl 07413815 Fundam. Inform. 181, No. 2-3, 129-161 (2021). MSC: 03D10 03D15 03D78 68Q15 81P68 PDF BibTeX XML Cite \textit{R. Whyman}, Fundam. Inform. 181, No. 2--3, 129--161 (2021; Zbl 07413815) Full Text: DOI
Gavinsky, Dmitry The layer complexity of Arthur-Merlin-like communication. (English) Zbl 07413503 Theory Comput. 17, Paper No. 8, 28 p. (2021). MSC: 68Q15 68Qxx PDF BibTeX XML Cite \textit{D. Gavinsky}, Theory Comput. 17, Paper No. 8, 28 p. (2021; Zbl 07413503) Full Text: DOI arXiv
Bun, Mark; Thaler, Justin The large-error approximate degree of \(\mathrm{AC}^0\). (English) Zbl 07413502 Theory Comput. 17, Paper No. 7, 46 p. (2021). MSC: 68Q15 68Q17 68Q32 68Qxx PDF BibTeX XML Cite \textit{M. Bun} and \textit{J. Thaler}, Theory Comput. 17, Paper No. 7, 46 p. (2021; Zbl 07413502) Full Text: DOI
Alhazov, Artiom; Leporati, Alberto; Manzoni, Luca; Mauri, Giancarlo; Zandron, Claudio Alternative space definitions for P systems with active membranes. (English) Zbl 1469.68015 J. Membr. Comput. 3, No. 2, 87-96 (2021). MSC: 68Q07 68Q15 PDF BibTeX XML Cite \textit{A. Alhazov} et al., J. Membr. Comput. 3, No. 2, 87--96 (2021; Zbl 1469.68015) Full Text: DOI
Sherstov, Alexander A. The hardest halfspace. (English) Zbl 1508.68122 Comput. Complexity 30, No. 2, Paper No. 11, 85 p. (2021). MSC: 68Q17 68Q11 68Q15 PDF BibTeX XML Cite \textit{A. A. Sherstov}, Comput. Complexity 30, No. 2, Paper No. 11, 85 p. (2021; Zbl 1508.68122) Full Text: DOI arXiv
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 07393745 SIAM J. Comput. 50, No. 4, 1461-1499 (2021). MSC: 68Q15 68Q17 PDF BibTeX XML Cite \textit{N. Limaye} et al., SIAM J. Comput. 50, No. 4, 1461--1499 (2021; Zbl 07393745) Full Text: DOI
Sherstov, Alexander A.; Wu, Pei Near-optimal lower bounds on the threshold degree and sign-rank of \(AC^0\). (English) Zbl 07393741 SIAM J. Comput. 50, No. 4, STOC19-1-STOC19-86 (2021). MSC: 68Q15 68Q17 PDF BibTeX XML Cite \textit{A. A. Sherstov} and \textit{P. Wu}, SIAM J. Comput. 50, No. 4, STOC19--1-STOC19--86 (2021; Zbl 07393741) Full Text: DOI arXiv
Hollender, Alexandros The classes PPA-\(k\): existence from arguments modulo \(k\). (English) Zbl 1514.68083 Theor. Comput. Sci. 885, 15-29 (2021). MSC: 68Q15 68Q25 91B32 PDF BibTeX XML Cite \textit{A. Hollender}, Theor. Comput. Sci. 885, 15--29 (2021; Zbl 1514.68083) Full Text: DOI arXiv
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 97P10 PDF BibTeX XML Cite \textit{Z. Xu} and \textit{J. Zhang}, Computational thinking: a perspective on computer science. Singapore: Springer (2021; Zbl 1490.68001) Full Text: DOI
Volk, Ben Lee; Kumar, Mrinal Lower bounds for matrix factorization. (English) Zbl 07372271 Comput. Complexity 30, No. 1, Paper No. 6, 40 p. (2021). MSC: 68Q06 15A23 68Q15 68Q17 PDF BibTeX XML Cite \textit{B. L. Volk} and \textit{M. Kumar}, Comput. Complexity 30, No. 1, Paper No. 6, 40 p. (2021; Zbl 07372271) Full Text: DOI arXiv
Abascal, Jackson; Hemaspaandra, Lane A.; Maimon, Shir; Rubery, Daniel Closure and nonclosure properties of the classes of compressible and rankable sets. (English) Zbl 1515.68146 J. Comput. Syst. Sci. 120, 162-176 (2021). MSC: 68Q15 PDF BibTeX XML Cite \textit{J. Abascal} et al., J. Comput. Syst. Sci. 120, 162--176 (2021; Zbl 1515.68146) Full Text: DOI
Koenig, Dale; Tsvietkova, Anastasiia NP-hard problems naturally arising in knot theory. (English) Zbl 1468.57005 Trans. Am. Math. Soc., Ser. B 8, 420-441 (2021). MSC: 57K10 68Q15 68Q25 57-08 PDF BibTeX XML Cite \textit{D. Koenig} and \textit{A. Tsvietkova}, Trans. Am. Math. Soc., Ser. B 8, 420--441 (2021; Zbl 1468.57005) Full Text: DOI arXiv
Ishizuka, Takashi On the complexity of finding a Caristi’s fixed point. (English) Zbl 1516.68038 Inf. Process. Lett. 170, Article ID 106119, 7 p. (2021). MSC: 68Q15 47H10 68Q17 68Q25 PDF BibTeX XML Cite \textit{T. Ishizuka}, Inf. Process. Lett. 170, Article ID 106119, 7 p. (2021; Zbl 1516.68038) Full Text: DOI
Paradise, Orr Smooth and strong PCPs. (English) Zbl 1485.68101 Comput. Complexity 30, No. 1, Paper No. 1, 77 p. (2021); corrigendum ibid. 30, No. 1, Paper No. 9, 1 p. (2021). Reviewer: Arne Meier (Hannover) MSC: 68Q15 68Q10 68Q17 68W20 PDF BibTeX XML Cite \textit{O. Paradise}, Comput. Complexity 30, No. 1, Paper No. 1, 77 p. (2021; Zbl 1485.68101) Full Text: DOI
Biasse, Jean-François; Bonnetain, Xavier; Pring, Benjamin; Schrottenloher, André; Youmans, William A trade-off between classical and quantum circuit size for an attack against CSIDH. (English) Zbl 1464.94028 J. Math. Cryptol. 15, 4-17 (2021). MSC: 94A60 68Q12 68Q15 81P68 11Y16 14Q05 14G50 81P94 PDF BibTeX XML Cite \textit{J.-F. Biasse} et al., J. Math. Cryptol. 15, 4--17 (2021; Zbl 1464.94028) Full Text: DOI
Rybakov, Vladimir V. A short essay towards if P not equal NP. (English) Zbl 1516.68039 J. Sib. Fed. Univ., Math. Phys. 14, No. 2, 258-260 (2021). MSC: 68Q15 PDF BibTeX XML Cite \textit{V. V. Rybakov}, J. Sib. Fed. Univ., Math. Phys. 14, No. 2, 258--260 (2021; Zbl 1516.68039) Full Text: DOI MNR
Ferrarotti, Flavio; González, Senén; Turull Torres, José María; Van den Bussche, Jan; Virtema, Jonni Descriptive complexity of deterministic polylogarithmic time and space. (English) Zbl 1517.68140 J. Comput. Syst. Sci. 119, 145-163 (2021). Reviewer: Gregory Loren McColm (Tampa) MSC: 68Q19 03D10 03D15 68Q15 PDF BibTeX XML Cite \textit{F. Ferrarotti} et al., J. Comput. Syst. Sci. 119, 145--163 (2021; Zbl 1517.68140) Full Text: DOI arXiv
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 PDF BibTeX XML Cite \textit{S. Wäldchen} et al., J. Artif. Intell. Res. (JAIR) 70, 351--387 (2021; Zbl 1512.68116) Full Text: DOI arXiv
Hoza, William M.; Umans, Chris Targeted pseudorandom generators, simulation advice generators, and derandomizing logspace. (English) Zbl 1509.68094 SIAM J. Comput. 51, No. 2, STOC17-281-STOC17-304 (2022). MSC: 68Q15 68Q87 68W20 PDF BibTeX XML Cite \textit{W. M. Hoza} and \textit{C. Umans}, SIAM J. Comput. 51, No. 2, STOC17--281-STOC17--304 (2021; Zbl 1509.68094) Full Text: DOI
Tsatsomeros, Michael J.; Zhang, Yueqiao Faith The fibre of P-matrices: the recursive construction of all matrices with positive principal minors. (English) Zbl 1461.15036 Linear Multilinear Algebra 69, No. 2, 224-232 (2021). Reviewer: Francisco Marcellán (Leganes) MSC: 15B99 15A15 15A23 68Q15 PDF BibTeX XML Cite \textit{M. J. Tsatsomeros} and \textit{Y. F. Zhang}, Linear Multilinear Algebra 69, No. 2, 224--232 (2021; Zbl 1461.15036) 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 PDF BibTeX XML Cite \textit{A. Deligkas} et al., J. Comput. Syst. Sci. 117, 75--98 (2021; Zbl 1477.68115) Full Text: DOI arXiv Link
Aldi, Marco; de Beaudrap, Niel; Gharibian, Sevag; Saeedi, Seyran On efficiently solvable cases of quantum \(k\)-SAT. (English) Zbl 1462.81085 Commun. Math. Phys. 381, No. 1, 209-256 (2021). Reviewer: Eric Stachura (Marietta) MSC: 81Q10 81P68 68Q15 35P05 82B20 81P65 PDF BibTeX XML Cite \textit{M. Aldi} et al., Commun. Math. Phys. 381, No. 1, 209--256 (2021; Zbl 1462.81085) Full Text: DOI
Zdanowski, Konrad Truth definition for \(\Delta_0\) formulas and PSPACE computations. (English) Zbl 1496.03240 Fundam. Math. 252, No. 1, 1-38 (2021). Reviewer: Leszek Aleksander Kołodziejczyk (Warszawa) MSC: 03F30 03F35 68Q15 03D15 03F20 PDF BibTeX XML Cite \textit{K. Zdanowski}, Fundam. Math. 252, No. 1, 1--38 (2021; Zbl 1496.03240) Full Text: DOI
Watson, Thomas Quadratic simulations of Merlin-Arthur games. (English) Zbl 1499.68128 ACM Trans. Comput. Theory 12, No. 2, Article No. 14, 11 p. (2020). MSC: 68Q15 68Q11 PDF BibTeX XML Cite \textit{T. Watson}, ACM Trans. Comput. Theory 12, No. 2, Article No. 14, 11 p. (2020; Zbl 1499.68128) Full Text: DOI
Modanese, Augusto Sublinear-time language recognition and decision by one-dimensional cellular automata. (English) Zbl 07601075 Jonoska, Nataša (ed.) et al., Developments in language theory. 24th international conference, DLT 2020, Tampa, FL, USA, May 11–15, 2020. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12086, 251-265 (2020). MSC: 68Q80 68Q15 68Q25 68Q45 PDF BibTeX XML Cite \textit{A. Modanese}, Lect. Notes Comput. Sci. 12086, 251--265 (2020; Zbl 07601075) Full Text: DOI arXiv
Abrahão, Felipe S.; Wehmuth, Klaus; Ziviani, Artur On the existence of hidden machines in computational time hierarchies. (English) Zbl 1496.03164 de Barros, J. Acacio (ed.) et al., A true polymath. A tribute to Francisco Antonio Doria. Based on the meeting, Rio de Janeiro, Brazil, December 2018. [s.l.]: College Publications. Acad. Bras. Filos. 2, 113-121 (2020). MSC: 03D15 03D20 68Q15 PDF BibTeX XML Cite \textit{F. S. Abrahão} et al., Acad. Bras. Filos. 2, 113--121 (2020; Zbl 1496.03164) Full Text: arXiv
Yunis, Rafael; Argüelles, Carlos R.; Nacir, Diana López Boltzmann hierarchies for self-interacting warm dark matter scenarios. (English) Zbl 1493.83018 J. Cosmol. Astropart. Phys. 2020, No. 9, Paper No. 41, 48 p. (2020). MSC: 83C56 83F05 35B20 81V15 80A10 70S05 35Q20 68Q15 47A10 PDF BibTeX XML Cite \textit{R. Yunis} et al., J. Cosmol. Astropart. Phys. 2020, No. 9, Paper No. 41, 48 p. (2020; Zbl 1493.83018) Full Text: DOI arXiv Link
Watson, Thomas A \(\mathrm{ZPP}^{\mathrm{NP[1]}}\) lifting theorem. (English) Zbl 1495.68091 ACM Trans. Comput. Theory 12, No. 4, Article No. 27, 20 p. (2020). MSC: 68Q15 68Q11 68W20 PDF BibTeX XML Cite \textit{T. Watson}, ACM Trans. Comput. Theory 12, No. 4, Article No. 27, 20 p. (2020; Zbl 1495.68091) Full Text: DOI
Ganian, Robert; de Haan, Ronald; Kanj, Iyad; Szeider, Stefan On existential MSO and its relation to ETH. (English) Zbl 1495.68088 ACM Trans. Comput. Theory 12, No. 4, Article No. 22, 32 p. (2020). MSC: 68Q15 03B16 03B70 PDF BibTeX XML Cite \textit{R. Ganian} et al., ACM Trans. Comput. Theory 12, No. 4, Article No. 22, 32 p. (2020; Zbl 1495.68088) Full Text: DOI Link
Meeks, Kitty Book review of: J. MacCormick, What can be computed? A practical guide to the theory of computation. (English) Zbl 1480.00030 Lond. Math. Soc., Newsl. 2020, No. 490, 50-51 (2020). MSC: 00A17 68-01 68N15 68Q01 68Q04 68Q15 68Q17 68Q25 68Q45 PDF BibTeX XML Cite \textit{K. Meeks}, Lond. Math. Soc., Newsl. 2020, No. 490, 50--51 (2020; Zbl 1480.00030) Full Text: Link
Orellana-Martín, David; Riscos-Núñez, Agustín Seeking computational efficiency boundaries: the Păun’s conjecture. (English) Zbl 1469.68050 J. Membr. Comput. 2, No. 4, 323-331 (2020). MSC: 68Q07 68Q15 PDF BibTeX XML Cite \textit{D. Orellana-Martín} and \textit{A. Riscos-Núñez}, J. Membr. Comput. 2, No. 4, 323--331 (2020; Zbl 1469.68050) Full Text: DOI
Leporati, Alberto; Manzoni, Luca; Mauri, Giancarlo; Porreca, Antonio E.; Zandron, Claudio Simulating counting oracles with cooperation. (English) Zbl 1469.68044 J. Membr. Comput. 2, No. 4, 303-310 (2020). MSC: 68Q07 68Q15 PDF BibTeX XML Cite \textit{A. Leporati} et al., J. Membr. Comput. 2, No. 4, 303--310 (2020; Zbl 1469.68044) Full Text: DOI
Hemaspaandra, Edith; Hemaspaandra, Lane A.; Spakowski, Holger; Watanabe, Osamu The robustness of LWPP and WPP, with an application to graph reconstruction. (English) Zbl 1503.68074 Comput. Complexity 29, No. 2, Paper No. 7, 49 p. (2020). MSC: 68Q15 68R10 PDF BibTeX XML Cite \textit{E. Hemaspaandra} et al., Comput. Complexity 29, No. 2, Paper No. 7, 49 p. (2020; Zbl 1503.68074) Full Text: DOI Link
Shchesnovich, V. S. On the classical complexity of sampling from quantum interference of indistinguishable bosons. (English) Zbl 1461.81149 Int. J. Quantum Inf. 18, No. 7, Article ID 2050044, 16 p. (2020). MSC: 81V73 81V80 81P68 68Q12 68Q15 PDF BibTeX XML Cite \textit{V. S. Shchesnovich}, Int. J. Quantum Inf. 18, No. 7, Article ID 2050044, 16 p. (2020; Zbl 1461.81149) Full Text: DOI arXiv
Dvir, Zeev; Liu, Allen Fourier and circulant matrices are not rigid. (English) Zbl 1477.68117 Theory Comput. 16, Paper No. 20, 48 p. (2020). MSC: 68Q17 15B99 68Q06 68Q15 68R05 PDF BibTeX XML Cite \textit{Z. Dvir} and \textit{A. Liu}, Theory Comput. 16, Paper No. 20, 48 p. (2020; Zbl 1477.68117) Full Text: DOI arXiv
Loomis, Samuel P.; Mahoney, John R.; Aghamohammadi, Cina; Crutchfield, James P. Optimizing quantum models of classical channels: the reverse Holevo problem. (English) Zbl 1460.81010 J. Stat. Phys. 181, No. 5, 1966-1985 (2020). MSC: 81P47 94A40 81P45 81P40 68Q15 PDF BibTeX XML Cite \textit{S. P. Loomis} et al., J. Stat. Phys. 181, No. 5, 1966--1985 (2020; Zbl 1460.81010) Full Text: DOI arXiv
Dean, Walter Erratum to: “Computational complexity theory and the philosophy of mathematics”. (English) Zbl 1453.68085 Philos. Math. (3) 28, No. 2, 290 (2020). MSC: 68Q15 00A30 PDF BibTeX XML Cite \textit{W. Dean}, Philos. Math. (3) 28, No. 2, 290 (2020; Zbl 1453.68085) Full Text: DOI
Gordeev, Lew; Haeusler, Edward Hermann Proof compression and NP versus PSPACE. II. (English) Zbl 1477.03246 Bull. Sect. Log., Univ. Łódź, Dep. Log. 49, No. 3, 213-230 (2020). MSC: 03F20 03D15 68Q15 PDF BibTeX XML Cite \textit{L. Gordeev} and \textit{E. H. Haeusler}, Bull. Sect. Log., Univ. Łódź, Dep. Log. 49, No. 3, 213--230 (2020; Zbl 1477.03246) Full Text: DOI