Stop the war!Остановите войну!
for scientists:
default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDSearch dblp for Publications
export results for "stream:journals/toct:"
download as .bib file
@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\'a\v{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 = {Wed, 18 May 2022 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, 15 Jun 2021 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 = {Mon, 26 Apr 2021 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 = {Tue, 08 Dec 2020 00:00:00 +0100},
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 = {Mon, 08 Jun 2020 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 = {Mon, 03 Jan 2022 00:00:00 +0100},
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 = {Mon, 08 Jun 2020 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 = {Mon, 08 Jun 2020 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 = {Fri, 09 Apr 2021 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 = {Mon, 08 Jun 2020 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 = {Mon, 08 Jun 2020 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 = {Sat, 30 Sep 2023 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 = {Mon, 08 Jun 2020 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}
}
a service of 
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.
retrieved on 2024-04-19 23:48 CEST from data curated by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
