default search action
Search dblp for Publications
export results for "stream:journals/toct:"
@article{DBLP:journals/toct/GrochowQ24, author = {Joshua A. Grochow and Youming Qiao}, title = {On \emph{p}-Group Isomorphism: Search-to-Decision, Counting-to-Decision, and Nilpotency Class Reductions via Tensors}, journal = {{ACM} Trans. Comput. Theory}, volume = {16}, number = {1}, pages = {2:1--2:39}, year = {2024}, url = {https://doi.org/10.1145/3625308}, doi = {10.1145/3625308}, timestamp = {Mon, 01 Apr 2024 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/GrochowQ24.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/JansenW24, author = {Bart M. P. Jansen and Michal Wlodarczyk}, title = {Optimal Polynomial-Time Compression for Boolean Max {CSP}}, journal = {{ACM} Trans. Comput. Theory}, volume = {16}, number = {1}, pages = {4:1--4:20}, year = {2024}, url = {https://doi.org/10.1145/3624704}, doi = {10.1145/3624704}, timestamp = {Mon, 01 Apr 2024 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/JansenW24.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/KurpiszLM24, author = {Adam Kurpisz and Samuli Lepp{\"{a}}nen and Monaldo Mastrolilli}, title = {Tight Sum-of-squares Lower Bounds for Binary Polynomial2 Optimization Problems}, journal = {{ACM} Trans. Comput. Theory}, volume = {16}, number = {1}, pages = {3:1--3:16}, year = {2024}, url = {https://doi.org/10.1145/3626106}, doi = {10.1145/3626106}, timestamp = {Mon, 01 Apr 2024 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/KurpiszLM24.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/MontanaroS24, author = {Ashley Montanaro and Changpeng Shao}, title = {Quantum Communication Complexity of Linear Regression}, journal = {{ACM} Trans. Comput. Theory}, volume = {16}, number = {1}, pages = {1:1--1:30}, year = {2024}, url = {https://doi.org/10.1145/3625225}, doi = {10.1145/3625225}, timestamp = {Mon, 01 Apr 2024 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/MontanaroS24.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/ChatterjeeS23, author = {Prerona Chatterjee and Ramprasad Saptharishi}, title = {Constructing Faithful Homomorphisms over Fields of Finite Characteristic}, journal = {{ACM} Trans. Comput. Theory}, volume = {15}, number = {1-2}, pages = {1--19}, year = {2023}, url = {https://doi.org/10.1145/3580351}, doi = {10.1145/3580351}, timestamp = {Fri, 18 Aug 2023 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/ChatterjeeS23.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/Folwarczny23, author = {Luk'av{s} Folwarczn'y}, title = {On Protocols for Monotone Feasible Interpolation}, journal = {{ACM} Trans. Comput. Theory}, volume = {15}, number = {1-2}, pages = {1--17}, year = {2023}, url = {https://doi.org/10.1145/3583754}, doi = {10.1145/3583754}, timestamp = {Mon, 05 Feb 2024 00:00:00 +0100}, biburl = {https://dblp.org/rec/journals/toct/Folwarczny23.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/HamoudiM23, author = {Yassine Hamoudi and Fr{\'{e}}d{\'{e}}ric Magniez}, title = {Quantum Time-Space Tradeoff for Finding Multiple Collision Pairs}, journal = {{ACM} Trans. Comput. Theory}, volume = {15}, number = {1-2}, pages = {1--22}, year = {2023}, url = {https://doi.org/10.1145/3589986}, doi = {10.1145/3589986}, timestamp = {Thu, 31 Aug 2023 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/HamoudiM23.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/ArvindFKKR22, author = {Vikraman Arvind and Frank Fuhlbr{\"{u}}ck and Johannes K{\"{o}}bler and Sebastian Kuhnert and Gaurav Rattan}, title = {The Parameterized Complexity of Fixing Number and Vertex Individualization in Graphs}, journal = {{ACM} Trans. Comput. Theory}, volume = {14}, number = {2}, pages = {9:1--9:26}, year = {2022}, url = {https://doi.org/10.1145/3558077}, doi = {10.1145/3558077}, timestamp = {Mon, 28 Aug 2023 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/ArvindFKKR22.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/BartholdiFLW22, author = {Laurent Bartholdi and Michael Figelius and Markus Lohrey and Armin Wei{\ss}}, title = {Groups with ALOGTIME-hard Word Problems and PSPACE-complete Compressed Word Problems}, journal = {{ACM} Trans. Comput. Theory}, volume = {14}, number = {3-4}, pages = {1--41}, year = {2022}, url = {https://doi.org/10.1145/3569708}, doi = {10.1145/3569708}, timestamp = {Fri, 18 Aug 2023 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/BartholdiFLW22.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/DattaLNTW22, author = {Samir Datta and Nutan Limaye and Prajakta Nimbhorkar and Thomas Thierauf and Fabian Wagner}, title = {Planar Graph Isomorphism Is in Log-Space}, journal = {{ACM} Trans. Comput. Theory}, volume = {14}, number = {2}, pages = {8:1--8:33}, year = {2022}, url = {https://doi.org/10.1145/3543686}, doi = {10.1145/3543686}, timestamp = {Mon, 05 Dec 2022 00:00:00 +0100}, biburl = {https://dblp.org/rec/journals/toct/DattaLNTW22.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/FominGST22, author = {Fedor V. Fomin and Petr A. Golovach and Giannos Stamoulis and Dimitrios M. Thilikos}, title = {An Algorithmic Meta-Theorem for Graph Modification to Planarity and {FOL}}, journal = {{ACM} Trans. Comput. Theory}, volume = {14}, number = {3-4}, pages = {1--29}, year = {2022}, url = {https://doi.org/10.1145/3571278}, doi = {10.1145/3571278}, timestamp = {Fri, 18 Aug 2023 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/FominGST22.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/GalanisGW22, author = {Andreas Galanis and Heng Guo and Jiaheng Wang}, title = {Inapproximability of Counting Hypergraph Colourings}, journal = {{ACM} Trans. Comput. Theory}, volume = {14}, number = {3-4}, pages = {1--33}, year = {2022}, url = {https://doi.org/10.1145/3558554}, doi = {10.1145/3558554}, timestamp = {Fri, 18 Aug 2023 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/GalanisGW22.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/HuangV22, author = {Xuangui Huang and Emanuele Viola}, title = {Approximate Degree, Weight, and Indistinguishability}, journal = {{ACM} Trans. Comput. Theory}, volume = {14}, number = {1}, pages = {3:1--3:26}, year = {2022}, url = {https://doi.org/10.1145/3492338}, doi = {10.1145/3492338}, timestamp = {Wed, 18 May 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/HuangV22.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/LagerkvistW22, author = {Victor Lagerkvist and Magnus Wahlstr{\"{o}}m}, title = {The (Coarse) Fine-Grained Structure of NP-Hard {SAT} and {CSP} Problems}, journal = {{ACM} Trans. Comput. Theory}, volume = {14}, number = {1}, pages = {2:1--2:54}, year = {2022}, url = {https://doi.org/10.1145/3492336}, doi = {10.1145/3492336}, timestamp = {Thu, 28 Apr 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/LagerkvistW22.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/LeviPRV22, author = {Amit Levi and Ramesh Krishnan S. Pallavoor and Sofya Raskhodnikova and Nithin Varma}, title = {Erasure-Resilient Sublinear-Time Graph Algorithms}, journal = {{ACM} Trans. Comput. Theory}, volume = {14}, number = {1}, pages = {1:1--1:22}, year = {2022}, url = {https://doi.org/10.1145/3488250}, doi = {10.1145/3488250}, timestamp = {Fri, 07 Jun 2024 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/LeviPRV22.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/MagniezN22, author = {Fr{\'{e}}d{\'{e}}ric Magniez and Ashwin Nayak}, title = {Quantum Distributed Complexity of Set Disjointness on a Line}, journal = {{ACM} Trans. Comput. Theory}, volume = {14}, number = {1}, pages = {5:1--5:22}, year = {2022}, url = {https://doi.org/10.1145/3512751}, doi = {10.1145/3512751}, timestamp = {Mon, 18 Sep 2023 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/MagniezN22.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/NakajimaZ22, author = {Tamio{-}Vesa Nakajima and Stanislav Zivn{\'{y}}}, title = {Linearly Ordered Colourings of Hypergraphs}, journal = {{ACM} Trans. Comput. Theory}, volume = {14}, number = {3-4}, pages = {1--19}, year = {2022}, url = {https://doi.org/10.1145/3570909}, doi = {10.1145/3570909}, timestamp = {Fri, 18 Aug 2023 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/NakajimaZ22.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/RonR22, author = {Dana Ron and Asaf Rosin}, title = {Optimal Distribution-Free Sample-Based Testing of Subsequence-Freeness with One-Sided Error}, journal = {{ACM} Trans. Comput. Theory}, volume = {14}, number = {1}, pages = {4:1--4:31}, year = {2022}, url = {https://doi.org/10.1145/3512750}, doi = {10.1145/3512750}, timestamp = {Wed, 18 May 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/RonR22.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/SingerS22, author = {Noah Singer and Madhu Sudan}, title = {Point-hyperplane Incidence Geometry and the Log-rank Conjecture}, journal = {{ACM} Trans. Comput. Theory}, volume = {14}, number = {2}, pages = {7:1--7:16}, year = {2022}, url = {https://doi.org/10.1145/3543684}, doi = {10.1145/3543684}, timestamp = {Mon, 28 Aug 2023 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/SingerS22.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/VolkK22, author = {Ben Lee Volk and Mrinal Kumar}, title = {A Polynomial Degree Bound on Equations for Non-rigid Matrices and Small Linear Circuits}, journal = {{ACM} Trans. Comput. Theory}, volume = {14}, number = {2}, pages = {6:1--6:14}, year = {2022}, url = {https://doi.org/10.1145/3543685}, doi = {10.1145/3543685}, timestamp = {Mon, 28 Aug 2023 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/VolkK22.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/AmbainisKPVZ21, author = {Andris Ambainis and Martins Kokainis and Krisjanis Prusis and Jevgenijs Vihrovs and Aleksejs Zajakins}, title = {All Classical Adversary Methods Are Equivalent for Total Functions}, journal = {{ACM} Trans. Comput. Theory}, volume = {13}, number = {1}, pages = {7:1--7:20}, year = {2021}, url = {https://doi.org/10.1145/3442357}, doi = {10.1145/3442357}, timestamp = {Mon, 26 Apr 2021 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/AmbainisKPVZ21.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/ArunachalamCKSW21, author = {Srinivasan Arunachalam and Sourav Chakraborty and Michal Kouck{\'{y}} and Nitin Saurabh and Ronald de Wolf}, title = {Improved Bounds on Fourier Entropy and Min-entropy}, journal = {{ACM} Trans. Comput. Theory}, volume = {13}, number = {4}, pages = {22:1--22:40}, year = {2021}, url = {https://doi.org/10.1145/3470860}, doi = {10.1145/3470860}, timestamp = {Wed, 07 Dec 2022 00:00:00 +0100}, biburl = {https://dblp.org/rec/journals/toct/ArunachalamCKSW21.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/BeckerBDEFGH21, author = {Florent Becker and Tom Besson and J{\'{e}}r{\^{o}}me Durand{-}Lose and Aur{\'{e}}lien Emmanuel and Mohammad{-}Hadi Foroughmand{-}Araabi and Sama Goliaei and Shahrzad Heydarshahi}, title = {Abstract Geometrical Computation 10: An Intrinsically Universal Family of Signal Machines}, journal = {{ACM} Trans. Comput. Theory}, volume = {13}, number = {1}, pages = {4:1--4:31}, year = {2021}, url = {https://doi.org/10.1145/3442359}, doi = {10.1145/3442359}, timestamp = {Wed, 07 Dec 2022 00:00:00 +0100}, biburl = {https://dblp.org/rec/journals/toct/BeckerBDEFGH21.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/BezakovaGGS21, author = {Ivona Bez{\'{a}}kov{\'{a}} and Andreas Galanis and Leslie Ann Goldberg and Daniel Stefankovic}, title = {The Complexity of Approximating the Matching Polynomial in the Complex Plane}, journal = {{ACM} Trans. Comput. Theory}, volume = {13}, number = {2}, pages = {13:1--13:37}, year = {2021}, url = {https://doi.org/10.1145/3448645}, doi = {10.1145/3448645}, timestamp = {Tue, 15 Jun 2021 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/BezakovaGGS21.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/BrandtsWZ21, author = {Alex Brandts and Marcin Wrochna and Stanislav Zivn{\'{y}}}, title = {The Complexity of Promise {SAT} on Non-Boolean Domains}, journal = {{ACM} Trans. Comput. Theory}, volume = {13}, number = {4}, pages = {26:1--26:20}, year = {2021}, url = {https://doi.org/10.1145/3470867}, doi = {10.1145/3470867}, timestamp = {Mon, 03 Jan 2022 00:00:00 +0100}, biburl = {https://dblp.org/rec/journals/toct/BrandtsWZ21.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/BredereckFNT21, author = {Robert Bredereck and Piotr Faliszewski and Rolf Niedermeier and Nimrod Talmon}, title = {Complexity of Shift Bribery in Committee Elections}, journal = {{ACM} Trans. Comput. Theory}, volume = {13}, number = {3}, pages = {20:1--20:25}, year = {2021}, url = {https://doi.org/10.1145/3470647}, doi = {10.1145/3470647}, timestamp = {Thu, 23 Jun 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/BredereckFNT21.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/BunMT21, author = {Mark Bun and Nikhil S. Mande and Justin Thaler}, title = {Sign-rank Can Increase under Intersection}, journal = {{ACM} Trans. Comput. Theory}, volume = {13}, number = {4}, pages = {24:1--24:17}, year = {2021}, url = {https://doi.org/10.1145/3470863}, doi = {10.1145/3470863}, timestamp = {Sun, 12 Nov 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/journals/toct/BunMT21.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/CaiG21, author = {Jin{-}yi Cai and Artem Govorov}, title = {On a Theorem of Lov{\'{a}}sz that ({\&}sdot, \emph{H}) Determines the Isomorphism Type of \emph{H}}, journal = {{ACM} Trans. Comput. Theory}, volume = {13}, number = {2}, pages = {11:1--11:25}, year = {2021}, url = {https://doi.org/10.1145/3448641}, doi = {10.1145/3448641}, timestamp = {Tue, 15 Jun 2021 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/CaiG21.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/ChauguleLV21, author = {Prasad Chaugule and Nutan Limaye and Aditya Varre}, title = {Variants of Homomorphism Polynomials Complete for Algebraic Complexity Classes}, journal = {{ACM} Trans. Comput. Theory}, volume = {13}, number = {4}, pages = {21:1--21:26}, year = {2021}, url = {https://doi.org/10.1145/3470858}, doi = {10.1145/3470858}, timestamp = {Wed, 15 Sep 2021 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/ChauguleLV21.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/Chillara21, author = {Suryajith Chillara}, title = {On Computing Multilinear Polynomials Using Multi-\emph{r}-ic Depth Four Circuits}, journal = {{ACM} Trans. Comput. Theory}, volume = {13}, number = {3}, pages = {16:1--16:21}, year = {2021}, url = {https://doi.org/10.1145/3460952}, doi = {10.1145/3460952}, timestamp = {Fri, 17 Dec 2021 00:00:00 +0100}, biburl = {https://dblp.org/rec/journals/toct/Chillara21.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/DellL21, author = {Holger Dell and John Lapinskas}, title = {Fine-Grained Reductions from Approximate Counting to Decision}, journal = {{ACM} Trans. Comput. Theory}, volume = {13}, number = {2}, pages = {8:1--8:24}, year = {2021}, url = {https://doi.org/10.1145/3442352}, doi = {10.1145/3442352}, timestamp = {Tue, 07 May 2024 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/DellL21.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/FominGLPSZ21, author = {Fedor V. Fomin and Petr A. Golovach and Daniel Lokshtanov and Fahad Panolan and Saket Saurabh and Meirav Zehavi}, title = {Multiplicative Parameterization Above a Guarantee}, journal = {{ACM} Trans. Comput. Theory}, volume = {13}, number = {3}, pages = {18:1--18:16}, year = {2021}, url = {https://doi.org/10.1145/3460956}, doi = {10.1145/3460956}, timestamp = {Mon, 05 Feb 2024 00:00:00 +0100}, biburl = {https://dblp.org/rec/journals/toct/FominGLPSZ21.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/FominLMSZ21, author = {Fedor V. Fomin and Daniel Lokshtanov and Ivan Mihajlin and Saket Saurabh and Meirav Zehavi}, title = {Computation of Hadwiger Number and Related Contraction Problems: Tight Lower Bounds}, journal = {{ACM} Trans. Comput. Theory}, volume = {13}, number = {2}, pages = {10:1--10:25}, year = {2021}, url = {https://doi.org/10.1145/3448639}, doi = {10.1145/3448639}, timestamp = {Sun, 12 Nov 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/journals/toct/FominLMSZ21.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/GalanisGS21, author = {Andreas Galanis and Leslie Ann Goldberg and James Stewart}, title = {Fast Algorithms for General Spin Systems on Bipartite Expanders}, journal = {{ACM} Trans. Comput. Theory}, volume = {13}, number = {4}, pages = {25:1--25:18}, year = {2021}, url = {https://doi.org/10.1145/3470865}, doi = {10.1145/3470865}, timestamp = {Wed, 26 Jul 2023 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/GalanisGS21.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/GobelLS21, author = {Andreas G{\"{o}}bel and J. A. Gregor Lagodzinski and Karen Seidel}, title = {Counting Homomorphisms to Trees Modulo a Prime}, journal = {{ACM} Trans. Comput. Theory}, volume = {13}, number = {3}, pages = {19:1--19:33}, year = {2021}, url = {https://doi.org/10.1145/3460958}, doi = {10.1145/3460958}, timestamp = {Sat, 09 Apr 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/GobelLS21.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/GundaJLST21, author = {Spoorthy Gunda and Pallavi Jain and Daniel Lokshtanov and Saket Saurabh and Prafullkumar Tale}, title = {On the Parameterized Approximability of Contraction to Classes of Chordal Graphs}, journal = {{ACM} Trans. Comput. Theory}, volume = {13}, number = {4}, pages = {27:1--27:40}, year = {2021}, url = {https://doi.org/10.1145/3470869}, doi = {10.1145/3470869}, timestamp = {Sat, 09 Apr 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/GundaJLST21.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/GuptaMSZ21, author = {Sushmita Gupta and Pranabendu Misra and Saket Saurabh and Meirav Zehavi}, title = {Popular Matching in Roommates Setting Is NP-hard}, journal = {{ACM} Trans. Comput. Theory}, volume = {13}, number = {2}, pages = {9:1--9:20}, year = {2021}, url = {https://doi.org/10.1145/3442354}, doi = {10.1145/3442354}, timestamp = {Tue, 15 Jun 2021 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/GuptaMSZ21.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/HitchcockSS21, author = {John M. Hitchcock and Adewale Sekoni and Hadi Shafei}, title = {Polynomial-Time Random Oracles and Separating Complexity Classes}, journal = {{ACM} Trans. Comput. Theory}, volume = {13}, number = {1}, pages = {11--16}, year = {2021}, url = {https://doi.org/10.1145/3434389}, doi = {10.1145/3434389}, timestamp = {Tue, 07 May 2024 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/HitchcockSS21.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/ItsyksonOO21, author = {Dmitry Itsykson and Alexander Okhotin and Vsevolod Oparin}, title = {Computational and Proof Complexity of Partial String Avoidability}, journal = {{ACM} Trans. Comput. Theory}, volume = {13}, number = {1}, pages = {6:1--6:25}, year = {2021}, url = {https://doi.org/10.1145/3442365}, doi = {10.1145/3442365}, timestamp = {Mon, 26 Apr 2021 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/ItsyksonOO21.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/JonssonLR21, author = {Peter Jonsson and Victor Lagerkvist and Biman Roy}, title = {Fine-Grained Time Complexity of Constraint Satisfaction Problems}, journal = {{ACM} Trans. Comput. Theory}, volume = {13}, number = {1}, pages = {2:1--2:32}, year = {2021}, url = {https://doi.org/10.1145/3434387}, doi = {10.1145/3434387}, timestamp = {Mon, 26 Apr 2021 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/JonssonLR21.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/KabanetsKLMO21, author = {Valentine Kabanets and Sajin Koroth and Zhenjian Lu and Dimitrios Myrisiotis and Igor C. Oliveira}, title = {Algorithms and Lower Bounds for De Morgan Formulas of Low-Communication Leaf Gates}, journal = {{ACM} Trans. Comput. Theory}, volume = {13}, number = {4}, pages = {23:1--23:37}, year = {2021}, url = {https://doi.org/10.1145/3470861}, doi = {10.1145/3470861}, timestamp = {Mon, 28 Aug 2023 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/KabanetsKLMO21.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/Kretschmer21, author = {William Kretschmer}, title = {Lower Bounding the {AND-OR} Tree via Symmetrization}, journal = {{ACM} Trans. Comput. Theory}, volume = {13}, number = {1}, pages = {3:1--3:11}, year = {2021}, url = {https://doi.org/10.1145/3434385}, doi = {10.1145/3434385}, timestamp = {Mon, 26 Apr 2021 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/Kretschmer21.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/LiS21, author = {Qian Li and Xiaoming Sun}, title = {On the Sensitivity Complexity of \emph{k}-Uniform Hypergraph Properties}, journal = {{ACM} Trans. Comput. Theory}, volume = {13}, number = {2}, pages = {12:1--12:13}, year = {2021}, url = {https://doi.org/10.1145/3448643}, doi = {10.1145/3448643}, timestamp = {Wed, 26 Apr 2023 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/LiS21.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/Lutz21, author = {Neil Lutz}, title = {Fractal Intersections and Products via Algorithmic Dimension}, journal = {{ACM} Trans. Comput. Theory}, volume = {13}, number = {3}, pages = {14:1--14:15}, year = {2021}, url = {https://doi.org/10.1145/3460948}, doi = {10.1145/3460948}, timestamp = {Fri, 17 Dec 2021 00:00:00 +0100}, biburl = {https://dblp.org/rec/journals/toct/Lutz21.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/MondeYKY21, author = {Akihiro Monde and Yukiko Yamauchi and Shuji Kijima and Masafumi Yamashita}, title = {Can a Skywalker Localize the Midpoint of a Rope?}, journal = {{ACM} Trans. Comput. Theory}, volume = {13}, number = {3}, pages = {17:1--17:23}, year = {2021}, url = {https://doi.org/10.1145/3460954}, doi = {10.1145/3460954}, timestamp = {Fri, 17 Dec 2021 00:00:00 +0100}, biburl = {https://dblp.org/rec/journals/toct/MondeYKY21.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/Viola21, author = {Emanuele Viola}, title = {{AC0} Unpredictability}, journal = {{ACM} Trans. Comput. Theory}, volume = {13}, number = {1}, pages = {5:1--5:8}, year = {2021}, url = {https://doi.org/10.1145/3442362}, doi = {10.1145/3442362}, timestamp = {Mon, 26 Apr 2021 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/Viola21.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/ApplebaumA20, author = {Benny Applebaum and Barak Arkis}, title = {On the Power of Amortization in Secret Sharing: \emph{d}-Uniform Secret Sharing and {CDS} with Constant Information Rate}, journal = {{ACM} Trans. Comput. Theory}, volume = {12}, number = {4}, pages = {24:1--24:21}, year = {2020}, url = {https://doi.org/10.1145/3417756}, doi = {10.1145/3417756}, timestamp = {Tue, 08 Dec 2020 00:00:00 +0100}, biburl = {https://dblp.org/rec/journals/toct/ApplebaumA20.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/BeyersdorffHP20, author = {Olaf Beyersdorff and Luke Hinde and J{\'{a}}n Pich}, title = {Reasons for Hardness in {QBF} Proof Systems}, journal = {{ACM} Trans. Comput. Theory}, volume = {12}, number = {2}, pages = {10:1--10:27}, year = {2020}, url = {https://doi.org/10.1145/3378665}, doi = {10.1145/3378665}, timestamp = {Tue, 29 Dec 2020 00:00:00 +0100}, biburl = {https://dblp.org/rec/journals/toct/BeyersdorffHP20.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/BulatovZ20, author = {Andrei A. Bulatov and Stanislav Zivn{\'{y}}}, title = {Approximate Counting {CSP} Seen from the Other Side}, journal = {{ACM} Trans. Comput. Theory}, volume = {12}, number = {2}, pages = {11:1--11:19}, year = {2020}, url = {https://doi.org/10.1145/3389390}, doi = {10.1145/3389390}, timestamp = {Sat, 08 Jan 2022 00:00:00 +0100}, biburl = {https://dblp.org/rec/journals/toct/BulatovZ20.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/CheraghchiKLM20, author = {Mahdi Cheraghchi and Valentine Kabanets and Zhenjian Lu and Dimitrios Myrisiotis}, title = {Circuit Lower Bounds for {MCSP} from Local Pseudorandom Generators}, journal = {{ACM} Trans. Comput. Theory}, volume = {12}, number = {3}, pages = {21:1--21:27}, year = {2020}, url = {https://doi.org/10.1145/3404860}, doi = {10.1145/3404860}, timestamp = {Thu, 14 Oct 2021 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/CheraghchiKLM20.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/ChiesaMS20, author = {Alessandro Chiesa and Peter Manohar and Igor Shinkar}, title = {Testing Linearity against Non-signaling Strategies}, journal = {{ACM} Trans. Comput. Theory}, volume = {12}, number = {3}, pages = {16:1--16:51}, year = {2020}, url = {https://doi.org/10.1145/3397474}, doi = {10.1145/3397474}, timestamp = {Mon, 03 Aug 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/ChiesaMS20.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/FernauMMS20, author = {Henning Fernau and Florin Manea and Robert Mercas and Markus L. Schmid}, title = {Pattern Matching with Variables: Efficient Algorithms and Complexity Results}, journal = {{ACM} Trans. Comput. Theory}, volume = {12}, number = {1}, pages = {6:1--6:37}, year = {2020}, url = {https://doi.org/10.1145/3369935}, doi = {10.1145/3369935}, timestamp = {Tue, 21 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/journals/toct/FernauMMS20.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/FockeGZ20, author = {Jacob Focke and Leslie Ann Goldberg and Stanislav Zivn{\'{y}}}, title = {The Complexity of Approximately Counting Retractions}, journal = {{ACM} Trans. Comput. Theory}, volume = {12}, number = {3}, pages = {15:1--15:43}, year = {2020}, url = {https://doi.org/10.1145/3397472}, doi = {10.1145/3397472}, timestamp = {Mon, 03 Aug 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/FockeGZ20.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/GalesiTT20, author = {Nicola Galesi and Navid Talebanfard and Jacobo Tor{\'{a}}n}, title = {Cops-Robber Games and the Resolution of Tseitin Formulas}, journal = {{ACM} Trans. Comput. Theory}, volume = {12}, number = {2}, pages = {9:1--9:22}, year = {2020}, url = {https://doi.org/10.1145/3378667}, doi = {10.1145/3378667}, timestamp = {Mon, 26 Oct 2020 00:00:00 +0100}, biburl = {https://dblp.org/rec/journals/toct/GalesiTT20.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/GanianHKS20, author = {Robert Ganian and Ronald de Haan and Iyad Kanj and Stefan Szeider}, title = {On Existential {MSO} and Its Relation to {ETH}}, journal = {{ACM} Trans. Comput. Theory}, volume = {12}, number = {4}, pages = {22:1--22:32}, year = {2020}, url = {https://doi.org/10.1145/3417759}, doi = {10.1145/3417759}, timestamp = {Sun, 04 Aug 2024 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/GanianHKS20.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/GhoshKM20, author = {Arijit Ghosh and Sudeshna Kolay and Gopinath Mishra}, title = {{FPT} Algorithms for Embedding into Low-Complexity Graphic Metrics}, journal = {{ACM} Trans. Comput. Theory}, volume = {12}, number = {1}, pages = {1:1--1:41}, year = {2020}, url = {https://doi.org/10.1145/3369933}, doi = {10.1145/3369933}, timestamp = {Mon, 08 Jun 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/GhoshKM20.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/GoldenbergS20, author = {Elazar Goldenberg and {Karthik {C. S.}}}, title = {Toward a General Direct Product Testing Theorem}, journal = {{ACM} Trans. Comput. Theory}, volume = {12}, number = {1}, pages = {7:1--7:18}, year = {2020}, url = {https://doi.org/10.1145/3369939}, doi = {10.1145/3369939}, timestamp = {Wed, 07 Dec 2022 00:00:00 +0100}, biburl = {https://dblp.org/rec/journals/toct/GoldenbergS20.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/GoldreichR20, author = {Oded Goldreich and Dana Ron}, title = {The Subgraph Testing Model}, journal = {{ACM} Trans. Comput. Theory}, volume = {12}, number = {4}, pages = {28:1--28:32}, year = {2020}, url = {https://doi.org/10.1145/3428675}, doi = {10.1145/3428675}, timestamp = {Tue, 08 Dec 2020 00:00:00 +0100}, biburl = {https://dblp.org/rec/journals/toct/GoldreichR20.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/GoosW20, author = {Mika G{\"{o}}{\"{o}}s and Thomas Watson}, title = {A Lower Bound for Sampling Disjoint Sets}, journal = {{ACM} Trans. Comput. Theory}, volume = {12}, number = {3}, pages = {20:1--20:13}, year = {2020}, url = {https://doi.org/10.1145/3404858}, doi = {10.1145/3404858}, timestamp = {Mon, 03 Aug 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/GoosW20.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/GurjarV20, author = {Rohit Gurjar and Ben Lee Volk}, title = {Pseudorandom Bits for Oblivious Branching Programs}, journal = {{ACM} Trans. Comput. Theory}, volume = {12}, number = {2}, pages = {8:1--8:12}, year = {2020}, url = {https://doi.org/10.1145/3378663}, doi = {10.1145/3378663}, timestamp = {Mon, 08 Jun 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/GurjarV20.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/HemaspaandraHM20, author = {Edith Hemaspaandra and Lane A. Hemaspaandra and Curtis Menton}, title = {Search versus Decision for Election Manipulation Problems}, journal = {{ACM} Trans. Comput. Theory}, volume = {12}, number = {1}, pages = {3:1--3:42}, year = {2020}, url = {https://doi.org/10.1145/3369937}, doi = {10.1145/3369937}, timestamp = {Mon, 05 Feb 2024 00:00:00 +0100}, biburl = {https://dblp.org/rec/journals/toct/HemaspaandraHM20.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/HermoO20, author = {Montserrat Hermo and Ana Ozaki}, title = {Exact Learning: On the Boundary between Horn and {CNF}}, journal = {{ACM} Trans. Comput. Theory}, volume = {12}, number = {1}, pages = {4:1--4:25}, year = {2020}, url = {https://doi.org/10.1145/3369930}, doi = {10.1145/3369930}, timestamp = {Tue, 29 Dec 2020 00:00:00 +0100}, biburl = {https://dblp.org/rec/journals/toct/HermoO20.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/Jukna20, author = {Stasys Jukna}, title = {Coin Flipping in Dynamic Programming Is Almost Useless}, journal = {{ACM} Trans. Comput. Theory}, volume = {12}, number = {3}, pages = {17:1--17:26}, year = {2020}, url = {https://doi.org/10.1145/3397476}, doi = {10.1145/3397476}, timestamp = {Sun, 02 Oct 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/Jukna20.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/KayalNS20, author = {Neeraj Kayal and Vineet Nair and Chandan Saha}, title = {Separation Between Read-once Oblivious Algebraic Branching Programs (ROABPs) and Multilinear Depth-three Circuits}, journal = {{ACM} Trans. Comput. Theory}, volume = {12}, number = {1}, pages = {2:1--2:27}, year = {2020}, url = {https://doi.org/10.1145/3369928}, doi = {10.1145/3369928}, timestamp = {Mon, 08 Jun 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/KayalNS20.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/KnopPW20, author = {Dusan Knop and Michal Pilipczuk and Marcin Wrochna}, title = {Tight Complexity Lower Bounds for Integer Linear Programming with Few Constraints}, journal = {{ACM} Trans. Comput. Theory}, volume = {12}, number = {3}, pages = {19:1--19:19}, year = {2020}, url = {https://doi.org/10.1145/3397484}, doi = {10.1145/3397484}, timestamp = {Mon, 03 Jan 2022 00:00:00 +0100}, biburl = {https://dblp.org/rec/journals/toct/KnopPW20.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/Kumar20, author = {Mrinal Kumar}, title = {On the Power of Border of Depth-3 Arithmetic Circuits}, journal = {{ACM} Trans. Comput. Theory}, volume = {12}, number = {1}, pages = {5:1--5:8}, year = {2020}, url = {https://doi.org/10.1145/3371506}, doi = {10.1145/3371506}, timestamp = {Fri, 17 Jul 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/Kumar20.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/LagerkvistW20, author = {Victor Lagerkvist and Magnus Wahlstr{\"{o}}m}, title = {Sparsification of {SAT} and {CSP} Problems via Tractable Extensions}, journal = {{ACM} Trans. Comput. Theory}, volume = {12}, number = {2}, pages = {13:1--13:29}, year = {2020}, url = {https://doi.org/10.1145/3389411}, doi = {10.1145/3389411}, timestamp = {Sat, 05 Sep 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/LagerkvistW20.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/ODonnell20, author = {Ryan O'Donnell}, title = {Editorial from the New Editor-in-Chief}, journal = {{ACM} Trans. Comput. Theory}, volume = {12}, number = {1}, pages = {1e:1}, year = {2020}, url = {https://doi.org/10.1145/3381517}, doi = {10.1145/3381517}, timestamp = {Mon, 08 Jun 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/ODonnell20.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/PodolskiiS20, author = {Vladimir V. Podolskii and Alexander A. Sherstov}, title = {Inner Product and Set Disjointness: Beyond Logarithmically Many Parties}, journal = {{ACM} Trans. Comput. Theory}, volume = {12}, number = {4}, pages = {26:1--26:28}, year = {2020}, url = {https://doi.org/10.1145/3428671}, doi = {10.1145/3428671}, timestamp = {Sat, 09 Apr 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/PodolskiiS20.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/RahmanW20, author = {Md Lutfar Rahman and Thomas Watson}, title = {Complexity of Unordered {CNF} Games}, journal = {{ACM} Trans. Comput. Theory}, volume = {12}, number = {3}, pages = {18:1--18:18}, year = {2020}, url = {https://doi.org/10.1145/3397478}, doi = {10.1145/3397478}, timestamp = {Mon, 03 Aug 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/RahmanW20.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/Rosenbaum20, author = {David J. Rosenbaum}, title = {Beating the Generator-Enumeration Bound for Solvable-Group Isomorphism}, journal = {{ACM} Trans. Comput. Theory}, volume = {12}, number = {2}, pages = {12:1--12:18}, year = {2020}, url = {https://doi.org/10.1145/3389396}, doi = {10.1145/3389396}, timestamp = {Mon, 08 Jun 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/Rosenbaum20.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/Srinivasan20, author = {Srikanth Srinivasan}, title = {Strongly Exponential Separation between Monotone {VP} and Monotone {VNP}}, journal = {{ACM} Trans. Comput. Theory}, volume = {12}, number = {4}, pages = {23:1--23:12}, year = {2020}, url = {https://doi.org/10.1145/3417758}, doi = {10.1145/3417758}, timestamp = {Mon, 28 Aug 2023 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/Srinivasan20.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/SrinivasanTV20, author = {Srikanth Srinivasan and Utkarsh Tripathi and S. Venkitesh}, title = {Decoding Variants of Reed-Muller Codes over Finite Grids}, journal = {{ACM} Trans. Comput. Theory}, volume = {12}, number = {4}, pages = {25:1--25:11}, year = {2020}, url = {https://doi.org/10.1145/3417754}, doi = {10.1145/3417754}, timestamp = {Thu, 14 Oct 2021 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/SrinivasanTV20.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/Watson20, author = {Thomas Watson}, title = {Quadratic Simulations of Merlin-Arthur Games}, journal = {{ACM} Trans. Comput. Theory}, volume = {12}, number = {2}, pages = {14:1--14:11}, year = {2020}, url = {https://doi.org/10.1145/3389399}, doi = {10.1145/3389399}, timestamp = {Mon, 08 Jun 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/Watson20.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/Watson20a, author = {Thomas Watson}, title = {A ZPP\({}^{\mbox{NP[1]}}\) Lifting Theorem}, journal = {{ACM} Trans. Comput. Theory}, volume = {12}, number = {4}, pages = {27:1--27:20}, year = {2020}, url = {https://doi.org/10.1145/3428673}, doi = {10.1145/3428673}, timestamp = {Wed, 03 Mar 2021 00:00:00 +0100}, biburl = {https://dblp.org/rec/journals/toct/Watson20a.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/AgrawalLSZ19, author = {Akanksha Agrawal and Daniel Lokshtanov and Saket Saurabh and Meirav Zehavi}, title = {Split Contraction: The Untold Story}, journal = {{ACM} Trans. Comput. Theory}, volume = {11}, number = {3}, pages = {18:1--18:22}, year = {2019}, url = {https://doi.org/10.1145/3319909}, doi = {10.1145/3319909}, timestamp = {Tue, 02 Jan 2024 00:00:00 +0100}, biburl = {https://dblp.org/rec/journals/toct/AgrawalLSZ19.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/AllenderH19, author = {Eric Allender and Shuichi Hirahara}, title = {New Insights on the (Non-)Hardness of Circuit Minimization and Related Problems}, journal = {{ACM} Trans. Comput. Theory}, volume = {11}, number = {4}, pages = {27:1--27:27}, year = {2019}, url = {https://doi.org/10.1145/3349616}, doi = {10.1145/3349616}, timestamp = {Fri, 09 Apr 2021 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/AllenderH19.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/AvivT19, author = {Nir Aviv and Amnon Ta{-}Shma}, title = {On the Entropy Loss and Gap of Condensers}, journal = {{ACM} Trans. Comput. Theory}, volume = {11}, number = {3}, pages = {15:1--15:14}, year = {2019}, url = {https://doi.org/10.1145/3317691}, doi = {10.1145/3317691}, timestamp = {Thu, 14 Oct 2021 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/AvivT19.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/AydinliogluB19, author = {Baris Aydinlioglu and Eric Bach}, title = {Corrigendum to Affine Relativization: Unifying the Algebrization and Relativization Barriers}, journal = {{ACM} Trans. Comput. Theory}, volume = {11}, number = {3}, pages = {16:1}, year = {2019}, url = {https://doi.org/10.1145/3317693}, doi = {10.1145/3317693}, timestamp = {Wed, 01 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/journals/toct/AydinliogluB19.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/BeyersdorffCJ19, author = {Olaf Beyersdorff and Leroy Chew and Mikol{\'{a}}s Janota}, title = {New Resolution-Based {QBF} Calculi and Their Proof Complexity}, journal = {{ACM} Trans. Comput. Theory}, volume = {11}, number = {4}, pages = {26:1--26:42}, year = {2019}, url = {https://doi.org/10.1145/3352155}, doi = {10.1145/3352155}, timestamp = {Mon, 05 Feb 2024 00:00:00 +0100}, biburl = {https://dblp.org/rec/journals/toct/BeyersdorffCJ19.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/Black19, author = {Timothy Black}, title = {Monotone Properties of \emph{k}-Uniform Hypergraphs Are Weakly Evasive}, journal = {{ACM} Trans. Comput. Theory}, volume = {11}, number = {3}, pages = {14:1--14:14}, year = {2019}, url = {https://doi.org/10.1145/3313908}, doi = {10.1145/3313908}, timestamp = {Mon, 08 Jun 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/Black19.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/BlaisCELR19, author = {Eric Blais and Cl{\'{e}}ment L. Canonne and Talya Eden and Amit Levi and Dana Ron}, title = {Tolerant Junta Testing and the Connection to Submodular Optimization and Function Isomorphism}, journal = {{ACM} Trans. Comput. Theory}, volume = {11}, number = {4}, pages = {24:1--24:33}, year = {2019}, url = {https://doi.org/10.1145/3337789}, doi = {10.1145/3337789}, timestamp = {Sat, 30 Sep 2023 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/BlaisCELR19.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/BlaisCG19, author = {Eric Blais and Cl{\'{e}}ment L. Canonne and Tom Gur}, title = {Distribution Testing Lower Bounds via Reductions from Communication Complexity}, journal = {{ACM} Trans. Comput. Theory}, volume = {11}, number = {2}, pages = {6:1--6:37}, year = {2019}, url = {https://doi.org/10.1145/3305270}, doi = {10.1145/3305270}, timestamp = {Mon, 26 Jun 2023 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/BlaisCG19.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/BonamyKPSW19, author = {Marthe Bonamy and Lukasz Kowalik and Michal Pilipczuk and Arkadiusz Socala and Marcin Wrochna}, title = {Tight Lower Bounds for the Complexity of Multicoloring}, journal = {{ACM} Trans. Comput. Theory}, volume = {11}, number = {3}, pages = {13:1--13:19}, year = {2019}, url = {https://doi.org/10.1145/3313906}, doi = {10.1145/3313906}, timestamp = {Mon, 03 Jan 2022 00:00:00 +0100}, biburl = {https://dblp.org/rec/journals/toct/BonamyKPSW19.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/BoppanaHLV19, author = {Ravi B. Boppana and Johan H{\aa}stad and Chin Ho Lee and Emanuele Viola}, title = {Bounded Independence versus Symmetric Tests}, journal = {{ACM} Trans. Comput. Theory}, volume = {11}, number = {4}, pages = {21:1--21:27}, year = {2019}, url = {https://doi.org/10.1145/3337783}, doi = {10.1145/3337783}, timestamp = {Mon, 08 Jun 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/BoppanaHLV19.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/CaiKW19, author = {Jin{-}Yi Cai and Michael Kowalczyk and Tyson Williams}, title = {Gadgets and Anti-Gadgets Leading to a Complexity Dichotomy}, journal = {{ACM} Trans. Comput. Theory}, volume = {11}, number = {2}, pages = {7:1--7:26}, year = {2019}, url = {https://doi.org/10.1145/3305272}, doi = {10.1145/3305272}, timestamp = {Mon, 08 Jun 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/CaiKW19.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/DineshKS19, author = {Krishnamoorthy Dinesh and Sajin Koroth and Jayalal Sarma}, title = {Characterization and Lower Bounds for Branching Program Size using Projective Dimension}, journal = {{ACM} Trans. Comput. Theory}, volume = {11}, number = {2}, pages = {8:1--8:22}, year = {2019}, url = {https://doi.org/10.1145/3305274}, doi = {10.1145/3305274}, timestamp = {Mon, 08 Jun 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/DineshKS19.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/FullaUZ19, author = {Peter Fulla and Hannes Uppman and Stanislav Zivn{\'{y}}}, title = {The Complexity of Boolean Surjective General-Valued CSPs}, journal = {{ACM} Trans. Comput. Theory}, volume = {11}, number = {1}, pages = {4:1--4:31}, year = {2019}, url = {https://doi.org/10.1145/3282429}, doi = {10.1145/3282429}, timestamp = {Sat, 08 Jan 2022 00:00:00 +0100}, biburl = {https://dblp.org/rec/journals/toct/FullaUZ19.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/GanardiL19, author = {Moses Ganardi and Markus Lohrey}, title = {A Universal Tree Balancing Theorem}, journal = {{ACM} Trans. Comput. Theory}, volume = {11}, number = {1}, pages = {1:1--1:25}, year = {2019}, url = {https://doi.org/10.1145/3278158}, doi = {10.1145/3278158}, timestamp = {Mon, 08 Jun 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/GanardiL19.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/GoldbergJ19, author = {Leslie Ann Goldberg and Mark Jerrum}, title = {Approximating Pairwise Correlations in the Ising Model}, journal = {{ACM} Trans. Comput. Theory}, volume = {11}, number = {4}, pages = {23:1--23:20}, year = {2019}, url = {https://doi.org/10.1145/3337785}, doi = {10.1145/3337785}, timestamp = {Mon, 08 Jun 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/GoldbergJ19.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/GoldreichGK19, author = {Oded Goldreich and Tom Gur and Ilan Komargodski}, title = {Strong Locally Testable Codes with Relaxed Local Decoders}, journal = {{ACM} Trans. Comput. Theory}, volume = {11}, number = {3}, pages = {17:1--17:38}, year = {2019}, url = {https://doi.org/10.1145/3319907}, doi = {10.1145/3319907}, timestamp = {Tue, 21 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/journals/toct/GoldreichGK19.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/Haviv19, author = {Ishay Haviv}, title = {On Minrank and Forbidden Subgraphs}, journal = {{ACM} Trans. Comput. Theory}, volume = {11}, number = {4}, pages = {20:1--20:13}, year = {2019}, url = {https://doi.org/10.1145/3322817}, doi = {10.1145/3322817}, timestamp = {Mon, 08 Jun 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/Haviv19.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/IwamaN19, author = {Kazuo Iwama and Atsuki Nagao}, title = {Read-Once Branching Programs for Tree Evaluation Problems}, journal = {{ACM} Trans. Comput. Theory}, volume = {11}, number = {1}, pages = {5:1--5:12}, year = {2019}, url = {https://doi.org/10.1145/3282433}, doi = {10.1145/3282433}, timestamp = {Sun, 02 Oct 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/IwamaN19.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/JansenP19, author = {Bart M. P. Jansen and Astrid Pieterse}, title = {Optimal Sparsification for Some Binary CSPs Using Low-Degree Polynomials}, journal = {{ACM} Trans. Comput. Theory}, volume = {11}, number = {4}, pages = {28:1--28:26}, year = {2019}, url = {https://doi.org/10.1145/3349618}, doi = {10.1145/3349618}, timestamp = {Sat, 08 Jan 2022 00:00:00 +0100}, biburl = {https://dblp.org/rec/journals/toct/JansenP19.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/KayalNST19, author = {Neeraj Kayal and Vineet Nair and Chandan Saha and S{\'{e}}bastien Tavenas}, title = {Reconstruction of Full Rank Algebraic Branching Programs}, journal = {{ACM} Trans. Comput. Theory}, volume = {11}, number = {1}, pages = {2:1--2:56}, year = {2019}, url = {https://doi.org/10.1145/3282427}, doi = {10.1145/3282427}, timestamp = {Mon, 08 Jun 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/KayalNST19.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/KerenidisRU19, author = {Iordanis Kerenidis and Adi Ros{\'{e}}n and Florent Urrutia}, title = {Multi-Party Protocols, Information Complexity and Privacy}, journal = {{ACM} Trans. Comput. Theory}, volume = {11}, number = {2}, pages = {9:1--9:29}, year = {2019}, url = {https://doi.org/10.1145/3313230}, doi = {10.1145/3313230}, timestamp = {Mon, 08 Jun 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/KerenidisRU19.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/KolayPS19, author = {Sudeshna Kolay and Fahad Panolan and Saket Saurabh}, title = {Communication Complexity and Graph Families}, journal = {{ACM} Trans. Comput. Theory}, volume = {11}, number = {2}, pages = {11:1--11:28}, year = {2019}, url = {https://doi.org/10.1145/3313234}, doi = {10.1145/3313234}, timestamp = {Mon, 08 Jun 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/KolayPS19.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/LaroseMP19, author = {Beno{\^{\i}}t Larose and Barnaby Martin and Dani{\"{e}}l Paulusma}, title = {Surjective H-Colouring over Reflexive Digraphs}, journal = {{ACM} Trans. Comput. Theory}, volume = {11}, number = {1}, pages = {3:1--3:21}, year = {2019}, url = {https://doi.org/10.1145/3282431}, doi = {10.1145/3282431}, timestamp = {Mon, 26 Oct 2020 00:00:00 +0100}, biburl = {https://dblp.org/rec/journals/toct/LaroseMP19.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/OliveiraP19, author = {Mateus de Oliveira Oliveira and Pavel Pudl{\'{a}}k}, title = {Representations of Monotone Boolean Functions by Linear Programs}, journal = {{ACM} Trans. Comput. Theory}, volume = {11}, number = {4}, pages = {22:1--22:31}, year = {2019}, url = {https://doi.org/10.1145/3337787}, doi = {10.1145/3337787}, timestamp = {Thu, 14 Oct 2021 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/OliveiraP19.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/RamyaR19, author = {C. Ramya and B. V. Raghavendra Rao}, title = {Lower bounds for Sum and Sum of Products of Read-once Formulas}, journal = {{ACM} Trans. Comput. Theory}, volume = {11}, number = {2}, pages = {10:1--10:27}, year = {2019}, url = {https://doi.org/10.1145/3313232}, doi = {10.1145/3313232}, timestamp = {Mon, 08 Jun 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/RamyaR19.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/Scheder19, author = {Dominik Scheder}, title = {{PPSZ} for \emph{k} {\(\geq\)} 5: More Is Better}, journal = {{ACM} Trans. Comput. Theory}, volume = {11}, number = {4}, pages = {25:1--25:22}, year = {2019}, url = {https://doi.org/10.1145/3349613}, doi = {10.1145/3349613}, timestamp = {Sun, 02 Oct 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/Scheder19.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/SchoenebeckT19, author = {Grant Schoenebeck and Biaoshuai Tao}, title = {Beyond Worst-case (In)approximability of Nonsubmodular Influence Maximization}, journal = {{ACM} Trans. Comput. Theory}, volume = {11}, number = {3}, pages = {12:1--12:56}, year = {2019}, url = {https://doi.org/10.1145/3313904}, doi = {10.1145/3313904}, timestamp = {Mon, 08 Jun 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/SchoenebeckT19.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/Viola19, author = {Emanuele Viola}, title = {Constant-Error Pseudorandomness Proofs from Hardness Require Majority}, journal = {{ACM} Trans. Comput. Theory}, volume = {11}, number = {4}, pages = {19:1--19:11}, year = {2019}, url = {https://doi.org/10.1145/3322815}, doi = {10.1145/3322815}, timestamp = {Mon, 28 Aug 2023 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/Viola19.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/AgrawalLMS18, author = {Akanksha Agrawal and Daniel Lokshtanov and Amer E. Mouawad and Saket Saurabh}, title = {Simultaneous Feedback Vertex Set: {A} Parameterized Perspective}, journal = {{ACM} Trans. Comput. Theory}, volume = {10}, number = {4}, pages = {18:1--18:25}, year = {2018}, url = {https://doi.org/10.1145/3265027}, doi = {10.1145/3265027}, timestamp = {Tue, 02 Jan 2024 00:00:00 +0100}, biburl = {https://dblp.org/rec/journals/toct/AgrawalLMS18.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/AndersonFSSV18, author = {Matthew Anderson and Michael A. Forbes and Ramprasad Saptharishi and Amir Shpilka and Ben Lee Volk}, title = {Identity Testing and Lower Bounds for Read-\emph{k} Oblivious Algebraic Branching Programs}, journal = {{ACM} Trans. Comput. Theory}, volume = {10}, number = {1}, pages = {3:1--3:30}, year = {2018}, url = {https://doi.org/10.1145/3170709}, doi = {10.1145/3170709}, timestamp = {Mon, 26 Jun 2023 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/AndersonFSSV18.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/AydinliogluB18, author = {Baris Aydinlioglu and Eric Bach}, title = {Affine Relativization: Unifying the Algebrization and Relativization Barriers}, journal = {{ACM} Trans. Comput. Theory}, volume = {10}, number = {1}, pages = {1:1--1:67}, year = {2018}, url = {https://doi.org/10.1145/3170704}, doi = {10.1145/3170704}, timestamp = {Wed, 01 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/journals/toct/AydinliogluB18.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/BhattacharyyaC18, author = {Rishiraj Bhattacharyya and Sourav Chakraborty}, title = {Property Testing of Joint Distributions using Conditional Samples}, journal = {{ACM} Trans. Comput. Theory}, volume = {10}, number = {4}, pages = {16:1--16:20}, year = {2018}, url = {https://doi.org/10.1145/3241377}, doi = {10.1145/3241377}, timestamp = {Sun, 04 Aug 2024 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/BhattacharyyaC18.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/BliznetsCKP18, author = {Ivan Bliznets and Marek Cygan and Pawel Komosa and Michal Pilipczuk}, title = {Hardness of Approximation for \emph{H}-free Edge Modification Problems}, journal = {{ACM} Trans. Comput. Theory}, volume = {10}, number = {2}, pages = {9:1--9:32}, year = {2018}, url = {https://doi.org/10.1145/3196834}, doi = {10.1145/3196834}, timestamp = {Mon, 08 Jun 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/BliznetsCKP18.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/BoczkowskiKM18, author = {Lucas Boczkowski and Iordanis Kerenidis and Fr{\'{e}}d{\'{e}}ric Magniez}, title = {Streaming Communication Protocols}, journal = {{ACM} Trans. Comput. Theory}, volume = {10}, number = {4}, pages = {19:1--19:21}, year = {2018}, url = {https://doi.org/10.1145/3276748}, doi = {10.1145/3276748}, timestamp = {Mon, 08 Jun 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/BoczkowskiKM18.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/ChakrabortyT18, author = {Diptarka Chakraborty and Raghunath Tewari}, title = {An \emph{O}(\emph{n}\({}^{\mbox{{\(\epsilon\)}}}\)) Space and Polynomial Time Algorithm for Reachability in Directed Layered Planar Graphs}, journal = {{ACM} Trans. Comput. Theory}, volume = {9}, number = {4}, pages = {19:1--19:11}, year = {2018}, url = {https://doi.org/10.1145/3154857}, doi = {10.1145/3154857}, timestamp = {Tue, 28 Jul 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/ChakrabortyT18.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/Chang18, author = {Ching{-}Lueh Chang}, title = {Metric 1-Median Selection: Query Complexity vs. Approximation Ratio}, journal = {{ACM} Trans. Comput. Theory}, volume = {9}, number = {4}, pages = {20:1--20:23}, year = {2018}, url = {https://doi.org/10.1145/3154858}, doi = {10.1145/3154858}, timestamp = {Sat, 09 Apr 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/Chang18.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/FilmusKMW18, author = {Yuval Filmus and Guy Kindler and Elchanan Mossel and Karl Wimmer}, title = {Invariance Principle on the Slice}, journal = {{ACM} Trans. Comput. Theory}, volume = {10}, number = {3}, pages = {11:1--11:37}, year = {2018}, url = {https://doi.org/10.1145/3186590}, doi = {10.1145/3186590}, timestamp = {Mon, 08 Jun 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/FilmusKMW18.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/GanardiHKL18, author = {Moses Ganardi and Danny Hucke and Daniel K{\"{o}}nig and Markus Lohrey}, title = {Circuits and Expressions over Finite Semirings}, journal = {{ACM} Trans. Comput. Theory}, volume = {10}, number = {4}, pages = {15:1--15:30}, year = {2018}, url = {https://doi.org/10.1145/3241375}, doi = {10.1145/3241375}, timestamp = {Mon, 08 Jun 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/GanardiHKL18.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/GharibianS18, author = {Sevag Gharibian and Jamie Sikora}, title = {Ground State Connectivity of Local Hamiltonians}, journal = {{ACM} Trans. Comput. Theory}, volume = {10}, number = {2}, pages = {8:1--8:28}, year = {2018}, url = {https://doi.org/10.1145/3186587}, doi = {10.1145/3186587}, timestamp = {Mon, 28 Aug 2023 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/GharibianS18.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/GoosJPW18, author = {Mika G{\"{o}}{\"{o}}s and T. S. Jayram and Toniann Pitassi and Thomas Watson}, title = {Randomized Communication versus Partition Number}, journal = {{ACM} Trans. Comput. Theory}, volume = {10}, number = {1}, pages = {4:1--4:20}, year = {2018}, url = {https://doi.org/10.1145/3170711}, doi = {10.1145/3170711}, timestamp = {Mon, 08 Jun 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/GoosJPW18.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/GuoL18, author = {Heng Guo and Pinyan Lu}, title = {Uniqueness, Spatial Mixing, and Approximation for Ferromagnetic 2-Spin Systems}, journal = {{ACM} Trans. Comput. Theory}, volume = {10}, number = {4}, pages = {17:1--17:25}, year = {2018}, url = {https://doi.org/10.1145/3265025}, doi = {10.1145/3265025}, timestamp = {Sat, 30 Sep 2023 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/GuoL18.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/IwamaY18, author = {Kazuo Iwama and Yuichi Yoshida}, title = {Parameterized Testability}, journal = {{ACM} Trans. Comput. Theory}, volume = {9}, number = {4}, pages = {16:1--16:16}, year = {2018}, url = {https://doi.org/10.1145/3155294}, doi = {10.1145/3155294}, timestamp = {Mon, 08 Jun 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/IwamaY18.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/Komusiewicz18, author = {Christian Komusiewicz}, title = {Tight Running Time Lower Bounds for Vertex Deletion Problems}, journal = {{ACM} Trans. Comput. Theory}, volume = {10}, number = {2}, pages = {6:1--6:18}, year = {2018}, url = {https://doi.org/10.1145/3186589}, doi = {10.1145/3186589}, timestamp = {Mon, 08 Jun 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/Komusiewicz18.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/LeeV18, author = {Chin Ho Lee and Emanuele Viola}, title = {The Coin Problem for Product Tests}, journal = {{ACM} Trans. Comput. Theory}, volume = {10}, number = {3}, pages = {14:1--14:10}, year = {2018}, url = {https://doi.org/10.1145/3201787}, doi = {10.1145/3201787}, timestamp = {Mon, 08 Jun 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/LeeV18.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/LutzL18, author = {Jack H. Lutz and Neil Lutz}, title = {Algorithmic Information, Plane Kakeya Sets, and Conditional Dimension}, journal = {{ACM} Trans. Comput. Theory}, volume = {10}, number = {2}, pages = {7:1--7:22}, year = {2018}, url = {https://doi.org/10.1145/3201783}, doi = {10.1145/3201783}, timestamp = {Mon, 08 Jun 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/LutzL18.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/MinahanV18, author = {Daniel Minahan and Ilya Volkovich}, title = {Complete Derandomization of Identity Testing and Reconstruction of Read-Once Formulas}, journal = {{ACM} Trans. Comput. Theory}, volume = {10}, number = {3}, pages = {10:1--10:11}, year = {2018}, url = {https://doi.org/10.1145/3196836}, doi = {10.1145/3196836}, timestamp = {Mon, 08 Jun 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/MinahanV18.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/ODonnellS18, author = {Ryan O'Donnell and A. C. Cem Say}, title = {The Weakness of {CTC} Qubits and the Power of Approximate Counting}, journal = {{ACM} Trans. Comput. Theory}, volume = {10}, number = {2}, pages = {5:1--5:22}, year = {2018}, url = {https://doi.org/10.1145/3196832}, doi = {10.1145/3196832}, timestamp = {Sun, 02 Oct 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/ODonnellS18.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/PallavoorRV18, author = {Ramesh Krishnan S. Pallavoor and Sofya Raskhodnikova and Nithin Varma}, title = {Parameterized Property Testing of Functions}, journal = {{ACM} Trans. Comput. Theory}, volume = {9}, number = {4}, pages = {17:1--17:19}, year = {2018}, url = {https://doi.org/10.1145/3155296}, doi = {10.1145/3155296}, timestamp = {Fri, 07 Jun 2024 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/PallavoorRV18.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/PilipczukW18, author = {Michal Pilipczuk and Marcin Wrochna}, title = {On Space Efficiency of Algorithms Working on Structural Decompositions of Graphs}, journal = {{ACM} Trans. Comput. Theory}, volume = {9}, number = {4}, pages = {18:1--18:36}, year = {2018}, url = {https://doi.org/10.1145/3154856}, doi = {10.1145/3154856}, timestamp = {Mon, 03 Jan 2022 00:00:00 +0100}, biburl = {https://dblp.org/rec/journals/toct/PilipczukW18.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/PilipczukW18a, author = {Marcin Pilipczuk and Magnus Wahlstr{\"{o}}m}, title = {Directed Multicut is W[1]-hard, Even for Four Terminal Pairs}, journal = {{ACM} Trans. Comput. Theory}, volume = {10}, number = {3}, pages = {13:1--13:18}, year = {2018}, url = {https://doi.org/10.1145/3201775}, doi = {10.1145/3201775}, timestamp = {Mon, 08 Jun 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/PilipczukW18a.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/ThapperZ18, author = {Johan Thapper and Stanislav Zivn{\'{y}}}, title = {The Limits of {SDP} Relaxations for General-Valued CSPs}, journal = {{ACM} Trans. Comput. Theory}, volume = {10}, number = {3}, pages = {12:1--12:22}, year = {2018}, url = {https://doi.org/10.1145/3201777}, doi = {10.1145/3201777}, timestamp = {Sat, 08 Jan 2022 00:00:00 +0100}, biburl = {https://dblp.org/rec/journals/toct/ThapperZ18.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/Watson18, author = {Thomas Watson}, title = {Communication Complexity of Statistical Distance}, journal = {{ACM} Trans. Comput. Theory}, volume = {10}, number = {1}, pages = {2:1--2:11}, year = {2018}, url = {https://doi.org/10.1145/3170708}, doi = {10.1145/3170708}, timestamp = {Mon, 08 Jun 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/Watson18.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/AdamaszekKPP17, author = {Anna Adamaszek and Tomasz Kociumaka and Marcin Pilipczuk and Michal Pilipczuk}, title = {Hardness of Approximation for Strip Packing}, journal = {{ACM} Trans. Comput. Theory}, volume = {9}, number = {3}, pages = {14:1--14:7}, year = {2017}, url = {https://doi.org/10.1145/3092026}, doi = {10.1145/3092026}, timestamp = {Mon, 08 Jun 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/AdamaszekKPP17.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/ArtemenkoS17, author = {Sergei Artemenko and Ronen Shaltiel}, title = {Pseudorandom Generators with Optimal Seed Length for Non-Boolean Poly-Size Circuits}, journal = {{ACM} Trans. Comput. Theory}, volume = {9}, number = {2}, pages = {6:1--6:26}, year = {2017}, url = {https://doi.org/10.1145/3018057}, doi = {10.1145/3018057}, timestamp = {Mon, 08 Jun 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/ArtemenkoS17.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/BhattacharyyaG17, author = {Arnab Bhattacharyya and Sivakanth Gopi}, title = {Lower Bounds for Constant Query Affine-Invariant LCCs and LTCs}, journal = {{ACM} Trans. Comput. Theory}, volume = {9}, number = {2}, pages = {7:1--7:17}, year = {2017}, url = {https://doi.org/10.1145/3016802}, doi = {10.1145/3016802}, timestamp = {Mon, 08 Jun 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/BhattacharyyaG17.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/Chen17, author = {Hubie Chen}, title = {Proof Complexity Modulo the Polynomial Hierarchy: Understanding Alternation as a Source of Hardness}, journal = {{ACM} Trans. Comput. Theory}, volume = {9}, number = {3}, pages = {15:1--15:20}, year = {2017}, url = {https://doi.org/10.1145/3087534}, doi = {10.1145/3087534}, timestamp = {Mon, 08 Jun 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/Chen17.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/ChenL17, author = {Hubie Chen and Beno{\^{\i}}t Larose}, title = {Asking the Metaquestions in Constraint Tractability}, journal = {{ACM} Trans. Comput. Theory}, volume = {9}, number = {3}, pages = {11:1--11:27}, year = {2017}, url = {https://doi.org/10.1145/3134757}, doi = {10.1145/3134757}, timestamp = {Mon, 08 Jun 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/ChenL17.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/DhayalSS17, author = {Anant Dhayal and Jayalal Sarma and Saurabh Sawlani}, title = {Min/Max-Poly Weighting Schemes and the {NL} versus {UL} Problem}, journal = {{ACM} Trans. Comput. Theory}, volume = {9}, number = {2}, pages = {10:1--10:25}, year = {2017}, url = {https://doi.org/10.1145/3070902}, doi = {10.1145/3070902}, timestamp = {Mon, 08 Jun 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/DhayalSS17.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/ElberfeldS17, author = {Michael Elberfeld and Pascal Schweitzer}, title = {Canonizing Graphs of Bounded Tree Width in Logspace}, journal = {{ACM} Trans. Comput. Theory}, volume = {9}, number = {3}, pages = {12:1--12:29}, year = {2017}, url = {https://doi.org/10.1145/3132720}, doi = {10.1145/3132720}, timestamp = {Sun, 04 Aug 2024 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/ElberfeldS17.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/GalanisGJ17, author = {Andreas Galanis and Leslie Ann Goldberg and Mark Jerrum}, title = {A Complexity Trichotomy for Approximately Counting List \emph{H}-Colorings}, journal = {{ACM} Trans. Comput. Theory}, volume = {9}, number = {2}, pages = {9:1--9:22}, year = {2017}, url = {https://doi.org/10.1145/3037381}, doi = {10.1145/3037381}, timestamp = {Mon, 08 Jun 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/GalanisGJ17.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/GurjarKMT17, author = {Rohit Gurjar and Arpita Korwar and Jochen Messner and Thomas Thierauf}, title = {Exact Perfect Matching in Complete Graphs}, journal = {{ACM} Trans. Comput. Theory}, volume = {9}, number = {2}, pages = {8:1--8:20}, year = {2017}, url = {https://doi.org/10.1145/3041402}, doi = {10.1145/3041402}, timestamp = {Mon, 08 Jun 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/GurjarKMT17.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/Schmid17, author = {Markus L. Schmid}, title = {Finding Consensus Strings with Small Length Difference between Input and Solution Strings}, journal = {{ACM} Trans. Comput. Theory}, volume = {9}, number = {3}, pages = {13:1--13:18}, year = {2017}, url = {https://doi.org/10.1145/3110290}, doi = {10.1145/3110290}, timestamp = {Mon, 08 Jun 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/Schmid17.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/0001GR16, author = {Andreas G{\"{o}}bel and Leslie Ann Goldberg and David Richerby}, title = {Counting Homomorphisms to Square-Free Graphs, Modulo 2}, journal = {{ACM} Trans. Comput. Theory}, volume = {8}, number = {3}, pages = {12:1--12:29}, year = {2016}, url = {https://doi.org/10.1145/2898441}, doi = {10.1145/2898441}, timestamp = {Sun, 02 Oct 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/0001GR16.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/0001MS16, author = {Mrinal Kumar and Gaurav Maheshwari and Jayalal Sarma}, title = {Arithmetic Circuit Lower Bounds via Maximum-Rank of Partial Derivative Matrices}, journal = {{ACM} Trans. Comput. Theory}, volume = {8}, number = {3}, pages = {8:1--8:17}, year = {2016}, url = {https://doi.org/10.1145/2898437}, doi = {10.1145/2898437}, timestamp = {Mon, 08 Jun 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/0001MS16.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/Ailon16, author = {Nir Ailon}, title = {An Omega((n log n)/R) Lower Bound for Fourier Transform Computation in the R-Well Conditioned Model}, journal = {{ACM} Trans. Comput. Theory}, volume = {8}, number = {1}, pages = {4:1--4:14}, year = {2016}, url = {https://doi.org/10.1145/2858785}, doi = {10.1145/2858785}, timestamp = {Mon, 08 Jun 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/Ailon16.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/ArvindJR16, author = {Vikraman Arvind and Pushkar S. Joglekar and S. Raja}, title = {Noncommutative Valiant's Classes: Structure and Complete Problems}, journal = {{ACM} Trans. Comput. Theory}, volume = {9}, number = {1}, pages = {3:1--3:29}, year = {2016}, url = {https://doi.org/10.1145/2956230}, doi = {10.1145/2956230}, timestamp = {Mon, 08 Jun 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/ArvindJR16.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/BeameGMS16, author = {Paul Beame and Nathan Grosshans and Pierre McKenzie and Luc Segoufin}, title = {Nondeterminism and An Abstract Formulation of Ne{\v{c}}iporuk's Lower Bound Method}, journal = {{ACM} Trans. Comput. Theory}, volume = {9}, number = {1}, pages = {5:1--5:34}, year = {2016}, url = {https://doi.org/10.1145/3013516}, doi = {10.1145/3013516}, timestamp = {Mon, 26 Oct 2020 00:00:00 +0100}, biburl = {https://dblp.org/rec/journals/toct/BeameGMS16.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/CaragiannisKK16, author = {Ioannis Caragiannis and Christos Kaklamanis and Maria Kyropoulou}, title = {Limitations of Deterministic Auction Design for Correlated Bidders}, journal = {{ACM} Trans. Comput. Theory}, volume = {8}, number = {4}, pages = {13:1--13:18}, year = {2016}, url = {https://doi.org/10.1145/2934309}, doi = {10.1145/2934309}, timestamp = {Mon, 08 Jun 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/CaragiannisKK16.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/FellowsHRS16, author = {Michael R. Fellows and Danny Hermelin and Frances A. Rosamond and Hadas Shachnai}, title = {Tractable Parameterizations for the Minimum Linear Arrangement Problem}, journal = {{ACM} Trans. Comput. Theory}, volume = {8}, number = {2}, pages = {6:1--6:12}, year = {2016}, url = {https://doi.org/10.1145/2898352}, doi = {10.1145/2898352}, timestamp = {Mon, 08 Jun 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/FellowsHRS16.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/FischerGL16, author = {Eldar Fischer and Yonatan Goldhirsh and Oded Lachish}, title = {Testing Read-Once Formula Satisfaction}, journal = {{ACM} Trans. Comput. Theory}, volume = {8}, number = {2}, pages = {5:1--5:26}, year = {2016}, url = {https://doi.org/10.1145/2897184}, doi = {10.1145/2897184}, timestamp = {Sun, 04 Aug 2024 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/FischerGL16.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/FontesJKLLR16, author = {Lila Fontes and Rahul Jain and Iordanis Kerenidis and Sophie Laplante and Mathieu Lauri{\`{e}}re and J{\'{e}}r{\'{e}}mie Roland}, title = {Relative Discrepancy Does Not Separate Information and Communication Complexity}, journal = {{ACM} Trans. Comput. Theory}, volume = {9}, number = {1}, pages = {4:1--4:15}, year = {2016}, url = {https://doi.org/10.1145/2967605}, doi = {10.1145/2967605}, timestamp = {Mon, 08 Jun 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/FontesJKLLR16.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/FullaZ16, author = {Peter Fulla and Stanislav Zivn{\'{y}}}, title = {A Galois Connection for Weighted (Relational) Clones of Infinite Size}, journal = {{ACM} Trans. Comput. Theory}, volume = {8}, number = {3}, pages = {9:1--9:21}, year = {2016}, url = {https://doi.org/10.1145/2898438}, doi = {10.1145/2898438}, timestamp = {Mon, 03 Aug 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/FullaZ16.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/GalJLMS16, author = {Anna G{\'{a}}l and Jing{-}Tang Jang and Nutan Limaye and Meena Mahajan and Karteek Sreenivasaiah}, title = {Space-Efficient Approximations for Subset Sum}, journal = {{ACM} Trans. Comput. Theory}, volume = {8}, number = {4}, pages = {16:1--16:28}, year = {2016}, url = {https://doi.org/10.1145/2894843}, doi = {10.1145/2894843}, timestamp = {Sat, 30 Sep 2023 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/GalJLMS16.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/GoldreichR16, author = {Oded Goldreich and Dana Ron}, title = {On Sample-Based Testers}, journal = {{ACM} Trans. Comput. Theory}, volume = {8}, number = {2}, pages = {7:1--7:54}, year = {2016}, url = {https://doi.org/10.1145/2898355}, doi = {10.1145/2898355}, timestamp = {Mon, 08 Jun 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/GoldreichR16.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/GurjarKMST16, author = {Rohit Gurjar and Arpita Korwar and Jochen Messner and Simon Straub and Thomas Thierauf}, title = {Planarizing Gadgets for Perfect Matching Do Not Exist}, journal = {{ACM} Trans. Comput. Theory}, volume = {8}, number = {4}, pages = {14:1--14:15}, year = {2016}, url = {https://doi.org/10.1145/2934310}, doi = {10.1145/2934310}, timestamp = {Mon, 08 Jun 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/GurjarKMST16.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/HavivR16, author = {Ishay Haviv and Oded Regev}, title = {The List-Decoding Size of Fourier-Sparse Boolean Functions}, journal = {{ACM} Trans. Comput. Theory}, volume = {8}, number = {3}, pages = {10:1--10:14}, year = {2016}, url = {https://doi.org/10.1145/2898439}, doi = {10.1145/2898439}, timestamp = {Mon, 08 Jun 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/HavivR16.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/Hrubes16, author = {Pavel Hrubes}, title = {On Hardness of Multilinearization and VNP-Completeness in Characteristic 2}, journal = {{ACM} Trans. Comput. Theory}, volume = {9}, number = {1}, pages = {1:1--1:14}, year = {2016}, url = {https://doi.org/10.1145/2940323}, doi = {10.1145/2940323}, timestamp = {Mon, 08 Jun 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/Hrubes16.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/KratschMW16, author = {Stefan Kratsch and D{\'{a}}niel Marx and Magnus Wahlstr{\"{o}}m}, title = {Parameterized Complexity and Kernelizability of Max Ones and Exact Ones Problems}, journal = {{ACM} Trans. Comput. Theory}, volume = {8}, number = {1}, pages = {1:1--1:28}, year = {2016}, url = {https://doi.org/10.1145/2858787}, doi = {10.1145/2858787}, timestamp = {Mon, 08 Jun 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/KratschMW16.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/KrebsLMS16, author = {Andreas Krebs and Nutan Limaye and Meena Mahajan and Karteek Sreenivasaiah}, title = {Small Depth Proof Systems}, journal = {{ACM} Trans. Comput. Theory}, volume = {9}, number = {1}, pages = {2:1--2:26}, year = {2016}, url = {https://doi.org/10.1145/2956229}, doi = {10.1145/2956229}, timestamp = {Sat, 30 Sep 2023 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/KrebsLMS16.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/Lauria16, author = {Massimo Lauria}, title = {A Rank Lower Bound for Cutting Planes Proofs of Ramsey's Theorem}, journal = {{ACM} Trans. Comput. Theory}, volume = {8}, number = {4}, pages = {17:1--17:13}, year = {2016}, url = {https://doi.org/10.1145/2903266}, doi = {10.1145/2903266}, timestamp = {Mon, 08 Jun 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/Lauria16.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/NguyenS16, author = {Dung T. Nguyen and Alan L. Selman}, title = {Structural Properties of Nonautoreducible Sets}, journal = {{ACM} Trans. Comput. Theory}, volume = {8}, number = {3}, pages = {11:1--11:24}, year = {2016}, url = {https://doi.org/10.1145/2898440}, doi = {10.1145/2898440}, timestamp = {Mon, 08 Jun 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/NguyenS16.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/RonT16, author = {Dana Ron and Gilad Tsur}, title = {The Power of an Example: Hidden Set Size Approximation Using Group Queries and Conditional Sampling}, journal = {{ACM} Trans. Comput. Theory}, volume = {8}, number = {4}, pages = {15:1--15:19}, year = {2016}, url = {https://doi.org/10.1145/2930657}, doi = {10.1145/2930657}, timestamp = {Mon, 08 Jun 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/RonT16.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/Schmitz16, author = {Sylvain Schmitz}, title = {Complexity Hierarchies beyond Elementary}, journal = {{ACM} Trans. Comput. Theory}, volume = {8}, number = {1}, pages = {3:1--3:36}, year = {2016}, url = {https://doi.org/10.1145/2858784}, doi = {10.1145/2858784}, timestamp = {Mon, 08 Jun 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/Schmitz16.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/Viola16, author = {Emanuele Viola}, title = {Quadratic Maps Are Hard to Sample}, journal = {{ACM} Trans. Comput. Theory}, volume = {8}, number = {4}, pages = {18:1--18:4}, year = {2016}, url = {https://doi.org/10.1145/2934308}, doi = {10.1145/2934308}, timestamp = {Mon, 08 Jun 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/Viola16.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/Volkovich16, author = {Ilya Volkovich}, title = {Characterizing Arithmetic Read-Once Formulae}, journal = {{ACM} Trans. Comput. Theory}, volume = {8}, number = {1}, pages = {2:1--2:19}, year = {2016}, url = {https://doi.org/10.1145/2858783}, doi = {10.1145/2858783}, timestamp = {Sat, 30 Sep 2023 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/Volkovich16.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/AmbainisGSU15, author = {Andris Ambainis and William I. Gasarch and Aravind Srinivasan and Andrey Utis}, title = {Lower Bounds on the Deterministic and Quantum Communication Complexity of Hamming-Distance Problems}, journal = {{ACM} Trans. Comput. Theory}, volume = {7}, number = {3}, pages = {10:1--10:10}, year = {2015}, url = {https://doi.org/10.1145/2698587}, doi = {10.1145/2698587}, timestamp = {Mon, 08 Jun 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/AmbainisGSU15.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/BlaserM15, author = {Markus Bl{\"{a}}ser and Bodo Manthey}, title = {Smoothed Complexity Theory}, journal = {{ACM} Trans. Comput. Theory}, volume = {7}, number = {2}, pages = {6:1--6:21}, year = {2015}, url = {https://doi.org/10.1145/2656210}, doi = {10.1145/2656210}, timestamp = {Mon, 08 Jun 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/BlaserM15.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/CaseL15, author = {Adam Case and Jack H. Lutz}, title = {Mutual Dimension}, journal = {{ACM} Trans. Comput. Theory}, volume = {7}, number = {3}, pages = {12:1--12:26}, year = {2015}, url = {https://doi.org/10.1145/2786566}, doi = {10.1145/2786566}, timestamp = {Mon, 08 Jun 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/CaseL15.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/ChenM15, author = {Hubie Chen and Moritz M{\"{u}}ller}, title = {The Fine Classification of Conjunctive Queries and Parameterized Logarithmic Space}, journal = {{ACM} Trans. Comput. Theory}, volume = {7}, number = {2}, pages = {7:1--7:27}, year = {2015}, url = {https://doi.org/10.1145/2751316}, doi = {10.1145/2751316}, timestamp = {Mon, 08 Jun 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/ChenM15.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/DrangeFPV15, author = {P{\aa}l Gr{\o}n{\aa}s Drange and Fedor V. Fomin and Michal Pilipczuk and Yngve Villanger}, title = {Exploring the Subexponential Complexity of Completion Problems}, journal = {{ACM} Trans. Comput. Theory}, volume = {7}, number = {4}, pages = {14:1--14:38}, year = {2015}, url = {https://doi.org/10.1145/2799640}, doi = {10.1145/2799640}, timestamp = {Mon, 08 Jun 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/DrangeFPV15.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/FernauLR15, author = {Henning Fernau and Alejandro L{\'{o}}pez{-}Ortiz and Jazm{\'{\i}}n Romero}, title = {Using Parametric Transformations Toward Polynomial Kernels for Packing Problems Allowing Overlaps}, journal = {{ACM} Trans. Comput. Theory}, volume = {7}, number = {3}, pages = {13:1--13:29}, year = {2015}, url = {https://doi.org/10.1145/2786015}, doi = {10.1145/2786015}, timestamp = {Tue, 21 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/journals/toct/FernauLR15.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/FilmusPS15, author = {Yuval Filmus and Toniann Pitassi and Rahul Santhanam}, title = {Exponential Lower Bounds for AC\({}^{\mbox{0}}\)-Frege Imply Superpolynomial Frege Lower Bounds}, journal = {{ACM} Trans. Comput. Theory}, volume = {7}, number = {2}, pages = {5:1--5:16}, year = {2015}, url = {https://doi.org/10.1145/2656209}, doi = {10.1145/2656209}, timestamp = {Mon, 08 Jun 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/FilmusPS15.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/GoldreichM15, author = {Oded Goldreich and Or Meir}, title = {Input-Oblivious Proof Systems and a Uniform Complexity Perspective on P/poly}, journal = {{ACM} Trans. Comput. Theory}, volume = {7}, number = {4}, pages = {16:1--16:13}, year = {2015}, url = {https://doi.org/10.1145/2799645}, doi = {10.1145/2799645}, timestamp = {Mon, 08 Jun 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/GoldreichM15.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/JerrumM15, author = {Mark Jerrum and Kitty Meeks}, title = {Some Hard Families of Parameterized Counting Problems}, journal = {{ACM} Trans. Comput. Theory}, volume = {7}, number = {3}, pages = {11:1--11:18}, year = {2015}, url = {https://doi.org/10.1145/2786017}, doi = {10.1145/2786017}, timestamp = {Mon, 08 Jun 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/JerrumM15.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/KomarathS15, author = {Balagopal Komarath and Jayalal Sarma}, title = {Pebbling, Entropy, and Branching Program Size Lower Bounds}, journal = {{ACM} Trans. Comput. Theory}, volume = {7}, number = {2}, pages = {8:1--8:21}, year = {2015}, url = {https://doi.org/10.1145/2751320}, doi = {10.1145/2751320}, timestamp = {Mon, 08 Jun 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/KomarathS15.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/ODonnellWZ15, author = {Ryan O'Donnell and Yi Wu and Yuan Zhou}, title = {Hardness of Max-2Lin and Max-3Lin over Integers, Reals, and Large Cyclic Groups}, journal = {{ACM} Trans. Comput. Theory}, volume = {7}, number = {2}, pages = {9:1--9:16}, year = {2015}, url = {https://doi.org/10.1145/2751322}, doi = {10.1145/2751322}, timestamp = {Mon, 08 Jun 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/ODonnellWZ15.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/RegevV15, author = {Oded Regev and Thomas Vidick}, title = {Quantum {XOR} Games}, journal = {{ACM} Trans. Comput. Theory}, volume = {7}, number = {4}, pages = {15:1--15:43}, year = {2015}, url = {https://doi.org/10.1145/2799560}, doi = {10.1145/2799560}, timestamp = {Mon, 08 Jun 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/RegevV15.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/TeutschZ15, author = {Jason Teutsch and Marius Zimand}, title = {On Approximate Decidability of Minimal Programs}, journal = {{ACM} Trans. Comput. Theory}, volume = {7}, number = {4}, pages = {17:1--17:16}, year = {2015}, url = {https://doi.org/10.1145/2799561}, doi = {10.1145/2799561}, timestamp = {Mon, 08 Jun 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/TeutschZ15.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/0001GR14, author = {Andreas G{\"{o}}bel and Leslie Ann Goldberg and David Richerby}, title = {The complexity of counting homomorphisms to cactus graphs modulo 2}, journal = {{ACM} Trans. Comput. Theory}, volume = {6}, number = {4}, pages = {17:1--17:29}, year = {2014}, url = {https://doi.org/10.1145/2635825}, doi = {10.1145/2635825}, timestamp = {Sun, 02 Oct 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/0001GR14.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/AdaCCFKP14, author = {Anil Ada and Arkadev Chattopadhyay and Stephen A. Cook and Lila Fontes and Michal Kouck{\'{y}} and Toniann Pitassi}, title = {The Hardness of Being Private}, journal = {{ACM} Trans. Comput. Theory}, volume = {6}, number = {1}, pages = {1:1--1:24}, year = {2014}, url = {https://doi.org/10.1145/2567671}, doi = {10.1145/2567671}, timestamp = {Thu, 02 Jul 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/AdaCCFKP14.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/AllenderG14, author = {Eric Allender and Shafi Goldwasser}, title = {Introduction to the Special Issue on Innovations in Theoretical Computer Science 2012 - Part {II}}, journal = {{ACM} Trans. Comput. Theory}, volume = {6}, number = {3}, pages = {10:1}, year = {2014}, url = {https://doi.org/10.1145/2638595}, doi = {10.1145/2638595}, timestamp = {Fri, 09 Apr 2021 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/AllenderG14.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/AustrinOTW14, author = {Per Austrin and Ryan O'Donnell and Li{-}Yang Tan and John Wright}, title = {New NP-Hardness Results for 3-Coloring and 2-to-1 Label Cover}, journal = {{ACM} Trans. Comput. Theory}, volume = {6}, number = {1}, pages = {2:1--2:20}, year = {2014}, url = {https://doi.org/10.1145/2537800}, doi = {10.1145/2537800}, timestamp = {Mon, 08 Jun 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/AustrinOTW14.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/AwasthiJMR14, author = {Pranjal Awasthi and Madhav Jha and Marco Molinaro and Sofya Raskhodnikova}, title = {Limitations of Local Filters of Lipschitz and Monotone Functions}, journal = {{ACM} Trans. Comput. Theory}, volume = {7}, number = {1}, pages = {2:1--2:16}, year = {2014}, url = {https://doi.org/10.1145/2692372.2692373}, doi = {10.1145/2692372.2692373}, timestamp = {Sat, 05 Mar 2022 00:00:00 +0100}, biburl = {https://dblp.org/rec/journals/toct/AwasthiJMR14.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/BrakerskiGV14, author = {Zvika Brakerski and Craig Gentry and Vinod Vaikuntanathan}, title = {(Leveled) Fully Homomorphic Encryption without Bootstrapping}, journal = {{ACM} Trans. Comput. Theory}, volume = {6}, number = {3}, pages = {13:1--13:36}, year = {2014}, url = {https://doi.org/10.1145/2633600}, doi = {10.1145/2633600}, timestamp = {Mon, 08 Jun 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/BrakerskiGV14.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/ChenFM14, author = {Yijia Chen and J{\"{o}}rg Flum and Moritz M{\"{u}}ller}, title = {Hard Instances of Algorithms and Proof Systems}, journal = {{ACM} Trans. Comput. Theory}, volume = {6}, number = {2}, pages = {7:1--7:25}, year = {2014}, url = {https://doi.org/10.1145/2601336}, doi = {10.1145/2601336}, timestamp = {Mon, 08 Jun 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/ChenFM14.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/CookEMT14, author = {James Cook and Omid Etesami and Rachel Miller and Luca Trevisan}, title = {On the One-Way Function Candidate Proposed by Goldreich}, journal = {{ACM} Trans. Comput. Theory}, volume = {6}, number = {3}, pages = {14:1--14:35}, year = {2014}, url = {https://doi.org/10.1145/2633602}, doi = {10.1145/2633602}, timestamp = {Mon, 08 Jun 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/CookEMT14.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/CookFL14, author = {Stephen A. Cook and Yuval Filmus and Dai Tri Man Le}, title = {The complexity of the comparator circuit value problem}, journal = {{ACM} Trans. Comput. Theory}, volume = {6}, number = {4}, pages = {15:1--15:44}, year = {2014}, url = {https://doi.org/10.1145/2635822}, doi = {10.1145/2635822}, timestamp = {Mon, 08 Jun 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/CookFL14.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/CyganKPPW14, author = {Marek Cygan and Stefan Kratsch and Marcin Pilipczuk and Michal Pilipczuk and Magnus Wahlstr{\"{o}}m}, title = {Clique Cover and Graph Separation: New Incompressibility Results}, journal = {{ACM} Trans. Comput. Theory}, volume = {6}, number = {2}, pages = {6:1--6:19}, year = {2014}, url = {https://doi.org/10.1145/2594439}, doi = {10.1145/2594439}, timestamp = {Sun, 25 Jul 2021 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/CyganKPPW14.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/EtessamiSY14, author = {Kousha Etessami and Alistair Stewart and Mihalis Yannakakis}, title = {A Note on the Complexity of Comparing Succinctly Represented Integers, with an Application to Maximum Probability Parsing}, journal = {{ACM} Trans. Comput. Theory}, volume = {6}, number = {2}, pages = {9:1--9:23}, year = {2014}, url = {https://doi.org/10.1145/2601327}, doi = {10.1145/2601327}, timestamp = {Mon, 08 Jun 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/EtessamiSY14.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/FellowsJ14, author = {Michael R. Fellows and Bart M. P. Jansen}, title = {{FPT} is characterized by useful obstruction sets: Connecting algorithms, kernels, and quasi-orders}, journal = {{ACM} Trans. Comput. Theory}, volume = {6}, number = {4}, pages = {16:1--16:26}, year = {2014}, url = {https://doi.org/10.1145/2635820}, doi = {10.1145/2635820}, timestamp = {Mon, 08 Jun 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/FellowsJ14.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/GlasserHPT14, author = {Christian Gla{\ss}er and John M. Hitchcock and Aduri Pavan and Stephen D. Travers}, title = {Unions of Disjoint NP-Complete Sets}, journal = {{ACM} Trans. Comput. Theory}, volume = {6}, number = {1}, pages = {3:1--3:10}, year = {2014}, url = {https://doi.org/10.1145/2591508}, doi = {10.1145/2591508}, timestamp = {Tue, 07 May 2024 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/GlasserHPT14.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/GoldbergJ14, author = {Leslie Ann Goldberg and Mark Jerrum}, title = {The Complexity of Approximately Counting Tree Homomorphisms}, journal = {{ACM} Trans. Comput. Theory}, volume = {6}, number = {2}, pages = {8:1--8:31}, year = {2014}, url = {https://doi.org/10.1145/2600917}, doi = {10.1145/2600917}, timestamp = {Mon, 08 Jun 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/GoldbergJ14.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/GrecoMPS14, author = {Gianluigi Greco and Enrico Malizia and Luigi Palopoli and Francesco Scarcello}, title = {The Complexity of the Nucleolus in Compact Games}, journal = {{ACM} Trans. Comput. Theory}, volume = {7}, number = {1}, pages = {3:1--3:52}, year = {2014}, url = {https://doi.org/10.1145/2692372.2692374}, doi = {10.1145/2692372.2692374}, timestamp = {Mon, 18 Jul 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/GrecoMPS14.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/KanadeS14, author = {Varun Kanade and Thomas Steinke}, title = {Learning Hurdles for Sleeping Experts}, journal = {{ACM} Trans. Comput. Theory}, volume = {6}, number = {3}, pages = {11:1--11:16}, year = {2014}, url = {https://doi.org/10.1145/2505983}, doi = {10.1145/2505983}, timestamp = {Sun, 14 Mar 2021 00:00:00 +0100}, biburl = {https://dblp.org/rec/journals/toct/KanadeS14.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/KratschPRR14, author = {Stefan Kratsch and Marcin Pilipczuk and Ashutosh Rai and Venkatesh Raman}, title = {Kernel Lower Bounds using Co-Nondeterminism: Finding Induced Hereditary Subgraphs}, journal = {{ACM} Trans. Comput. Theory}, volume = {7}, number = {1}, pages = {4:1--4:18}, year = {2014}, url = {https://doi.org/10.1145/2691321}, doi = {10.1145/2691321}, timestamp = {Mon, 08 Jun 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/KratschPRR14.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/ODonnellWZ14, author = {Ryan O'Donnell and Yi Wu and Yuan Zhou}, title = {Optimal Lower Bounds for Locality-Sensitive Hashing (Except When q is Tiny)}, journal = {{ACM} Trans. Comput. Theory}, volume = {6}, number = {1}, pages = {5:1--5:13}, year = {2014}, url = {https://doi.org/10.1145/2578221}, doi = {10.1145/2578221}, timestamp = {Mon, 08 Jun 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/ODonnellWZ14.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/SunZ14, author = {Shu{-}Ming Sun and Ning Zhong}, title = {On Effective Convergence of Numerical Solutions for Differential Equations}, journal = {{ACM} Trans. Comput. Theory}, volume = {6}, number = {1}, pages = {4:1--4:25}, year = {2014}, url = {https://doi.org/10.1145/2578219}, doi = {10.1145/2578219}, timestamp = {Mon, 08 Jun 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/SunZ14.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/Valiant14, author = {Paul Valiant}, title = {Evolvability of Real Functions}, journal = {{ACM} Trans. Comput. Theory}, volume = {6}, number = {3}, pages = {12:1--12:19}, year = {2014}, url = {https://doi.org/10.1145/2633598}, doi = {10.1145/2633598}, timestamp = {Mon, 08 Jun 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/Valiant14.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/Watson14, author = {Thomas Watson}, title = {Advice Lower Bounds for the Dense Model Theorem}, journal = {{ACM} Trans. Comput. Theory}, volume = {7}, number = {1}, pages = {1:1--1:18}, year = {2014}, url = {https://doi.org/10.1145/2676659}, doi = {10.1145/2676659}, timestamp = {Mon, 08 Jun 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/Watson14.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/AllenderG13, author = {Eric Allender and Shafi Goldwasser}, title = {Introduction to the special issue on innovations in theoretical computer science 2012}, journal = {{ACM} Trans. Comput. Theory}, volume = {5}, number = {3}, pages = {8:1}, year = {2013}, url = {https://doi.org/10.1145/2493252.2493253}, doi = {10.1145/2493252.2493253}, timestamp = {Fri, 09 Apr 2021 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/AllenderG13.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/AustrinH13, author = {Per Austrin and Johan H{\aa}stad}, title = {On the usefulness of predicates}, journal = {{ACM} Trans. Comput. Theory}, volume = {5}, number = {1}, pages = {1:1--1:24}, year = {2013}, url = {https://doi.org/10.1145/2462896.2462897}, doi = {10.1145/2462896.2462897}, timestamp = {Mon, 08 Jun 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/AustrinH13.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/BeyersdorffDKMSSTV13, author = {Olaf Beyersdorff and Samir Datta and Andreas Krebs and Meena Mahajan and Gido Scharfenberger{-}Fabian and Karteek Sreenivasaiah and Michael Thomas and Heribert Vollmer}, title = {Verifying proofs in constant depth}, journal = {{ACM} Trans. Comput. Theory}, volume = {5}, number = {1}, pages = {2:1--2:23}, year = {2013}, url = {https://doi.org/10.1145/2462896.2462898}, doi = {10.1145/2462896.2462898}, timestamp = {Sat, 30 Sep 2023 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/BeyersdorffDKMSSTV13.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/BogdanovKT13, author = {Andrej Bogdanov and Akinori Kawachi and Hidetoki Tanaka}, title = {Hard Functions for Low-Degree Polynomials over Prime Fields}, journal = {{ACM} Trans. Comput. Theory}, volume = {5}, number = {2}, pages = {5:1--5:15}, year = {2013}, url = {https://doi.org/10.1145/2493246.2493248}, doi = {10.1145/2493246.2493248}, timestamp = {Mon, 08 Jun 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/BogdanovKT13.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/ChattopadhyayTW13, author = {Arkadev Chattopadhyay and Jacobo Tor{\'{a}}n and Fabian Wagner}, title = {Graph Isomorphism is Not AC0-Reducible to Group Isomorphism}, journal = {{ACM} Trans. Comput. Theory}, volume = {5}, number = {4}, pages = {13:1--13:13}, year = {2013}, url = {https://doi.org/10.1145/2540088}, doi = {10.1145/2540088}, timestamp = {Mon, 08 Jun 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/ChattopadhyayTW13.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/CyganPPW13, author = {Marek Cygan and Marcin Pilipczuk and Michal Pilipczuk and Jakub Onufry Wojtaszczyk}, title = {On multiway cut parameterized above lower bounds}, journal = {{ACM} Trans. Comput. Theory}, volume = {5}, number = {1}, pages = {3:1--3:11}, year = {2013}, url = {https://doi.org/10.1145/2462896.2462899}, doi = {10.1145/2462896.2462899}, timestamp = {Sun, 25 Jul 2021 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/CyganPPW13.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/DalmauK13, author = {V{\'{\i}}ctor Dalmau and Andrei A. Krokhin}, title = {Robust Satisfiability for CSPs: Hardness and Algorithmic Results}, journal = {{ACM} Trans. Comput. Theory}, volume = {5}, number = {4}, pages = {15:1--15:25}, year = {2013}, url = {https://doi.org/10.1145/2540090}, doi = {10.1145/2540090}, timestamp = {Mon, 08 Jun 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/DalmauK13.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/DeM13, author = {Anindya De and Elchanan Mossel}, title = {Explicit Optimal Hardness via Gaussian Stability Results}, journal = {{ACM} Trans. Comput. Theory}, volume = {5}, number = {4}, pages = {14:1--14:26}, year = {2013}, url = {https://doi.org/10.1145/2505766}, doi = {10.1145/2505766}, timestamp = {Mon, 08 Jun 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/DeM13.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/Drucker13, author = {Andrew Drucker}, title = {High-confidence predictions under adversarial uncertainty}, journal = {{ACM} Trans. Comput. Theory}, volume = {5}, number = {3}, pages = {12:1--12:18}, year = {2013}, url = {https://doi.org/10.1145/2493252.2493257}, doi = {10.1145/2493252.2493257}, timestamp = {Mon, 08 Jun 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/Drucker13.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/EnglertRSV13, author = {Matthias Englert and Heiko R{\"{o}}glin and Jacob Sp{\"{o}}nemann and Berthold V{\"{o}}cking}, title = {Economical Caching}, journal = {{ACM} Trans. Comput. Theory}, volume = {5}, number = {2}, pages = {4:1--4:21}, year = {2013}, url = {https://doi.org/10.1145/2493246.2493247}, doi = {10.1145/2493246.2493247}, timestamp = {Sat, 30 Sep 2023 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/EnglertRSV13.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/FellowsFLLRS13, author = {Michael R. Fellows and Fedor V. Fomin and Daniel Lokshtanov and Elena Losievskaja and Frances A. Rosamond and Saket Saurabh}, title = {Distortion is Fixed Parameter Tractable}, journal = {{ACM} Trans. Comput. Theory}, volume = {5}, number = {4}, pages = {16:1--16:20}, year = {2013}, url = {https://doi.org/10.1145/2489789}, doi = {10.1145/2489789}, timestamp = {Mon, 08 Jun 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/FellowsFLLRS13.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/HarkinsH13, author = {Ryan C. Harkins and John M. Hitchcock}, title = {Exact Learning Algorithms, Betting Games, and Circuit Lower Bounds}, journal = {{ACM} Trans. Comput. Theory}, volume = {5}, number = {4}, pages = {18:1--18:11}, year = {2013}, url = {https://doi.org/10.1145/2539126.2539130}, doi = {10.1145/2539126.2539130}, timestamp = {Tue, 07 May 2024 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/HarkinsH13.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/OzolsRR13, author = {Maris Ozols and Martin Roetteler and J{\'{e}}r{\'{e}}mie Roland}, title = {Quantum rejection sampling}, journal = {{ACM} Trans. Comput. Theory}, volume = {5}, number = {3}, pages = {11:1--11:33}, year = {2013}, url = {https://doi.org/10.1145/2493252.2493256}, doi = {10.1145/2493252.2493256}, timestamp = {Thu, 14 Oct 2021 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/OzolsRR13.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/Pagh13, author = {Rasmus Pagh}, title = {Compressed matrix multiplication}, journal = {{ACM} Trans. Comput. Theory}, volume = {5}, number = {3}, pages = {9:1--9:17}, year = {2013}, url = {https://doi.org/10.1145/2493252.2493254}, doi = {10.1145/2493252.2493254}, timestamp = {Mon, 08 Jun 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/Pagh13.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/RazborovV13, author = {Alexander A. Razborov and Emanuele Viola}, title = {Real Advantage}, journal = {{ACM} Trans. Comput. Theory}, volume = {5}, number = {4}, pages = {17:1--17:8}, year = {2013}, url = {https://doi.org/10.1145/2540089}, doi = {10.1145/2540089}, timestamp = {Mon, 08 Jun 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/RazborovV13.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/RonT13, author = {Dana Ron and Gilad Tsur}, title = {On Approximating the Number of Relevant Variables in a Function}, journal = {{ACM} Trans. Comput. Theory}, volume = {5}, number = {2}, pages = {7:1--7:19}, year = {2013}, url = {https://doi.org/10.1145/2493246.2493250}, doi = {10.1145/2493246.2493250}, timestamp = {Mon, 08 Jun 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/RonT13.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/Viderman13, author = {Michael Viderman}, title = {Linear-time decoding of regular expander codes}, journal = {{ACM} Trans. Comput. Theory}, volume = {5}, number = {3}, pages = {10:1--10:25}, year = {2013}, url = {https://doi.org/10.1145/2493252.2493255}, doi = {10.1145/2493252.2493255}, timestamp = {Mon, 08 Jun 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/Viderman13.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/Williams13, author = {Ryan Williams}, title = {Alternation-Trading Proofs, Linear Programming, and Lower Bounds}, journal = {{ACM} Trans. Comput. Theory}, volume = {5}, number = {2}, pages = {6:1--6:49}, year = {2013}, url = {https://doi.org/10.1145/2493246.2493249}, doi = {10.1145/2493246.2493249}, timestamp = {Mon, 08 Jun 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/Williams13.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/BeameH12, author = {Paul Beame and Trinh Huynh}, title = {The Value of Multiple Read/Write Streams for Approximating Frequency Moments}, journal = {{ACM} Trans. Comput. Theory}, volume = {3}, number = {2}, pages = {6:1--6:22}, year = {2012}, url = {https://doi.org/10.1145/2077336.2077339}, doi = {10.1145/2077336.2077339}, timestamp = {Mon, 08 Jun 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/BeameH12.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/BeyersdorffGLR12, author = {Olaf Beyersdorff and Nicola Galesi and Massimo Lauria and Alexander A. Razborov}, title = {Parameterized Bounded-Depth Frege Is not Optimal}, journal = {{ACM} Trans. Comput. Theory}, volume = {4}, number = {3}, pages = {7:1--7:16}, year = {2012}, url = {https://doi.org/10.1145/2355580.2355582}, doi = {10.1145/2355580.2355582}, timestamp = {Mon, 08 Jun 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/BeyersdorffGLR12.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/CheraghchiHIS12, author = {Mahdi Cheraghchi and Johan H{\aa}stad and Marcus Isaksson and Ola Svensson}, title = {Approximating Linear Threshold Predicates}, journal = {{ACM} Trans. Comput. Theory}, volume = {4}, number = {1}, pages = {2:1--2:31}, year = {2012}, url = {https://doi.org/10.1145/2141938.2141940}, doi = {10.1145/2141938.2141940}, timestamp = {Mon, 08 Jun 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/CheraghchiHIS12.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/CookMWBS12, author = {Stephen A. Cook and Pierre McKenzie and Dustin Wehr and Mark Braverman and Rahul Santhanam}, title = {Pebbles and Branching Programs for Tree Evaluation}, journal = {{ACM} Trans. Comput. Theory}, volume = {3}, number = {2}, pages = {4:1--4:43}, year = {2012}, url = {https://doi.org/10.1145/2077336.2077337}, doi = {10.1145/2077336.2077337}, timestamp = {Mon, 08 Jun 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/CookMWBS12.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/DeW12, author = {Anindya De and Thomas Watson}, title = {Extractors and Lower Bounds for Locally Samplable Sources}, journal = {{ACM} Trans. Comput. Theory}, volume = {4}, number = {1}, pages = {3:1--3:21}, year = {2012}, url = {https://doi.org/10.1145/2141938.2141941}, doi = {10.1145/2141938.2141941}, timestamp = {Mon, 08 Jun 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/DeW12.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/GalM12, author = {Anna G{\'{a}}l and Andrew Mills}, title = {Three-Query Locally Decodable Codes with Higher Correctness Require Exponential Length}, journal = {{ACM} Trans. Comput. Theory}, volume = {3}, number = {2}, pages = {5:1--5:34}, year = {2012}, url = {https://doi.org/10.1145/2077336.2077338}, doi = {10.1145/2077336.2077338}, timestamp = {Mon, 08 Jun 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/GalM12.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/KawamuraC12, author = {Akitoshi Kawamura and Stephen A. Cook}, title = {Complexity Theory for Operators in Analysis}, journal = {{ACM} Trans. Comput. Theory}, volume = {4}, number = {2}, pages = {5:1--5:24}, year = {2012}, url = {https://doi.org/10.1145/2189778.2189780}, doi = {10.1145/2189778.2189780}, timestamp = {Mon, 08 Jun 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/KawamuraC12.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/KayalS12, author = {Neeraj Kayal and Chandan Saha}, title = {On the Sum of Square Roots of Polynomials and Related Problems}, journal = {{ACM} Trans. Comput. Theory}, volume = {4}, number = {4}, pages = {9:1--9:15}, year = {2012}, url = {https://doi.org/10.1145/2382559.2382560}, doi = {10.1145/2382559.2382560}, timestamp = {Mon, 08 Jun 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/KayalS12.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/PassV12, author = {Rafael Pass and Muthuramakrishnan Venkitasubramaniam}, title = {A Parallel Repetition Theorem for Constant-Round Arthur-Merlin Proofs}, journal = {{ACM} Trans. Comput. Theory}, volume = {4}, number = {4}, pages = {10:1--10:22}, year = {2012}, url = {https://doi.org/10.1145/2382559.2382561}, doi = {10.1145/2382559.2382561}, timestamp = {Mon, 26 Jun 2023 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/PassV12.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/PennaV12, author = {Paolo Penna and Carmine Ventre}, title = {Collusion-Resistant Mechanisms with Verification Yielding Optimal Solutions}, journal = {{ACM} Trans. Comput. Theory}, volume = {4}, number = {2}, pages = {6:1--6:17}, year = {2012}, url = {https://doi.org/10.1145/2189778.2189781}, doi = {10.1145/2189778.2189781}, timestamp = {Mon, 08 Jun 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/PennaV12.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/RonRSSW12, author = {Dana Ron and Ronitt Rubinfeld and Muli Safra and Alex Samorodnitsky and Omri Weinstein}, title = {Approximating the Influence of Monotone Boolean Functions in O({\(\surd\)}n) Query Complexity}, journal = {{ACM} Trans. Comput. Theory}, volume = {4}, number = {4}, pages = {11:1--11:12}, year = {2012}, url = {https://doi.org/10.1145/2382559.2382562}, doi = {10.1145/2382559.2382562}, timestamp = {Sat, 30 Sep 2023 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/RonRSSW12.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/SchoenebeckV12, author = {Grant Schoenebeck and Salil P. Vadhan}, title = {The Computational Complexity of Nash Equilibria in Concisely Represented Games}, journal = {{ACM} Trans. Comput. Theory}, volume = {4}, number = {2}, pages = {4:1--4:50}, year = {2012}, url = {https://doi.org/10.1145/2189778.2189779}, doi = {10.1145/2189778.2189779}, timestamp = {Tue, 21 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/journals/toct/SchoenebeckV12.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/TaniKM12, author = {Seiichiro Tani and Hirotada Kobayashi and Keiji Matsumoto}, title = {Exact Quantum Algorithms for the Leader Election Problem}, journal = {{ACM} Trans. Comput. Theory}, volume = {4}, number = {1}, pages = {1:1--1:24}, year = {2012}, url = {https://doi.org/10.1145/2141938.2141939}, doi = {10.1145/2141938.2141939}, timestamp = {Sat, 05 Sep 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/TaniKM12.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/VlassisLB12, author = {Nikos Vlassis and Michael L. Littman and David Barber}, title = {On the Computational Complexity of Stochastic Controller Optimization in POMDPs}, journal = {{ACM} Trans. Comput. Theory}, volume = {4}, number = {4}, pages = {12:1--12:8}, year = {2012}, url = {https://doi.org/10.1145/2382559.2382563}, doi = {10.1145/2382559.2382563}, timestamp = {Mon, 08 Jun 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/VlassisLB12.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/Watson12, author = {Thomas Watson}, title = {Relativized Worlds without Worst-Case to Average-Case Reductions for {NP}}, journal = {{ACM} Trans. Comput. Theory}, volume = {4}, number = {3}, pages = {8:1--8:30}, year = {2012}, url = {https://doi.org/10.1145/2355580.2355583}, doi = {10.1145/2355580.2355583}, timestamp = {Mon, 08 Jun 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/Watson12.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/ArvindT11, author = {Vikraman Arvind and Jacobo Tor{\'{a}}n}, title = {Solvable Group Isomorphism Is (Almost) in {NP} {\(\cap\)} coNP}, journal = {{ACM} Trans. Comput. Theory}, volume = {2}, number = {2}, pages = {4:1--4:22}, year = {2011}, url = {https://doi.org/10.1145/1944857.1944859}, doi = {10.1145/1944857.1944859}, timestamp = {Mon, 08 Jun 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/ArvindT11.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/FellowsGMN11, author = {Michael R. Fellows and Jiong Guo and Hannes Moser and Rolf Niedermeier}, title = {A Complexity Dichotomy for Finding Disjoint Solutions of Vertex Deletion Problems}, journal = {{ACM} Trans. Comput. Theory}, volume = {2}, number = {2}, pages = {5:1--5:23}, year = {2011}, url = {https://doi.org/10.1145/1944857.1944860}, doi = {10.1145/1944857.1944860}, timestamp = {Mon, 08 Jun 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/FellowsGMN11.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/HitchcockPV11, author = {John M. Hitchcock and Aduri Pavan and N. Variyam Vinodchandran}, title = {Kolmogorov Complexity in Randomness Extraction}, journal = {{ACM} Trans. Comput. Theory}, volume = {3}, number = {1}, pages = {1:1--1:12}, year = {2011}, url = {https://doi.org/10.1145/2003685.2003686}, doi = {10.1145/2003685.2003686}, timestamp = {Tue, 07 May 2024 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/HitchcockPV11.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/Kulkarni11, author = {Raghav Kulkarni}, title = {On the Power of Isolation in Planar Graphs}, journal = {{ACM} Trans. Comput. Theory}, volume = {3}, number = {1}, pages = {2:1--2:12}, year = {2011}, url = {https://doi.org/10.1145/2003685.2003687}, doi = {10.1145/2003685.2003687}, timestamp = {Mon, 08 Jun 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/Kulkarni11.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/Purdy11, author = {Eric Purdy}, title = {Lower Bounds for Coin-Weighing Problems}, journal = {{ACM} Trans. Comput. Theory}, volume = {2}, number = {2}, pages = {3:1--3:12}, year = {2011}, url = {https://doi.org/10.1145/1944857.1944858}, doi = {10.1145/1944857.1944858}, timestamp = {Mon, 08 Jun 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/Purdy11.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/Smyth11, author = {Clifford D. Smyth}, title = {Approximate Query Complexity}, journal = {{ACM} Trans. Comput. Theory}, volume = {3}, number = {1}, pages = {3:1--3:11}, year = {2011}, url = {https://doi.org/10.1145/2003685.2003688}, doi = {10.1145/2003685.2003688}, timestamp = {Wed, 09 Aug 2023 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/Smyth11.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/BeameIPS10, author = {Paul Beame and Russell Impagliazzo and Toniann Pitassi and Nathan Segerlind}, title = {Formula Caching in {DPLL}}, journal = {{ACM} Trans. Comput. Theory}, volume = {1}, number = {3}, pages = {9:1--9:33}, year = {2010}, url = {https://doi.org/10.1145/1714450.1714452}, doi = {10.1145/1714450.1714452}, timestamp = {Tue, 07 May 2024 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/BeameIPS10.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/DattaKLM10, author = {Samir Datta and Raghav Kulkarni and Nutan Limaye and Meena Mahajan}, title = {Planarity, Determinants, Permanents, and (Unique) Matchings}, journal = {{ACM} Trans. Comput. Theory}, volume = {1}, number = {3}, pages = {10:1--10:20}, year = {2010}, url = {https://doi.org/10.1145/1714450.1714453}, doi = {10.1145/1714450.1714453}, timestamp = {Sun, 02 Oct 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/DattaKLM10.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/HoeferS10, author = {Martin Hoefer and Alexander Souza}, title = {Tradeoffs and Average-Case Equilibria in Selfish Routing}, journal = {{ACM} Trans. Comput. Theory}, volume = {2}, number = {1}, pages = {2:1--2:25}, year = {2010}, url = {https://doi.org/10.1145/1867719.1867721}, doi = {10.1145/1867719.1867721}, timestamp = {Fri, 26 Mar 2021 00:00:00 +0100}, biburl = {https://dblp.org/rec/journals/toct/HoeferS10.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/KynclV10, author = {Jan Kyncl and Tom{\'{a}}s Vyskocil}, title = {Logspace Reduction of Directed Reachability for Bounded Genus Graphs to the Planar Case}, journal = {{ACM} Trans. Comput. Theory}, volume = {1}, number = {3}, pages = {8:1--8:11}, year = {2010}, url = {https://doi.org/10.1145/1714450.1714451}, doi = {10.1145/1714450.1714451}, timestamp = {Mon, 08 Jun 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/KynclV10.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/Yin10, author = {Yitong Yin}, title = {Cell-Probe Proofs}, journal = {{ACM} Trans. Comput. Theory}, volume = {2}, number = {1}, pages = {1:1--1:17}, year = {2010}, url = {https://doi.org/10.1145/1867719.1867720}, doi = {10.1145/1867719.1867720}, timestamp = {Mon, 08 Jun 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/Yin10.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/AaronsonW09, author = {Scott Aaronson and Avi Wigderson}, title = {Algebrization: {A} New Barrier in Complexity Theory}, journal = {{ACM} Trans. Comput. Theory}, volume = {1}, number = {1}, pages = {2:1--2:54}, year = {2009}, url = {https://doi.org/10.1145/1490270.1490272}, doi = {10.1145/1490270.1490272}, timestamp = {Mon, 08 Jun 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/AaronsonW09.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/Ben-SassonHLM09, author = {Eli Ben{-}Sasson and Prahladh Harsha and Oded Lachish and Arie Matsliah}, title = {Sound 3-Query PCPPs Are Long}, journal = {{ACM} Trans. Comput. Theory}, volume = {1}, number = {2}, pages = {7:1--7:49}, year = {2009}, url = {https://doi.org/10.1145/1595391.1595394}, doi = {10.1145/1595391.1595394}, timestamp = {Sun, 04 Aug 2024 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/Ben-SassonHLM09.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/BourkeTV09, author = {Chris Bourke and Raghunath Tewari and N. V. Vinodchandran}, title = {Directed Planar Reachability Is in Unambiguous Log-Space}, journal = {{ACM} Trans. Comput. Theory}, volume = {1}, number = {1}, pages = {4:1--4:17}, year = {2009}, url = {https://doi.org/10.1145/1490270.1490274}, doi = {10.1145/1490270.1490274}, timestamp = {Mon, 08 Jun 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/BourkeTV09.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/DavidPV09, author = {Matei David and Toniann Pitassi and Emanuele Viola}, title = {Improved Separations between Nondeterministic and Randomized Multiparty Communication}, journal = {{ACM} Trans. Comput. Theory}, volume = {1}, number = {2}, pages = {5:1--5:20}, year = {2009}, url = {https://doi.org/10.1145/1595391.1595392}, doi = {10.1145/1595391.1595392}, timestamp = {Mon, 08 Jun 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/DavidPV09.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/Fortnow09, author = {Lance Fortnow}, title = {Editor's Foreword}, journal = {{ACM} Trans. Comput. Theory}, volume = {1}, number = {1}, pages = {1:1--1:2}, year = {2009}, url = {https://doi.org/10.1145/1490270.1490271}, doi = {10.1145/1490270.1490271}, timestamp = {Mon, 08 Jun 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/Fortnow09.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/GuruswamiR09, author = {Venkatesan Guruswami and Prasad Raghavendra}, title = {Hardness of Solving Sparse Overdetermined Linear Systems: {A} 3-Query {PCP} over Integers}, journal = {{ACM} Trans. Comput. Theory}, volume = {1}, number = {2}, pages = {6:1--6:20}, year = {2009}, url = {https://doi.org/10.1145/1595391.1595393}, doi = {10.1145/1595391.1595393}, timestamp = {Mon, 08 Jun 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/GuruswamiR09.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/Razborov09, author = {Alexander A. Razborov}, title = {A Simple Proof of Bazzi's Theorem}, journal = {{ACM} Trans. Comput. Theory}, volume = {1}, number = {1}, pages = {3:1--3:5}, year = {2009}, url = {https://doi.org/10.1145/1490270.1490273}, doi = {10.1145/1490270.1490273}, timestamp = {Mon, 08 Jun 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/Razborov09.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.