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/toc:"
download as .bib file
@article{DBLP:journals/toc/0006LZ22,
author = {Xin Li and
Shachar Lovett and
Jiapeng Zhang},
title = {Sunflowers and Robust Sunflowers from Randomness Extractors},
journal = {Theory Comput.},
volume = {18},
pages = {1--18},
year = {2022},
url = {https://theoryofcomputing.org/articles/v018a002/},
timestamp = {Thu, 02 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/toc/0006LZ22.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/AustrinKK22,
author = {Per Austrin and
Petteri Kaski and
Kaie Kubjas},
title = {Tensor Network Complexity of Multilinear Maps},
journal = {Theory Comput.},
volume = {18},
pages = {1--54},
year = {2022},
url = {https://theoryofcomputing.org/articles/v018a016/},
timestamp = {Thu, 02 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/toc/AustrinKK22.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/BhangaleK22,
author = {Amey Bhangale and
Subhash Khot},
title = {UG-hardness to NP-hardness by Losing Half},
journal = {Theory Comput.},
volume = {18},
pages = {1--28},
year = {2022},
url = {https://theoryofcomputing.org/articles/v018a005/},
timestamp = {Thu, 02 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/toc/BhangaleK22.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/BravermanKY22,
author = {Vladimir Braverman and
Robert Krauthgamer and
Lin F. Yang},
title = {Universal Streaming of Subset Norms},
journal = {Theory Comput.},
volume = {18},
pages = {1--32},
year = {2022},
url = {https://theoryofcomputing.org/articles/v018a020/},
timestamp = {Thu, 02 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/toc/BravermanKY22.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/Chekuri022,
author = {Chandra Chekuri and
Tanmay Inamdar},
title = {Algorithms for Intersection Graphs for t-Intervals and t-Pseudodisks},
journal = {Theory Comput.},
volume = {18},
pages = {1--19},
year = {2022},
url = {https://theoryofcomputing.org/articles/v018a018/},
timestamp = {Thu, 02 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/toc/Chekuri022.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/ChenV22,
author = {Zongchen Chen and
Santosh S. Vempala},
title = {Optimal Convergence Rate of Hamiltonian Monte Carlo for Strongly Logconcave
Distributions},
journal = {Theory Comput.},
volume = {18},
pages = {1--18},
year = {2022},
url = {https://theoryofcomputing.org/articles/v018a009/},
timestamp = {Thu, 02 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/toc/ChenV22.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/ChengH22,
author = {Kuan Cheng and
William M. Hoza},
title = {Hitting Sets Give Two-Sided Derandomization of Small Space},
journal = {Theory Comput.},
volume = {18},
pages = {1--32},
year = {2022},
url = {https://theoryofcomputing.org/articles/v018a021/},
timestamp = {Thu, 02 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/toc/ChengH22.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/CoesterL22,
author = {Christian Coester and
James R. Lee},
title = {Pure Entropic Regularization for Metrical Task Systems},
journal = {Theory Comput.},
volume = {18},
pages = {1--24},
year = {2022},
url = {https://theoryofcomputing.org/articles/v018a023/},
timestamp = {Thu, 02 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/toc/CoesterL22.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/DinurHKR22,
author = {Irit Dinur and
Prahladh Harsha and
Tali Kaufman and
Noga Ron{-}Zewi},
title = {From Local to Robust Testing via Agreement Testing},
journal = {Theory Comput.},
volume = {18},
pages = {1--25},
year = {2022},
url = {https://theoryofcomputing.org/articles/v018a012/},
timestamp = {Thu, 02 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/toc/DinurHKR22.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/Drucker22,
author = {Andrew Drucker},
title = {Guest Editor's Foreword to the {RANDOM} 2018 Special Issue},
journal = {Theory Comput.},
volume = {18},
pages = {1--3},
year = {2022},
url = {https://theoryofcomputing.org/articles/v018a001/},
timestamp = {Thu, 02 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/toc/Drucker22.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/DvirT22,
author = {Zeev Dvir and
Avishay Tal},
title = {Guest Editors' Foreword to the {CCC} 2020 Special Issue},
journal = {Theory Comput.},
volume = {18},
pages = {1--4},
year = {2022},
url = {https://theoryofcomputing.org/articles/v018a014/},
timestamp = {Thu, 02 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/toc/DvirT22.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/EdenFF22,
author = {Alon Eden and
Uriel Feige and
Michal Feldman},
title = {Max-Min Greedy Matching},
journal = {Theory Comput.},
volume = {18},
pages = {1--33},
year = {2022},
url = {https://theoryofcomputing.org/articles/v018a006/},
timestamp = {Fri, 02 Jun 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/EdenFF22.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/Fleischer22,
author = {Lukas Fleischer},
title = {The Cayley Semigroup Membership Problem},
journal = {Theory Comput.},
volume = {18},
pages = {1--18},
year = {2022},
url = {https://theoryofcomputing.org/articles/v018a008/},
timestamp = {Thu, 02 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/toc/Fleischer22.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/GolovnevH22,
author = {Alexander Golovnev and
Ishay Haviv},
title = {The (Generalized) Orthogonality Dimension of (Generalized) Kneser
Graphs: Bounds and Applications},
journal = {Theory Comput.},
volume = {18},
pages = {1--22},
year = {2022},
url = {https://theoryofcomputing.org/articles/v018a022/},
timestamp = {Thu, 02 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/toc/GolovnevH22.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/HosseiniHL22,
author = {Kaave Hosseini and
Hamed Hatami and
Shachar Lovett},
title = {Sign-Rank vs. Discrepancy},
journal = {Theory Comput.},
volume = {18},
pages = {1--22},
year = {2022},
url = {https://theoryofcomputing.org/articles/v018a019/},
timestamp = {Thu, 02 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/toc/HosseiniHL22.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/Jeffery22,
author = {Stacey Jeffery},
title = {Span Programs and Quantum Space Complexity},
journal = {Theory Comput.},
volume = {18},
pages = {1--49},
year = {2022},
url = {https://theoryofcomputing.org/articles/v018a011/},
timestamp = {Thu, 02 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/toc/Jeffery22.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/KozachinskiyP22,
author = {Alexander Kozachinskiy and
Vladimir V. Podolskii},
title = {Multiparty Karchmer-Wigderson Games and Threshold Circuits},
journal = {Theory Comput.},
volume = {18},
pages = {1--33},
year = {2022},
url = {https://theoryofcomputing.org/articles/v018a015/},
timestamp = {Thu, 02 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/toc/KozachinskiyP22.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/Leshkowitz22,
author = {Maya Leshkowitz},
title = {Round Complexity Versus Randomness Complexity in Interactive Proofs},
journal = {Theory Comput.},
volume = {18},
pages = {1--65},
year = {2022},
url = {https://theoryofcomputing.org/articles/v018a013/},
timestamp = {Thu, 02 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/toc/Leshkowitz22.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/ManurangsiNT22,
author = {Pasin Manurangsi and
Preetum Nakkiran and
Luca Trevisan},
title = {Near-Optimal NP-Hardness of Approximating Max k-CSP\({}_{\mbox{R}}\)},
journal = {Theory Comput.},
volume = {18},
pages = {1--29},
year = {2022},
url = {https://theoryofcomputing.org/articles/v018a003/},
timestamp = {Thu, 02 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/toc/ManurangsiNT22.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/Quanrud22,
author = {Kent Quanrud},
title = {Fast and Deterministic Approximations for k-Cut},
journal = {Theory Comput.},
volume = {18},
pages = {1--24},
year = {2022},
url = {https://theoryofcomputing.org/articles/v018a007/},
timestamp = {Thu, 02 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/toc/Quanrud22.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/ServedioT22,
author = {Rocco A. Servedio and
Li{-}Yang Tan},
title = {Improved Pseudorandom Generators from Pseudorandom Multi-switching
Lemmas},
journal = {Theory Comput.},
volume = {18},
pages = {1--46},
year = {2022},
url = {https://theoryofcomputing.org/articles/v018a004/},
timestamp = {Thu, 02 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/toc/ServedioT22.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/Viola22,
author = {Emanuele Viola},
title = {Pseudorandom Bits and Lower Bounds for Randomized Turing Machines},
journal = {Theory Comput.},
volume = {18},
pages = {1--12},
year = {2022},
url = {https://theoryofcomputing.org/articles/v018a010/},
timestamp = {Thu, 02 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/toc/Viola22.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/Wu22,
author = {Xinyu Wu},
title = {A Stochastic Calculus Approach to the Oracle Separation of {BQP} and
{PH}},
journal = {Theory Comput.},
volume = {18},
pages = {1--11},
year = {2022},
url = {https://theoryofcomputing.org/articles/v018a017/},
timestamp = {Thu, 02 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/toc/Wu22.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/AbboudKT21,
author = {Amir Abboud and
Robert Krauthgamer and
Ohad Trabelsi},
title = {New Algorithms and Lower Bounds for All-Pairs Max-Flow in Undirected
Graphs},
journal = {Theory Comput.},
volume = {17},
pages = {1--27},
year = {2021},
url = {https://theoryofcomputing.org/articles/v017a005/},
timestamp = {Tue, 07 Dec 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/toc/AbboudKT21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/Alman21,
author = {Josh Alman},
title = {Limits on the Universal Method for Matrix Multiplication},
journal = {Theory Comput.},
volume = {17},
pages = {1--30},
year = {2021},
url = {https://theoryofcomputing.org/articles/v017a001/},
timestamp = {Tue, 07 Dec 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/toc/Alman21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/BunT21,
author = {Mark Bun and
Justin Thaler},
title = {The Large-Error Approximate Degree of AC\({}^{\mbox{0}}\)},
journal = {Theory Comput.},
volume = {17},
pages = {1--46},
year = {2021},
url = {https://theoryofcomputing.org/articles/v017a007/},
timestamp = {Tue, 07 Dec 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/toc/BunT21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/ChristandlVZ21,
author = {Matthias Christandl and
P{\'{e}}ter Vrana and
Jeroen Zuiddam},
title = {Barriers for Fast Matrix Multiplication from Irreversibility},
journal = {Theory Comput.},
volume = {17},
pages = {1--32},
year = {2021},
url = {https://theoryofcomputing.org/articles/v017a002/},
timestamp = {Tue, 07 Dec 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/toc/ChristandlVZ21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/ChuzhoyKN21,
author = {Julia Chuzhoy and
David Hong Kyun Kim and
Rachit Nimavat},
title = {Almost Polynomial Hardness of Node-Disjoint Paths in Grids},
journal = {Theory Comput.},
volume = {17},
pages = {1--57},
year = {2021},
url = {https://theoryofcomputing.org/articles/v017a006/},
timestamp = {Tue, 07 Dec 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/toc/ChuzhoyKN21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/ForbesSTW21,
author = {Michael A. Forbes and
Amir Shpilka and
Iddo Tzameret and
Avi Wigderson},
title = {Proof Complexity Lower Bounds from Algebraic Circuit Complexity},
journal = {Theory Comput.},
volume = {17},
pages = {1--88},
year = {2021},
url = {https://theoryofcomputing.org/articles/v017a010/},
timestamp = {Tue, 30 May 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/ForbesSTW21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/Gavinsky21,
author = {Dmitry Gavinsky},
title = {The Layer Complexity of Arthur-Merlin-like Communication},
journal = {Theory Comput.},
volume = {17},
pages = {1--28},
year = {2021},
url = {https://theoryofcomputing.org/articles/v017a008/},
timestamp = {Tue, 07 Dec 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/toc/Gavinsky21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/MurtaghRSV21,
author = {Jack Murtagh and
Omer Reingold and
Aaron Sidford and
Salil P. Vadhan},
title = {Deterministic Approximation of Random Walks in Small Space},
journal = {Theory Comput.},
volume = {17},
pages = {1--35},
year = {2021},
url = {https://theoryofcomputing.org/articles/v017a004/},
timestamp = {Tue, 07 Dec 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/toc/MurtaghRSV21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/ODonnellS21,
author = {Ryan O'Donnell and
Tselil Schramm},
title = {Sherali-Adams Strikes Back},
journal = {Theory Comput.},
volume = {17},
pages = {1--30},
year = {2021},
url = {https://theoryofcomputing.org/articles/v017a009/},
timestamp = {Tue, 07 Dec 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/toc/ODonnellS21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/OliveiraPS21,
author = {Igor C. Oliveira and
J{\'{a}}n Pich and
Rahul Santhanam},
title = {Hardness Magnification Near State-of-the-Art Lower Bounds},
journal = {Theory Comput.},
volume = {17},
pages = {1--38},
year = {2021},
url = {https://theoryofcomputing.org/articles/v017a011/},
timestamp = {Tue, 30 May 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/OliveiraPS21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/Ron-ZewiBV21,
author = {Noga Ron{-}Zewi and
Ivona Bez{\'{a}}kov{\'{a}} and
L{\'{a}}szl{\'{o}} A. V{\'{e}}gh},
title = {Special Issue: {APPROX-RANDOM} 2019: Guest Editors' Foreword},
journal = {Theory Comput.},
volume = {17},
pages = {1--4},
year = {2021},
url = {https://theoryofcomputing.org/articles/v017a003/},
timestamp = {Tue, 07 Dec 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/toc/Ron-ZewiBV21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/AaronsonG20,
author = {Scott Aaronson and
Sam Gunn},
title = {On the Classical Hardness of Spoofing Linear Cross-Entropy Benchmarking},
journal = {Theory Comput.},
volume = {16},
pages = {1--8},
year = {2020},
url = {https://doi.org/10.4086/toc.2020.v016a011},
doi = {10.4086/TOC.2020.V016A011},
timestamp = {Wed, 10 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/toc/AaronsonG20.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/AlonMP20,
author = {Noga Alon and
Elchanan Mossel and
Robin Pemantle},
title = {Distributed Corruption Detection in Networks},
journal = {Theory Comput.},
volume = {16},
pages = {1--23},
year = {2020},
url = {https://doi.org/10.4086/toc.2020.v016a001},
doi = {10.4086/TOC.2020.V016A001},
timestamp = {Wed, 10 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/toc/AlonMP20.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/BaleshzarCPRS20,
author = {Roksana Baleshzar and
Deeparnab Chakrabarty and
Ramesh Krishnan S. Pallavoor and
Sofya Raskhodnikova and
C. Seshadhri},
title = {Optimal Unateness Testers for Real-Valued Functions: Adaptivity Helps},
journal = {Theory Comput.},
volume = {16},
pages = {1--36},
year = {2020},
url = {https://doi.org/10.4086/toc.2020.v016a003},
doi = {10.4086/TOC.2020.V016A003},
timestamp = {Thu, 07 Jul 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/BaleshzarCPRS20.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/BavarianGHKRS20,
author = {Mohammad Bavarian and
Badih Ghazi and
Elad Haramaty and
Pritish Kamath and
Ronald L. Rivest and
Madhu Sudan},
title = {Optimality of Correlated Sampling Strategies},
journal = {Theory Comput.},
volume = {16},
pages = {1--18},
year = {2020},
url = {https://doi.org/10.4086/toc.2020.v016a012},
doi = {10.4086/TOC.2020.V016A012},
timestamp = {Tue, 14 Jun 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/BavarianGHKRS20.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/BhangaleHV20,
author = {Amey Bhangale and
Prahladh Harsha and
Girish Varma},
title = {A Characterization of Hard-to-Cover CSPs},
journal = {Theory Comput.},
volume = {16},
pages = {1--30},
year = {2020},
url = {https://doi.org/10.4086/toc.2020.v016a016},
doi = {10.4086/TOC.2020.V016A016},
timestamp = {Wed, 10 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/toc/BhangaleHV20.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/BogdanovGK20,
author = {Andrej Bogdanov and
Siyao Guo and
Ilan Komargodski},
title = {Threshold Secret Sharing Requires a Linear-Size Alphabet},
journal = {Theory Comput.},
volume = {16},
pages = {1--18},
year = {2020},
url = {https://doi.org/10.4086/toc.2020.v016a002},
doi = {10.4086/TOC.2020.V016A002},
timestamp = {Wed, 10 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/toc/BogdanovGK20.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/BunKT20,
author = {Mark Bun and
Robin Kothari and
Justin Thaler},
title = {The Polynomial Method Strikes Back: Tight Quantum Query Bounds via
Dual Polynomials},
journal = {Theory Comput.},
volume = {16},
pages = {1--71},
year = {2020},
url = {https://doi.org/10.4086/toc.2020.v016a010},
doi = {10.4086/TOC.2020.V016A010},
timestamp = {Mon, 26 Jun 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/BunKT20.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/ChekuriL20,
author = {Chandra Chekuri and
Shi Li},
title = {On the Hardness of Approximating the k-Way Hypergraph Cut problem},
journal = {Theory Comput.},
volume = {16},
pages = {1--8},
year = {2020},
url = {https://doi.org/10.4086/toc.2020.v016a014},
doi = {10.4086/TOC.2020.V016A014},
timestamp = {Thu, 29 Apr 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/ChekuriL20.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/Chen20,
author = {Lijie Chen},
title = {On The Hardness of Approximate and Exact (Bichromatic) Maximum Inner
Product},
journal = {Theory Comput.},
volume = {16},
pages = {1--50},
year = {2020},
url = {https://doi.org/10.4086/toc.2020.v016a004},
doi = {10.4086/TOC.2020.V016A004},
timestamp = {Tue, 16 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/toc/Chen20.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/ChiesaMS20,
author = {Alessandro Chiesa and
Peter Manohar and
Igor Shinkar},
title = {On Axis-Parallel Tests for Tensor Product Codes},
journal = {Theory Comput.},
volume = {16},
pages = {1--34},
year = {2020},
url = {https://doi.org/10.4086/toc.2020.v016a005},
doi = {10.4086/TOC.2020.V016A005},
timestamp = {Wed, 10 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/toc/ChiesaMS20.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/CohenMP20,
author = {Michael B. Cohen and
Cameron Musco and
Jakub Pachocki},
title = {Online Row Sampling},
journal = {Theory Comput.},
volume = {16},
pages = {1--25},
year = {2020},
url = {https://doi.org/10.4086/toc.2020.v016a015},
doi = {10.4086/TOC.2020.V016A015},
timestamp = {Wed, 10 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/toc/CohenMP20.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/DeOS20,
author = {Anindya De and
Ryan O'Donnell and
Rocco A. Servedio},
title = {Sharp Bounds for Population Recovery},
journal = {Theory Comput.},
volume = {16},
pages = {1--20},
year = {2020},
url = {https://doi.org/10.4086/toc.2020.v016a006},
doi = {10.4086/TOC.2020.V016A006},
timestamp = {Wed, 10 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/toc/DeOS20.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/DvirL20,
author = {Zeev Dvir and
Allen Liu},
title = {Fourier and Circulant Matrices are Not Rigid},
journal = {Theory Comput.},
volume = {16},
pages = {1--48},
year = {2020},
url = {https://doi.org/10.4086/toc.2020.v016a020},
doi = {10.4086/TOC.2020.V016A020},
timestamp = {Wed, 10 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/toc/DvirL20.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/Filmus20,
author = {Yuval Filmus},
title = {Special Issue: {CCC} 2019: Guest Editor's Foreword},
journal = {Theory Comput.},
volume = {16},
pages = {1--5},
year = {2020},
url = {https://doi.org/10.4086/toc.2020.v016a019},
doi = {10.4086/TOC.2020.V016A019},
timestamp = {Wed, 10 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/toc/Filmus20.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/GargGK020,
author = {Ankit Garg and
Mika G{\"{o}}{\"{o}}s and
Pritish Kamath and
Dmitry Sokolov},
title = {Monotone Circuit Lower Bounds from Resolution},
journal = {Theory Comput.},
volume = {16},
pages = {1--30},
year = {2020},
url = {https://doi.org/10.4086/toc.2020.v016a013},
doi = {10.4086/TOC.2020.V016A013},
timestamp = {Mon, 05 Feb 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/toc/GargGK020.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/GopalanY20,
author = {Parikshit Gopalan and
Amir Yehudayoff},
title = {Concentration for Limited Independence via Inequalities for the Elementary
Symmetric Polynomials},
journal = {Theory Comput.},
volume = {16},
pages = {1--29},
year = {2020},
url = {https://doi.org/10.4086/toc.2020.v016a017},
doi = {10.4086/TOC.2020.V016A017},
timestamp = {Wed, 10 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/toc/GopalanY20.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/GurRR20,
author = {Tom Gur and
Govind Ramnarayan and
Ron Rothblum},
title = {Relaxed Locally Correctable Codes},
journal = {Theory Comput.},
volume = {16},
pages = {1--68},
year = {2020},
url = {https://doi.org/10.4086/toc.2020.v016a018},
doi = {10.4086/TOC.2020.V016A018},
timestamp = {Wed, 10 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/toc/GurRR20.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/HaitnerHRVW20,
author = {Iftach Haitner and
Thomas Holenstein and
Omer Reingold and
Salil P. Vadhan and
Hoeteck Wee},
title = {Inaccessible Entropy {II:} {IE} Functions and Universal One-Way Hashing},
journal = {Theory Comput.},
volume = {16},
pages = {1--55},
year = {2020},
url = {https://doi.org/10.4086/toc.2020.v016a008},
doi = {10.4086/TOC.2020.V016A008},
timestamp = {Wed, 10 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/toc/HaitnerHRVW20.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/Hrubes20,
author = {Pavel Hrubes},
title = {On the Complexity of Computing a Random Boolean Function Over the
Reals},
journal = {Theory Comput.},
volume = {16},
pages = {1--12},
year = {2020},
url = {https://doi.org/10.4086/toc.2020.v016a009},
doi = {10.4086/TOC.2020.V016A009},
timestamp = {Wed, 10 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/toc/Hrubes20.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/LeeV20,
author = {Chin Ho Lee and
Emanuele Viola},
title = {More on Bounded Independence Plus Noise: Pseudorandom Generators for
Read-Once Polynomials},
journal = {Theory Comput.},
volume = {16},
pages = {1--50},
year = {2020},
url = {https://doi.org/10.4086/toc.2020.v016a007},
doi = {10.4086/TOC.2020.V016A007},
timestamp = {Wed, 10 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/toc/LeeV20.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/000119,
author = {Srikanth Srinivasan},
title = {Special Issue: {CCC} 2018: Guest Editor's Foreword},
journal = {Theory Comput.},
volume = {15},
pages = {1--3},
year = {2019},
url = {https://doi.org/10.4086/toc.2019.v015a009},
doi = {10.4086/TOC.2019.V015A009},
timestamp = {Thu, 14 Oct 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/000119.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/ArvindJM019,
author = {Vikraman Arvind and
Pushkar S. Joglekar and
Partha Mukhopadhyay and
S. Raja},
title = {Randomized Polynomial-Time Identity Testing for Noncommutative Circuits},
journal = {Theory Comput.},
volume = {15},
pages = {1--36},
year = {2019},
url = {https://doi.org/10.4086/toc.2019.v015a007},
doi = {10.4086/TOC.2019.V015A007},
timestamp = {Tue, 09 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/toc/ArvindJM019.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/BansalDGL19,
author = {Nikhil Bansal and
Daniel Dadush and
Shashwat Garg and
Shachar Lovett},
title = {The Gram-Schmidt Walk: {A} Cure for the Banaszczyk Blues},
journal = {Theory Comput.},
volume = {15},
pages = {1--27},
year = {2019},
url = {https://doi.org/10.4086/toc.2019.v015a021},
doi = {10.4086/TOC.2019.V015A021},
timestamp = {Tue, 15 Feb 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/toc/BansalDGL19.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/BansalG19,
author = {Nikhil Bansal and
Anupam Gupta},
title = {Potential-Function Proofs for Gradient Methods},
journal = {Theory Comput.},
volume = {15},
pages = {1--32},
year = {2019},
url = {https://doi.org/10.4086/toc.2019.v015a004},
doi = {10.4086/TOC.2019.V015A004},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/BansalG19.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/BrietDG19,
author = {Jop Bri{\"{e}}t and
Zeev Dvir and
Sivakanth Gopi},
title = {Outlaw Distributions and Locally Decodable Codes},
journal = {Theory Comput.},
volume = {15},
pages = {1--24},
year = {2019},
url = {https://doi.org/10.4086/toc.2019.v015a012},
doi = {10.4086/TOC.2019.V015A012},
timestamp = {Tue, 09 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/toc/BrietDG19.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/CanonneGG0W19,
author = {Cl{\'{e}}ment L. Canonne and
Elena Grigorescu and
Siyao Guo and
Akash Kumar and
Karl Wimmer},
title = {Testing k-Monotonicity: The Rise and Fall of Boolean Functions},
journal = {Theory Comput.},
volume = {15},
pages = {1--55},
year = {2019},
url = {https://doi.org/10.4086/toc.2019.v015a001},
doi = {10.4086/TOC.2019.V015A001},
timestamp = {Mon, 26 Jun 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/CanonneGG0W19.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/ChattopadhyayHH19,
author = {Eshan Chattopadhyay and
Pooya Hatami and
Kaave Hosseini and
Shachar Lovett},
title = {Pseudorandom Generators from Polarizing Random Walks},
journal = {Theory Comput.},
volume = {15},
pages = {1--26},
year = {2019},
url = {https://doi.org/10.4086/toc.2019.v015a010},
doi = {10.4086/TOC.2019.V015A010},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/ChattopadhyayHH19.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/ChechikS19,
author = {Shiri Chechik and
Ronen Shaltiel},
title = {Special Issue: {APPROX-RANDOM} 2016: Guest Editors' Foreword},
journal = {Theory Comput.},
volume = {15},
pages = {1--3},
year = {2019},
url = {https://doi.org/10.4086/toc.2019.v015a014},
doi = {10.4086/TOC.2019.V015A014},
timestamp = {Tue, 09 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/toc/ChechikS19.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/Chou0S19,
author = {Chi{-}Ning Chou and
Mrinal Kumar and
Noam Solomon},
title = {Closure Results for Polynomial Factorization},
journal = {Theory Comput.},
volume = {15},
pages = {1--34},
year = {2019},
url = {https://doi.org/10.4086/toc.2019.v015a013},
doi = {10.4086/TOC.2019.V015A013},
timestamp = {Tue, 09 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/toc/Chou0S19.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/CliffordJS19,
author = {Rapha{\"{e}}l Clifford and
Markus Jalsenius and
Benjamin Sach},
title = {Time Bounds for Streaming Problems},
journal = {Theory Comput.},
volume = {15},
pages = {1--31},
year = {2019},
url = {https://doi.org/10.4086/toc.2019.v015a002},
doi = {10.4086/TOC.2019.V015A002},
timestamp = {Tue, 09 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/toc/CliffordJS19.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/DadushGLN19,
author = {Daniel Dadush and
Shashwat Garg and
Shachar Lovett and
Aleksandar Nikolov},
title = {Towards a Constructive Version of Banaszczyk's Vector Balancing Theorem},
journal = {Theory Comput.},
volume = {15},
pages = {1--58},
year = {2019},
url = {https://doi.org/10.4086/toc.2019.v015a015},
doi = {10.4086/TOC.2019.V015A015},
timestamp = {Tue, 09 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/toc/DadushGLN19.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/DeMN19,
author = {Anindya De and
Elchanan Mossel and
Joe Neeman},
title = {Noise Stability is Computable and Approximately Low-Dimensional},
journal = {Theory Comput.},
volume = {15},
pages = {1--47},
year = {2019},
url = {https://doi.org/10.4086/toc.2019.v015a006},
doi = {10.4086/TOC.2019.V015A006},
timestamp = {Tue, 09 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/toc/DeMN19.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/DvirE19,
author = {Zeev Dvir and
Benjamin L. Edelman},
title = {Matrix Rigidity and the Croot-Lev-Pach Lemma},
journal = {Theory Comput.},
volume = {15},
pages = {1--7},
year = {2019},
url = {https://doi.org/10.4086/toc.2019.v015a008},
doi = {10.4086/TOC.2019.V015A008},
timestamp = {Tue, 09 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/toc/DvirE19.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/GesmundoL19,
author = {Fulvio Gesmundo and
Joseph M. Landsberg},
title = {Explicit Polynomial Sequences with Maximal Spaces of Partial Derivatives
and a Question of K. Mulmuley},
journal = {Theory Comput.},
volume = {15},
pages = {1--24},
year = {2019},
url = {https://doi.org/10.4086/toc.2019.v015a003},
doi = {10.4086/TOC.2019.V015A003},
timestamp = {Fri, 19 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/toc/GesmundoL19.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/GowersJ19,
author = {Timothy Gowers and
Oliver Janzer},
title = {Subsets of Cayley Graphs that Induce Many Edges},
journal = {Theory Comput.},
volume = {15},
pages = {1--29},
year = {2019},
url = {https://doi.org/10.4086/toc.2019.v015a020},
doi = {10.4086/TOC.2019.V015A020},
timestamp = {Tue, 09 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/toc/GowersJ19.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/Guo0S19,
author = {Zeyu Guo and
Nitin Saxena and
Amit Sinhababu},
title = {Algebraic Dependencies and {PSPACE} Algorithms in Approximative Complexity
over Any Field},
journal = {Theory Comput.},
volume = {15},
pages = {1--30},
year = {2019},
url = {https://doi.org/10.4086/toc.2019.v015a016},
doi = {10.4086/TOC.2019.V015A016},
timestamp = {Tue, 07 May 2024 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/Guo0S19.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/Ji19,
author = {Zhengfeng Ji},
title = {Classical Verification of Quantum Proofs},
journal = {Theory Comput.},
volume = {15},
pages = {1--42},
year = {2019},
url = {https://doi.org/10.4086/toc.2019.v015a005},
doi = {10.4086/TOC.2019.V015A005},
timestamp = {Tue, 09 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/toc/Ji19.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/Rossman019,
author = {Benjamin Rossman and
Srikanth Srinivasan},
title = {Separation of AC\({}^{\mbox{0}}\)[{\(\oplus\)}] Formulas and Circuits},
journal = {Theory Comput.},
volume = {15},
pages = {1--20},
year = {2019},
url = {https://doi.org/10.4086/toc.2019.v015a017},
doi = {10.4086/TOC.2019.V015A017},
timestamp = {Thu, 14 Oct 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/Rossman019.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/Sanyal19,
author = {Swagato Sanyal},
title = {Fourier Sparsity and Dimension},
journal = {Theory Comput.},
volume = {15},
pages = {1--13},
year = {2019},
url = {https://doi.org/10.4086/toc.2019.v015a011},
doi = {10.4086/TOC.2019.V015A011},
timestamp = {Tue, 09 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/toc/Sanyal19.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/Viola19,
author = {Emanuele Viola},
title = {Lower Bounds for Data Structures with Space Close to Maximum Imply
Circuit Lower Bounds},
journal = {Theory Comput.},
volume = {15},
pages = {1--9},
year = {2019},
url = {https://doi.org/10.4086/toc.2019.v015a018},
doi = {10.4086/TOC.2019.V015A018},
timestamp = {Tue, 09 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/toc/Viola19.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/Wilson19,
author = {James B. Wilson},
title = {The Threshold for Subgroup Profiles to Agree is Logarithmic},
journal = {Theory Comput.},
volume = {15},
pages = {1--25},
year = {2019},
url = {https://doi.org/10.4086/toc.2019.v015a019},
doi = {10.4086/TOC.2019.V015A019},
timestamp = {Thu, 14 Oct 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/Wilson19.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/AcharyaCK18,
author = {Jayadev Acharya and
Cl{\'{e}}ment L. Canonne and
Gautam Kamath},
title = {A Chasm Between Identity and Equivalence Testing with Conditional
Queries},
journal = {Theory Comput.},
volume = {14},
number = {1},
pages = {1--46},
year = {2018},
url = {https://doi.org/10.4086/toc.2018.v014a019},
doi = {10.4086/TOC.2018.V014A019},
timestamp = {Mon, 26 Jun 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/AcharyaCK18.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/ApplebaumDE18,
author = {Benny Applebaum and
Liron David and
Guy Even},
title = {Explicit Rateless Codes for Memoryless Binary-Input Output-Symmetric
Channels},
journal = {Theory Comput.},
volume = {14},
number = {1},
pages = {1--29},
year = {2018},
url = {https://doi.org/10.4086/toc.2018.v014a004},
doi = {10.4086/TOC.2018.V014A004},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/ApplebaumDE18.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/AradSSZ18,
author = {Itai Arad and
Miklos Santha and
Aarthi Sundaram and
Shengyu Zhang},
title = {Linear-Time Algorithm for Quantum 2SAT},
journal = {Theory Comput.},
volume = {14},
number = {1},
pages = {1--27},
year = {2018},
url = {https://doi.org/10.4086/toc.2018.v014a001},
doi = {10.4086/TOC.2018.V014A001},
timestamp = {Thu, 01 Dec 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/toc/AradSSZ18.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/BazziFHS18,
author = {Abbas Bazzi and
Samuel Fiorini and
Sangxia Huang and
Ola Svensson},
title = {Small Extended Formulation for Knapsack Cover Inequalities from Monotone
Circuits},
journal = {Theory Comput.},
volume = {14},
number = {1},
pages = {1--29},
year = {2018},
url = {https://doi.org/10.4086/toc.2018.v014a014},
doi = {10.4086/TOC.2018.V014A014},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/BazziFHS18.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/Ben-DavidK18,
author = {Shalev Ben{-}David and
Robin Kothari},
title = {Randomized Query Complexity of Sabotaged and Composed Functions},
journal = {Theory Comput.},
volume = {14},
number = {1},
pages = {1--27},
year = {2018},
url = {https://doi.org/10.4086/toc.2018.v014a005},
doi = {10.4086/TOC.2018.V014A005},
timestamp = {Mon, 26 Oct 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/toc/Ben-DavidK18.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/BlaserJP18,
author = {Markus Bl{\"{a}}ser and
Gorav Jindal and
Anurag Pandey},
title = {A Deterministic {PTAS} for the Commutative Rank of Matrix Spaces},
journal = {Theory Comput.},
volume = {14},
number = {1},
pages = {1--21},
year = {2018},
url = {https://doi.org/10.4086/toc.2018.v014a003},
doi = {10.4086/TOC.2018.V014A003},
timestamp = {Sun, 06 Aug 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/BlaserJP18.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/Broadbent18,
author = {Anne Broadbent},
title = {How to Verify a Quantum Computation},
journal = {Theory Comput.},
volume = {14},
number = {1},
pages = {1--37},
year = {2018},
url = {https://doi.org/10.4086/toc.2018.v014a011},
doi = {10.4086/TOC.2018.V014A011},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/Broadbent18.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/ChattopadhyayM18,
author = {Arkadev Chattopadhyay and
Nikhil S. Mande},
title = {Separation of Unbounded-Error Models in Multi-Party Communication
Complexity},
journal = {Theory Comput.},
volume = {14},
number = {1},
pages = {1--23},
year = {2018},
url = {https://doi.org/10.4086/toc.2018.v014a021},
doi = {10.4086/TOC.2018.V014A021},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/ChattopadhyayM18.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/ChenS018,
author = {Ruiwen Chen and
Rahul Santhanam and
Srikanth Srinivasan},
title = {Average-Case Lower Bounds and Satisfiability Algorithms for Small
Threshold Circuits},
journal = {Theory Comput.},
volume = {14},
number = {1},
pages = {1--55},
year = {2018},
url = {https://doi.org/10.4086/toc.2018.v014a009},
doi = {10.4086/TOC.2018.V014A009},
timestamp = {Thu, 14 Oct 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/ChenS018.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/DaganFHL18,
author = {Yuval Dagan and
Yuval Filmus and
Hamed Hatami and
Yaqiao Li},
title = {Trading Information Complexity for Error},
journal = {Theory Comput.},
volume = {14},
number = {1},
pages = {1--73},
year = {2018},
url = {https://doi.org/10.4086/toc.2018.v014a006},
doi = {10.4086/TOC.2018.V014A006},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/DaganFHL18.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/DulekSS18,
author = {Yfke Dulek and
Christian Schaffner and
Florian Speelman},
title = {Quantum Homomorphic Encryption for Polynomial-Size Circuits},
journal = {Theory Comput.},
volume = {14},
number = {1},
pages = {1--45},
year = {2018},
url = {https://doi.org/10.4086/toc.2018.v014a007},
doi = {10.4086/TOC.2018.V014A007},
timestamp = {Thu, 14 Oct 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/DulekSS18.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/ForbesSV18,
author = {Michael A. Forbes and
Amir Shpilka and
Ben Lee Volk},
title = {Succinct Hitting Sets and Barriers to Proving Lower Bounds for Algebraic
Circuits},
journal = {Theory Comput.},
volume = {14},
number = {1},
pages = {1--45},
year = {2018},
url = {https://doi.org/10.4086/toc.2018.v014a018},
doi = {10.4086/TOC.2018.V014A018},
timestamp = {Mon, 26 Jun 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/ForbesSV18.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/GhoshT18,
author = {Mrinalkanti Ghosh and
Madhur Tulsiani},
title = {From Weak to Strong Linear Programming Gaps for All Constraint Satisfaction
Problems},
journal = {Theory Comput.},
volume = {14},
number = {1},
pages = {1--33},
year = {2018},
url = {https://doi.org/10.4086/toc.2018.v014a010},
doi = {10.4086/TOC.2018.V014A010},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/GhoshT18.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/Kayal0T18,
author = {Neeraj Kayal and
Chandan Saha and
S{\'{e}}bastien Tavenas},
title = {On the Size of Homogeneous and of Depth-Four Formulas with Low Individual
Degree},
journal = {Theory Comput.},
volume = {14},
number = {1},
pages = {1--46},
year = {2018},
url = {https://doi.org/10.4086/toc.2018.v014a016},
doi = {10.4086/TOC.2018.V014A016},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/Kayal0T18.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/Kopparty018,
author = {Swastik Kopparty and
Srikanth Srinivasan},
title = {Certifying Polynomials for {\textdollar}{\textbackslash}mathrm\{AC\}0[{\textbackslash}oplus]{\textdollar}
Circuits, with Applications to Lower Bounds and Circuit Compression},
journal = {Theory Comput.},
volume = {14},
number = {1},
pages = {1--24},
year = {2018},
url = {https://doi.org/10.4086/toc.2018.v014a012},
doi = {10.4086/TOC.2018.V014A012},
timestamp = {Thu, 14 Oct 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/Kopparty018.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/LovettO18,
author = {Shachar Lovett and
Ryan O'Donnell},
title = {Special Issue: {CCC} 2017: Guest Editor's Foreword},
journal = {Theory Comput.},
volume = {14},
number = {1},
pages = {1--2},
year = {2018},
url = {https://doi.org/10.4086/toc.2018.v014a002},
doi = {10.4086/TOC.2018.V014A002},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/LovettO18.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/Micciancio18,
author = {Daniele Micciancio},
title = {On the Hardness of Learning With Errors with Binary Secrets},
journal = {Theory Comput.},
volume = {14},
number = {1},
pages = {1--17},
year = {2018},
url = {https://doi.org/10.4086/toc.2018.v014a013},
doi = {10.4086/TOC.2018.V014A013},
timestamp = {Mon, 05 Feb 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/toc/Micciancio18.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/Montanaro18,
author = {Ashley Montanaro},
title = {Quantum-Walk Speedup of Backtracking Algorithms},
journal = {Theory Comput.},
volume = {14},
number = {1},
pages = {1--24},
year = {2018},
url = {https://doi.org/10.4086/toc.2018.v014a015},
doi = {10.4086/TOC.2018.V014A015},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/Montanaro18.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/MurtaghV18,
author = {Jack Murtagh and
Salil P. Vadhan},
title = {The Complexity of Computing the Optimal Composition of Differential
Privacy},
journal = {Theory Comput.},
volume = {14},
number = {1},
pages = {1--35},
year = {2018},
url = {https://doi.org/10.4086/toc.2018.v014a008},
doi = {10.4086/TOC.2018.V014A008},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/MurtaghV18.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/RaoS18,
author = {Anup Rao and
Makrand Sinha},
title = {Simplified Separation of Information and Communication},
journal = {Theory Comput.},
volume = {14},
number = {1},
pages = {1--29},
year = {2018},
url = {https://doi.org/10.4086/toc.2018.v014a020},
doi = {10.4086/TOC.2018.V014A020},
timestamp = {Sat, 05 Sep 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/RaoS18.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/Sherstov18,
author = {Alexander A. Sherstov},
title = {On Multiparty Communication with Large versus Unbounded Error},
journal = {Theory Comput.},
volume = {14},
number = {1},
pages = {1--17},
year = {2018},
url = {https://doi.org/10.4086/toc.2018.v014a022},
doi = {10.4086/TOC.2018.V014A022},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/Sherstov18.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/Williams18,
author = {R. Ryan Williams},
title = {New Algorithms and Lower Bounds for Circuits With Linear Threshold
Gates},
journal = {Theory Comput.},
volume = {14},
number = {1},
pages = {1--25},
year = {2018},
url = {https://doi.org/10.4086/toc.2018.v014a017},
doi = {10.4086/TOC.2018.V014A017},
timestamp = {Tue, 07 May 2024 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/Williams18.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/0001S17,
author = {Mrinal Kumar and
Shubhangi Saraf},
title = {Arithmetic Circuits with Locally Low Algebraic Rank},
journal = {Theory Comput.},
volume = {13},
number = {1},
pages = {1--33},
year = {2017},
url = {https://doi.org/10.4086/toc.2017.v013a006},
doi = {10.4086/TOC.2017.V013A006},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/0001S17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/BalcanB17,
author = {Maria{-}Florina Balcan and
Mark Braverman},
title = {Nash Equilibria in Perturbation-Stable Games},
journal = {Theory Comput.},
volume = {13},
number = {1},
pages = {1--31},
year = {2017},
url = {https://doi.org/10.4086/toc.2017.v013a013},
doi = {10.4086/TOC.2017.V013A013},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/BalcanB17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/Briet0S17,
author = {Jop Bri{\"{e}}t and
Oded Regev and
Rishi Saket},
title = {Tight Hardness of the Non-Commutative Grothendieck Problem},
journal = {Theory Comput.},
volume = {13},
number = {1},
pages = {1--24},
year = {2017},
url = {https://doi.org/10.4086/toc.2017.v013a015},
doi = {10.4086/TOC.2017.V013A015},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/Briet0S17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/Coja-OghlanCKS17,
author = {Amin Coja{-}Oghlan and
Oliver Cooley and
Mihyun Kang and
Kathrin Skubch},
title = {The Minimum Bisection in the Planted Bisection Model},
journal = {Theory Comput.},
volume = {13},
number = {1},
pages = {1--22},
year = {2017},
url = {https://doi.org/10.4086/toc.2017.v013a008},
doi = {10.4086/TOC.2017.V013A008},
timestamp = {Mon, 26 Oct 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/toc/Coja-OghlanCKS17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/DvirSW17,
author = {Zeev Dvir and
Shubhangi Saraf and
Avi Wigderson},
title = {Superquadratic Lower Bound for 3-Query Locally Correctable Codes over
the Reals},
journal = {Theory Comput.},
volume = {13},
number = {1},
pages = {1--36},
year = {2017},
url = {https://doi.org/10.4086/toc.2017.v013a011},
doi = {10.4086/TOC.2017.V013A011},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/DvirSW17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/FelberO17,
author = {David Felber and
Rafail Ostrovsky},
title = {A Randomized Online Quantile Summary in O((1/{\(\epsilon\)}) log(1/{\(\epsilon\)}))
Words},
journal = {Theory Comput.},
volume = {13},
number = {1},
pages = {1--17},
year = {2017},
url = {https://doi.org/10.4086/toc.2017.v013a014},
doi = {10.4086/TOC.2017.V013A014},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/FelberO17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/FournierLM017,
author = {Herv{\'{e}} Fournier and
Nutan Limaye and
Meena Mahajan and
Srikanth Srinivasan},
title = {The Shifted Partial Derivative Complexity of Elementary Symmetric
Polynomials},
journal = {Theory Comput.},
volume = {13},
number = {1},
pages = {1--34},
year = {2017},
url = {https://doi.org/10.4086/toc.2017.v013a009},
doi = {10.4086/TOC.2017.V013A009},
timestamp = {Thu, 14 Oct 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/FournierLM017.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/GilmerKS17,
author = {Justin Gilmer and
Michal Kouck{\'{y}} and
Michael E. Saks},
title = {A Communication Game Related to the Sensitivity Conjecture},
journal = {Theory Comput.},
volume = {13},
number = {1},
pages = {1--18},
year = {2017},
url = {https://doi.org/10.4086/toc.2017.v013a007},
doi = {10.4086/TOC.2017.V013A007},
timestamp = {Wed, 07 Dec 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/toc/GilmerKS17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/Grochow17,
author = {Joshua A. Grochow},
title = {Monotone Projection Lower Bounds from Extended Formulation Lower Bounds},
journal = {Theory Comput.},
volume = {13},
number = {1},
pages = {1--15},
year = {2017},
url = {https://doi.org/10.4086/toc.2017.v013a018},
doi = {10.4086/TOC.2017.V013A018},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/Grochow17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/GurjarKS17,
author = {Rohit Gurjar and
Arpita Korwar and
Nitin Saxena},
title = {Identity Testing for Constant-Width, and Any-Order, Read-Once Oblivious
Arithmetic Branching Programs},
journal = {Theory Comput.},
volume = {13},
number = {1},
pages = {1--21},
year = {2017},
url = {https://doi.org/10.4086/toc.2017.v013a002},
doi = {10.4086/TOC.2017.V013A002},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/GurjarKS17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/GuruswamiL17,
author = {Venkatesan Guruswami and
Euiwoong Lee},
title = {Towards a Characterization of Approximation Resistance for Symmetric
CSPs},
journal = {Theory Comput.},
volume = {13},
number = {1},
pages = {1--24},
year = {2017},
url = {https://doi.org/10.4086/toc.2017.v013a003},
doi = {10.4086/TOC.2017.V013A003},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/GuruswamiL17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/HarrisS17,
author = {David G. Harris and
Aravind Srinivasan},
title = {A Constructive Lov{\'{a}}sz Local Lemma for Permutations},
journal = {Theory Comput.},
volume = {13},
number = {1},
pages = {1--41},
year = {2017},
url = {https://doi.org/10.4086/toc.2017.v013a017},
doi = {10.4086/TOC.2017.V013A017},
timestamp = {Thu, 24 Feb 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/toc/HarrisS17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/Harsha17,
author = {Prahladh Harsha},
title = {Special Issue: {CCC} 2016: Guest Editor's Foreword},
journal = {Theory Comput.},
volume = {13},
number = {1},
pages = {1--3},
year = {2017},
url = {https://doi.org/10.4086/toc.2017.v013a001},
doi = {10.4086/TOC.2017.V013A001},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/Harsha17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/HastadHMOW17,
author = {Johan H{\aa}stad and
Sangxia Huang and
Rajsekar Manokaran and
Ryan O'Donnell and
John Wright},
title = {Improved NP-Inapproximability for 2-Variable Linear Equations},
journal = {Theory Comput.},
volume = {13},
number = {1},
pages = {1--51},
year = {2017},
url = {https://doi.org/10.4086/toc.2017.v013a019},
doi = {10.4086/TOC.2017.V013A019},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/HastadHMOW17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/HastadM17,
author = {Johan H{\aa}stad and
Rajsekar Manokaran},
title = {On the Hardness of Approximating Balanced Homogenous 3-Lin},
journal = {Theory Comput.},
volume = {13},
number = {1},
pages = {1--19},
year = {2017},
url = {https://doi.org/10.4086/toc.2017.v013a010},
doi = {10.4086/TOC.2017.V013A010},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/HastadM17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/KimK17,
author = {John Y. Kim and
Swastik Kopparty},
title = {Decoding Reed-Muller Codes over Product Sets},
journal = {Theory Comput.},
volume = {13},
number = {1},
pages = {1--38},
year = {2017},
url = {https://doi.org/10.4086/toc.2017.v013a021},
doi = {10.4086/TOC.2017.V013A021},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/KimK17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/LeeV17,
author = {Chin Ho Lee and
Emanuele Viola},
title = {Some Limitations of the Sum of Small-Bias Distributions},
journal = {Theory Comput.},
volume = {13},
number = {1},
pages = {1--23},
year = {2017},
url = {https://doi.org/10.4086/toc.2017.v013a016},
doi = {10.4086/TOC.2017.V013A016},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/LeeV17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/Lovett17,
author = {Shachar Lovett},
title = {Additive Combinatorics and its Applications in Theoretical Computer
Science},
journal = {Theory Comput.},
volume = {8},
pages = {1--55},
year = {2017},
url = {https://doi.org/10.4086/toc.gs.2017.008},
doi = {10.4086/TOC.GS.2017.008},
timestamp = {Wed, 22 Jul 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/Lovett17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/MakarychevNS17,
author = {Yury Makarychev and
Amir Nayyeri and
Anastasios Sidiropoulos},
title = {A Pseudo-Approximation for the Genus of Hamiltonian Graphs},
journal = {Theory Comput.},
volume = {13},
number = {1},
pages = {1--47},
year = {2017},
url = {https://doi.org/10.4086/toc.2017.v013a005},
doi = {10.4086/TOC.2017.V013A005},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/MakarychevNS17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/MurrayW17,
author = {Cody D. Murray and
R. Ryan Williams},
title = {On the (Non) NP-Hardness of Computing Circuit Complexity},
journal = {Theory Comput.},
volume = {13},
number = {1},
pages = {1--22},
year = {2017},
url = {https://doi.org/10.4086/toc.2017.v013a004},
doi = {10.4086/TOC.2017.V013A004},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/MurrayW17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/ShepherdV17,
author = {F. Bruce Shepherd and
Adrian R. Vetta},
title = {The Inapproximability of Maximum Single-Sink Unsplittable, Priority
and Confluent Flow Problems},
journal = {Theory Comput.},
volume = {13},
number = {1},
pages = {1--25},
year = {2017},
url = {https://doi.org/10.4086/toc.2017.v013a020},
doi = {10.4086/TOC.2017.V013A020},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/ShepherdV17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/SteinkeVW17,
author = {Thomas Steinke and
Salil P. Vadhan and
Andrew Wan},
title = {Pseudorandomness and Fourier-Growth Bounds for Width-3 Branching Programs},
journal = {Theory Comput.},
volume = {13},
number = {1},
pages = {1--50},
year = {2017},
url = {https://doi.org/10.4086/toc.2017.v013a012},
doi = {10.4086/TOC.2017.V013A012},
timestamp = {Sun, 14 Mar 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/toc/SteinkeVW17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/BansalC16,
author = {Nikhil Bansal and
Bouke Cloostermans},
title = {Minimizing Maximum Flow-Time on Related Machines},
journal = {Theory Comput.},
volume = {12},
number = {1},
pages = {1--14},
year = {2016},
url = {https://doi.org/10.4086/toc.2016.v012a014},
doi = {10.4086/TOC.2016.V012A014},
timestamp = {Tue, 15 Feb 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/toc/BansalC16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/BeimelNS16,
author = {Amos Beimel and
Kobbi Nissim and
Uri Stemmer},
title = {Private Learning and Sanitization: Pure vs. Approximate Differential
Privacy},
journal = {Theory Comput.},
volume = {12},
number = {1},
pages = {1--61},
year = {2016},
url = {https://doi.org/10.4086/toc.2016.v012a001},
doi = {10.4086/TOC.2016.V012A001},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/BeimelNS16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/BunT16,
author = {Mark Bun and
Justin Thaler},
title = {Dual Polynomials for Collision and Element Distinctness},
journal = {Theory Comput.},
volume = {12},
number = {1},
pages = {1--34},
year = {2016},
url = {https://doi.org/10.4086/toc.2016.v012a016},
doi = {10.4086/TOC.2016.V012A016},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/BunT16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/ChakrabartiC016,
author = {Amit Chakrabarti and
Graham Cormode and
Andrew McGregor},
title = {Robust Lower Bounds for Communication and Stream Computation},
journal = {Theory Comput.},
volume = {12},
number = {1},
pages = {1--35},
year = {2016},
url = {https://doi.org/10.4086/toc.2016.v012a010},
doi = {10.4086/TOC.2016.V012A010},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/ChakrabartiC016.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/ChakrabartyG16,
author = {Deeparnab Chakrabarty and
David J. Galvin},
title = {Special Issue: {APPROX-RANDOM} 2014: Guest Editors' Foreword},
journal = {Theory Comput.},
volume = {12},
number = {1},
pages = {1--3},
year = {2016},
url = {https://doi.org/10.4086/toc.2016.v012a008},
doi = {10.4086/TOC.2016.V012A008},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/ChakrabartyG16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/ChlamtacD16,
author = {Eden Chlamt{\'{a}}c and
Michael Dinitz},
title = {Lowest-Degree k-Spanner: Approximation and Hardness},
journal = {Theory Comput.},
volume = {12},
number = {1},
pages = {1--29},
year = {2016},
url = {https://doi.org/10.4086/toc.2016.v012a015},
doi = {10.4086/TOC.2016.V012A015},
timestamp = {Thu, 14 Oct 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/ChlamtacD16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/DadushK16,
author = {Daniel Dadush and
G{\'{a}}bor Kun},
title = {Lattice Sparsification and the Approximate Closest Vector Problem},
journal = {Theory Comput.},
volume = {12},
number = {1},
pages = {1--34},
year = {2016},
url = {https://doi.org/10.4086/toc.2016.v012a002},
doi = {10.4086/TOC.2016.V012A002},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/DadushK16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/DeMN16,
author = {Anindya De and
Elchanan Mossel and
Joe Neeman},
title = {Majority is Stablest: Discrete and SoS},
journal = {Theory Comput.},
volume = {12},
number = {1},
pages = {1--50},
year = {2016},
url = {https://doi.org/10.4086/toc.2016.v012a004},
doi = {10.4086/TOC.2016.V012A004},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/DeMN16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/GargMV16,
author = {Jugal Garg and
Ruta Mehta and
Vijay V. Vazirani},
title = {Dichotomies in Equilibrium Computation and Membership of {PLC} Markets
in {FIXP}},
journal = {Theory Comput.},
volume = {12},
number = {1},
pages = {1--25},
year = {2016},
url = {https://doi.org/10.4086/toc.2016.v012a020},
doi = {10.4086/TOC.2016.V012A020},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/GargMV16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/Goos016,
author = {Mika G{\"{o}}{\"{o}}s and
Thomas Watson},
title = {Communication Complexity of Set-Disjointness for All Probabilities},
journal = {Theory Comput.},
volume = {12},
number = {1},
pages = {1--23},
year = {2016},
url = {https://doi.org/10.4086/toc.2016.v012a009},
doi = {10.4086/TOC.2016.V012A009},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/Goos016.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/GoosS16,
author = {Mika G{\"{o}}{\"{o}}s and
Jukka Suomela},
title = {Locally Checkable Proofs in Distributed Computing},
journal = {Theory Comput.},
volume = {12},
number = {1},
pages = {1--33},
year = {2016},
url = {https://doi.org/10.4086/toc.2016.v012a019},
doi = {10.4086/TOC.2016.V012A019},
timestamp = {Tue, 29 Dec 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/toc/GoosS16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/GuruswamiL16,
author = {Venkatesan Guruswami and
Euiwoong Lee},
title = {Simple Proof of Hardness of Feedback Vertex Set},
journal = {Theory Comput.},
volume = {12},
number = {1},
pages = {1--11},
year = {2016},
url = {https://doi.org/10.4086/toc.2016.v012a006},
doi = {10.4086/TOC.2016.V012A006},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/GuruswamiL16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/Kopparty0S16,
author = {Swastik Kopparty and
Mrinal Kumar and
Michael E. Saks},
title = {Efficient Indexing of Necklaces and Irreducible Polynomials over Finite
Fields},
journal = {Theory Comput.},
volume = {12},
number = {1},
pages = {1--27},
year = {2016},
url = {https://doi.org/10.4086/toc.2016.v012a007},
doi = {10.4086/TOC.2016.V012A007},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/Kopparty0S16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/LimayeMS16,
author = {Nutan Limaye and
Guillaume Malod and
Srikanth Srinivasan},
title = {Lower Bounds for Non-Commutative Skew Circuits},
journal = {Theory Comput.},
volume = {12},
number = {1},
pages = {1--38},
year = {2016},
url = {https://doi.org/10.4086/toc.2016.v012a012},
doi = {10.4086/TOC.2016.V012A012},
timestamp = {Thu, 14 Oct 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/LimayeMS16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/LinL16,
author = {Cedric Yen{-}Yu Lin and
Han{-}Hsuan Lin},
title = {Upper Bounds on Quantum Query Complexity Inspired by the Elitzur--Vaidman
Bomb Tester},
journal = {Theory Comput.},
volume = {12},
number = {1},
pages = {1--35},
year = {2016},
url = {https://doi.org/10.4086/toc.2016.v012a018},
doi = {10.4086/TOC.2016.V012A018},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/LinL16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/LouisM16,
author = {Anand Louis and
Yury Makarychev},
title = {Approximation Algorithms for Hypergraph Small-Set Expansion and Small-Set
Vertex Expansion},
journal = {Theory Comput.},
volume = {12},
number = {1},
pages = {1--25},
year = {2016},
url = {https://doi.org/10.4086/toc.2016.v012a017},
doi = {10.4086/TOC.2016.V012A017},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/LouisM16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/McKague16,
author = {Matthew McKague},
title = {Interactive Proofs for {BQP} via Self-Tested Graph States},
journal = {Theory Comput.},
volume = {12},
number = {1},
pages = {1--42},
year = {2016},
url = {https://doi.org/10.4086/toc.2016.v012a003},
doi = {10.4086/TOC.2016.V012A003},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/McKague16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/MegowW16,
author = {Nicole Megow and
Mary Wootters},
title = {Special Issue: {APPROX-RANDOM} 2015: Guest Editors' Foreword},
journal = {Theory Comput.},
volume = {12},
number = {1},
pages = {1--3},
year = {2016},
url = {https://doi.org/10.4086/toc.2016.v012a013},
doi = {10.4086/TOC.2016.V012A013},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/MegowW16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/MekaNV16,
author = {Raghu Meka and
Oanh Nguyen and
Van Vu},
title = {Anti-concentration for Polynomials of Independent Random Variables},
journal = {Theory Comput.},
volume = {12},
number = {1},
pages = {1--17},
year = {2016},
url = {https://doi.org/10.4086/toc.2016.v012a011},
doi = {10.4086/TOC.2016.V012A011},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/MekaNV16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/MontanaroW16,
author = {Ashley Montanaro and
Ronald de Wolf},
title = {A Survey of Quantum Property Testing},
journal = {Theory Comput.},
volume = {7},
pages = {1--81},
year = {2016},
url = {https://doi.org/10.4086/toc.gs.2016.007},
doi = {10.4086/TOC.GS.2016.007},
timestamp = {Wed, 22 Jul 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/MontanaroW16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/Thapen16,
author = {Neil Thapen},
title = {A Tradeoff Between Length and Width in Resolution},
journal = {Theory Comput.},
volume = {12},
number = {1},
pages = {1--14},
year = {2016},
url = {https://doi.org/10.4086/toc.2016.v012a005},
doi = {10.4086/TOC.2016.V012A005},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/Thapen16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/AbbeM15,
author = {Emmanuel Abbe and
Andrea Montanari},
title = {Conditional Random Fields, Planted Constraint Satisfaction, and Entropy
Concentration},
journal = {Theory Comput.},
volume = {11},
pages = {413--443},
year = {2015},
url = {https://doi.org/10.4086/toc.2015.v011a017},
doi = {10.4086/TOC.2015.V011A017},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/AbbeM15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/AustrinMW15,
author = {Per Austrin and
Rajsekar Manokaran and
Cenny Wenner},
title = {On the NP-Hardness of Approximating Ordering-Constraint Satisfaction
Problems},
journal = {Theory Comput.},
volume = {11},
pages = {257--283},
year = {2015},
url = {https://doi.org/10.4086/toc.2015.v011a010},
doi = {10.4086/TOC.2015.V011A010},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/AustrinMW15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/Barvinok15,
author = {Alexander I. Barvinok},
title = {Computing the Partition Function for Cliques in a Graph},
journal = {Theory Comput.},
volume = {11},
pages = {339--355},
year = {2015},
url = {https://doi.org/10.4086/toc.2015.v011a013},
doi = {10.4086/TOC.2015.V011A013},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/Barvinok15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/BelovsB15,
author = {Aleksandrs Belovs and
Eric Blais},
title = {Quantum Algorithm for Monotonicity Testing on the Hypercube},
journal = {Theory Comput.},
volume = {11},
pages = {403--412},
year = {2015},
url = {https://doi.org/10.4086/toc.2015.v011a016},
doi = {10.4086/TOC.2015.V011A016},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/BelovsB15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/BrodyL15,
author = {Joshua Brody and
Kasper Green Larsen},
title = {Adapt or Die: Polynomial Lower Bounds for Non-Adaptive Dynamic Data
Structures},
journal = {Theory Comput.},
volume = {11},
pages = {471--489},
year = {2015},
url = {https://doi.org/10.4086/toc.2015.v011a019},
doi = {10.4086/TOC.2015.V011A019},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/BrodyL15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/ChildsGW15,
author = {Andrew M. Childs and
David Gosset and
Zak Webb},
title = {The Bose-Hubbard Model is QMA-complete},
journal = {Theory Comput.},
volume = {11},
pages = {491--603},
year = {2015},
url = {https://doi.org/10.4086/toc.2015.v011a020},
doi = {10.4086/TOC.2015.V011A020},
timestamp = {Tue, 21 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/toc/ChildsGW15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/FabenJ15,
author = {John D. Faben and
Mark Jerrum},
title = {The Complexity of Parity Graph Homomorphism: An Initial Investigation},
journal = {Theory Comput.},
volume = {11},
pages = {35--57},
year = {2015},
url = {https://doi.org/10.4086/toc.2015.v011a002},
doi = {10.4086/TOC.2015.V011A002},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/FabenJ15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/GharanT15,
author = {Shayan Oveis Gharan and
Luca Trevisan},
title = {A New Regularity Lemma and Faster Approximation Algorithms for Low
Threshold Rank Graphs},
journal = {Theory Comput.},
volume = {11},
pages = {241--256},
year = {2015},
url = {https://doi.org/10.4086/toc.2015.v011a009},
doi = {10.4086/TOC.2015.V011A009},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/GharanT15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/GlaubermanG15,
author = {George Glauberman and
Lukasz Grabowski},
title = {Groups with Identical k-Profiles},
journal = {Theory Comput.},
volume = {11},
pages = {395--401},
year = {2015},
url = {https://doi.org/10.4086/toc.2015.v011a015},
doi = {10.4086/TOC.2015.V011A015},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/GlaubermanG15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/GutoskiHMW15,
author = {Gus Gutoski and
Patrick M. Hayden and
Kevin Milner and
Mark M. Wilde},
title = {Quantum Interactive Proofs and the Complexity of Separability Testing},
journal = {Theory Comput.},
volume = {11},
pages = {59--103},
year = {2015},
url = {https://doi.org/10.4086/toc.2015.v011a003},
doi = {10.4086/TOC.2015.V011A003},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/GutoskiHMW15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/HaramatyRS15,
author = {Elad Haramaty and
Noga Ron{-}Zewi and
Madhu Sudan},
title = {Absolutely Sound Testing of Lifted Codes},
journal = {Theory Comput.},
volume = {11},
pages = {299--338},
year = {2015},
url = {https://doi.org/10.4086/toc.2015.v011a012},
doi = {10.4086/TOC.2015.V011A012},
timestamp = {Tue, 14 Jun 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/HaramatyRS15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/HrubesW15,
author = {Pavel Hrubes and
Avi Wigderson},
title = {Non-Commutative Arithmetic Circuits with Division},
journal = {Theory Comput.},
volume = {11},
pages = {357--393},
year = {2015},
url = {https://doi.org/10.4086/toc.2015.v011a014},
doi = {10.4086/TOC.2015.V011A014},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/HrubesW15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/JendrejOW15,
author = {Jacek Jendrej and
Krzysztof Oleszkiewicz and
Jakub Onufry Wojtaszczyk},
title = {On some extensions of the {FKN} theorem},
journal = {Theory Comput.},
volume = {11},
pages = {445--469},
year = {2015},
url = {https://doi.org/10.4086/toc.2015.v011a018},
doi = {10.4086/TOC.2015.V011A018},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/JendrejOW15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/KempeKT15,
author = {David Kempe and
Jon M. Kleinberg and
{\'{E}}va Tardos},
title = {Maximizing the Spread of Influence through a Social Network},
journal = {Theory Comput.},
volume = {11},
pages = {105--147},
year = {2015},
url = {https://doi.org/10.4086/toc.2015.v011a004},
doi = {10.4086/TOC.2015.V011A004},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/KempeKT15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/Kopparty15,
author = {Swastik Kopparty},
title = {List-Decoding Multiplicity Codes},
journal = {Theory Comput.},
volume = {11},
pages = {149--182},
year = {2015},
url = {https://doi.org/10.4086/toc.2015.v011a005},
doi = {10.4086/TOC.2015.V011A005},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/Kopparty15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/Kuperberg15,
author = {Greg Kuperberg},
title = {How Hard Is It to Approximate the Jones Polynomial?},
journal = {Theory Comput.},
volume = {11},
pages = {183--219},
year = {2015},
url = {https://doi.org/10.4086/toc.2015.v011a006},
doi = {10.4086/TOC.2015.V011A006},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/Kuperberg15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/LandsbergO15,
author = {Joseph M. Landsberg and
Giorgio Ottaviani},
title = {New Lower Bounds for the Border Rank of Matrix Multiplication},
journal = {Theory Comput.},
volume = {11},
pages = {285--298},
year = {2015},
url = {https://doi.org/10.4086/toc.2015.v011a011},
doi = {10.4086/TOC.2015.V011A011},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/LandsbergO15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/Lovett15,
author = {Shachar Lovett},
title = {An Exposition of Sanders' Quasi-Polynomial Freiman-Ruzsa Theorem},
journal = {Theory Comput.},
volume = {6},
pages = {1--14},
year = {2015},
url = {https://doi.org/10.4086/toc.gs.2015.006},
doi = {10.4086/TOC.GS.2015.006},
timestamp = {Wed, 22 Jul 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/Lovett15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/Moshkovitz15,
author = {Dana Moshkovitz},
title = {The Projection Games Conjecture and the NP-Hardness of ln n-Approximating
Set-Cover},
journal = {Theory Comput.},
volume = {11},
pages = {221--235},
year = {2015},
url = {https://doi.org/10.4086/toc.2015.v011a007},
doi = {10.4086/TOC.2015.V011A007},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/Moshkovitz15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/RaskhodnikovaS15,
author = {Sofya Raskhodnikova and
Ola Svensson},
title = {Special Issue: {APPROX-RANDOM} 2013: Guest Editors' Foreword},
journal = {Theory Comput.},
volume = {11},
pages = {237--239},
year = {2015},
url = {https://doi.org/10.4086/toc.2015.v011a008},
doi = {10.4086/TOC.2015.V011A008},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/RaskhodnikovaS15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/Watson15,
author = {Thomas Watson},
title = {The Complexity of Deciding Statistical Properties of Samplable Distributions},
journal = {Theory Comput.},
volume = {11},
pages = {1--34},
year = {2015},
url = {https://doi.org/10.4086/toc.2015.v011a001},
doi = {10.4086/TOC.2015.V011A001},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/Watson15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/AaronsonA14,
author = {Scott Aaronson and
Andris Ambainis},
title = {The Need for Structure in Quantum Speedups},
journal = {Theory Comput.},
volume = {10},
pages = {133--166},
year = {2014},
url = {https://doi.org/10.4086/toc.2014.v010a006},
doi = {10.4086/TOC.2014.V010A006},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/AaronsonA14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/AllenderCLPT14,
author = {Eric Allender and
Shiteng Chen and
Tiancheng Lou and
Periklis A. Papakonstantinou and
Bangsheng Tang},
title = {Width-Parametrized {SAT:} Time--Space Tradeoffs},
journal = {Theory Comput.},
volume = {10},
pages = {297--339},
year = {2014},
url = {https://doi.org/10.4086/toc.2014.v010a012},
doi = {10.4086/TOC.2014.V010A012},
timestamp = {Fri, 09 Apr 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/AllenderCLPT14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/AllenderL14,
author = {Eric Allender and
Klaus{-}J{\"{o}}rn Lange},
title = {Symmetry Coincides with Nondeterminism for Time-Bounded Auxiliary
Pushdown Automata},
journal = {Theory Comput.},
volume = {10},
pages = {199--215},
year = {2014},
url = {https://doi.org/10.4086/toc.2014.v010a008},
doi = {10.4086/TOC.2014.V010A008},
timestamp = {Fri, 09 Apr 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/AllenderL14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/BrietFV14,
author = {Jop Bri{\"{e}}t and
Fernando M{\'{a}}rio de Oliveira Filho and
Frank Vallentin},
title = {Grothendieck Inequalities for Semidefinite Programs with Rank Constraint},
journal = {Theory Comput.},
volume = {10},
pages = {77--105},
year = {2014},
url = {https://doi.org/10.4086/toc.2014.v010a004},
doi = {10.4086/TOC.2014.V010A004},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/BrietFV14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/BrunschGRR14,
author = {Tobias Brunsch and
Navin Goyal and
Luis Rademacher and
Heiko R{\"{o}}glin},
title = {Lower Bounds for the Average and Smoothed Number of Pareto-Optima},
journal = {Theory Comput.},
volume = {10},
pages = {237--256},
year = {2014},
url = {https://doi.org/10.4086/toc.2014.v010a010},
doi = {10.4086/TOC.2014.V010A010},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/BrunschGRR14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/CaiG14,
author = {Jin{-}Yi Cai and
Aaron Gorenstein},
title = {Matchgates Revisited},
journal = {Theory Comput.},
volume = {10},
pages = {167--197},
year = {2014},
url = {https://doi.org/10.4086/toc.2014.v010a007},
doi = {10.4086/TOC.2014.V010A007},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/CaiG14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/ChakrabartyS14,
author = {Deeparnab Chakrabarty and
C. Seshadhri},
title = {An Optimal Lower Bound for Monotonicity Testing over Hypergrids},
journal = {Theory Comput.},
volume = {10},
pages = {453--464},
year = {2014},
url = {https://doi.org/10.4086/toc.2014.v010a017},
doi = {10.4086/TOC.2014.V010A017},
timestamp = {Thu, 07 Jul 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/ChakrabartyS14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/ChakrabortyFM14,
author = {Sourav Chakraborty and
Eldar Fischer and
Arie Matsliah},
title = {Query Complexity Lower Bounds for Reconstruction of Codes},
journal = {Theory Comput.},
volume = {10},
pages = {515--533},
year = {2014},
url = {https://doi.org/10.4086/toc.2014.v010a019},
doi = {10.4086/TOC.2014.V010A019},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/ChakrabortyFM14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/ChanP14,
author = {Siu Man Chan and
Aaron Potechin},
title = {Tight Bounds for Monotone Switching Networks via Fourier Analysis},
journal = {Theory Comput.},
volume = {10},
pages = {389--419},
year = {2014},
url = {https://doi.org/10.4086/toc.2014.v010a015},
doi = {10.4086/TOC.2014.V010A015},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/ChanP14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/Chazelle14,
author = {Bernard Chazelle},
title = {How Many Bits Can a Flock of Birds Compute?},
journal = {Theory Comput.},
volume = {10},
pages = {421--451},
year = {2014},
url = {https://doi.org/10.4086/toc.2014.v010a016},
doi = {10.4086/TOC.2014.V010A016},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/Chazelle14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/DaskalakisDS14,
author = {Constantinos Daskalakis and
Ilias Diakonikolas and
Rocco A. Servedio},
title = {Learning \emph{k}-Modal Distributions via Testing},
journal = {Theory Comput.},
volume = {10},
pages = {535--570},
year = {2014},
url = {https://doi.org/10.4086/toc.2014.v010a020},
doi = {10.4086/TOC.2014.V010A020},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/DaskalakisDS14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/DiakonikolasSTW14,
author = {Ilias Diakonikolas and
Rocco A. Servedio and
Li{-}Yang Tan and
Andrew Wan},
title = {A Regularity Lemma and Low-Weight Approximators for Low-Degree Polynomial
Threshold Functions},
journal = {Theory Comput.},
volume = {10},
pages = {27--53},
year = {2014},
url = {https://doi.org/10.4086/toc.2014.v010a002},
doi = {10.4086/TOC.2014.V010A002},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/DiakonikolasSTW14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/HarrowKS14,
author = {Aram W. Harrow and
Alexandra Kolla and
Leonard J. Schulman},
title = {Dimension-Free L\({}_{\mbox{2}}\) Maximal Inequality for Spherical
Means in the Hypercube},
journal = {Theory Comput.},
volume = {10},
pages = {55--75},
year = {2014},
url = {https://doi.org/10.4086/toc.2014.v010a003},
doi = {10.4086/TOC.2014.V010A003},
timestamp = {Tue, 21 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/toc/HarrowKS14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/HarshaKM14,
author = {Prahladh Harsha and
Adam R. Klivans and
Raghu Meka},
title = {Bounding the Sensitivity of Polynomial Threshold Functions},
journal = {Theory Comput.},
volume = {10},
pages = {1--26},
year = {2014},
url = {https://doi.org/10.4086/toc.2014.v010a001},
doi = {10.4086/TOC.2014.V010A001},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/HarshaKM14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/Huang14,
author = {Sangxia Huang},
title = {Approximation Resistance on Satisfiable Instances for Sparse Predicates},
journal = {Theory Comput.},
volume = {10},
pages = {359--388},
year = {2014},
url = {https://doi.org/10.4086/toc.2014.v010a014},
doi = {10.4086/TOC.2014.V010A014},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/Huang14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/KolR14,
author = {Gillat Kol and
Ran Raz},
title = {Competing-Provers Protocols for Circuit Evaluation},
journal = {Theory Comput.},
volume = {10},
pages = {107--131},
year = {2014},
url = {https://doi.org/10.4086/toc.2014.v010a005},
doi = {10.4086/TOC.2014.V010A005},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/KolR14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/Lampis14,
author = {Michael Lampis},
title = {Improved Inapproximability for {TSP}},
journal = {Theory Comput.},
volume = {10},
pages = {217--236},
year = {2014},
url = {https://doi.org/10.4086/toc.2014.v010a009},
doi = {10.4086/TOC.2014.V010A009},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/Lampis14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/MakarychevM14,
author = {Konstantin Makarychev and
Yury Makarychev},
title = {Approximation Algorithm for Non-Boolean Max-\emph{k}-CSP},
journal = {Theory Comput.},
volume = {10},
pages = {341--358},
year = {2014},
url = {https://doi.org/10.4086/toc.2014.v010a013},
doi = {10.4086/TOC.2014.V010A013},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/MakarychevM14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/NaorRV14,
author = {Assaf Naor and
Oded Regev and
Thomas Vidick},
title = {Efficient Rounding for the Noncommutative Grothendieck Inequality},
journal = {Theory Comput.},
volume = {10},
pages = {257--295},
year = {2014},
url = {https://doi.org/10.4086/toc.2014.v010a011},
doi = {10.4086/TOC.2014.V010A011},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/NaorRV14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/ShpilkaV14,
author = {Amir Shpilka and
Ilya Volkovich},
title = {On Reconstruction and Testing of Read-Once Formulas},
journal = {Theory Comput.},
volume = {10},
pages = {465--514},
year = {2014},
url = {https://doi.org/10.4086/toc.2014.v010a018},
doi = {10.4086/TOC.2014.V010A018},
timestamp = {Mon, 26 Jun 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/ShpilkaV14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/AaronsonA13,
author = {Scott Aaronson and
Alex Arkhipov},
title = {The Computational Complexity of Linear Optics},
journal = {Theory Comput.},
volume = {9},
pages = {143--252},
year = {2013},
url = {https://doi.org/10.4086/toc.2013.v009a004},
doi = {10.4086/TOC.2013.V009A004},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/AaronsonA13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/AaronsonC13,
author = {Scott Aaronson and
Paul F. Christiano},
title = {Quantum Money from Hidden Subspaces},
journal = {Theory Comput.},
volume = {9},
pages = {349--401},
year = {2013},
url = {https://doi.org/10.4086/toc.2013.v009a009},
doi = {10.4086/TOC.2013.V009A009},
timestamp = {Thu, 01 Apr 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/AaronsonC13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/AlonL13,
author = {Noga Alon and
Shachar Lovett},
title = {Almost k-Wise vs. k-Wise Independent Permutations, and Uniformity
for General Group Actions},
journal = {Theory Comput.},
volume = {9},
pages = {559--577},
year = {2013},
url = {https://doi.org/10.4086/toc.2013.v009a015},
doi = {10.4086/TOC.2013.V009A015},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/AlonL13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/AndoniR13,
author = {Alexandr Andoni and
Atri Rudra},
title = {Special Issue: {APPROX-RANDOM} 2012: Guest Editors' Foreword},
journal = {Theory Comput.},
volume = {9},
pages = {437--439},
year = {2013},
url = {https://doi.org/10.4086/toc.2013.v009a012},
doi = {10.4086/TOC.2013.V009A012},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/AndoniR13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/AustrinBC13,
author = {Per Austrin and
Mark Braverman and
Eden Chlamtac},
title = {Inapproximability of NP-Complete Variants of Nash Equilibrium},
journal = {Theory Comput.},
volume = {9},
pages = {117--142},
year = {2013},
url = {https://doi.org/10.4086/toc.2013.v009a003},
doi = {10.4086/TOC.2013.V009A003},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/AustrinBC13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/Ben-AroyaT13,
author = {Avraham Ben{-}Aroya and
Amnon Ta{-}Shma},
title = {Constructing Small-Bias Sets from Algebraic-Geometric Codes},
journal = {Theory Comput.},
volume = {9},
pages = {253--272},
year = {2013},
url = {https://doi.org/10.4086/toc.2013.v009a005},
doi = {10.4086/TOC.2013.V009A005},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/Ben-AroyaT13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/Ben-SassonG13,
author = {Eli Ben{-}Sasson and
Ariel Gabizon},
title = {Extractors for Polynomial Sources over Fields of Constant Order and
Small Characteristic},
journal = {Theory Comput.},
volume = {9},
pages = {665--683},
year = {2013},
url = {https://doi.org/10.4086/toc.2013.v009a021},
doi = {10.4086/TOC.2013.V009A021},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/Ben-SassonG13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/BhaskaraDS13,
author = {Aditya Bhaskara and
Devendra Desai and
Srikanth Srinivasan},
title = {Optimal Hitting Sets for Combinatorial Shapes},
journal = {Theory Comput.},
volume = {9},
pages = {441--470},
year = {2013},
url = {https://doi.org/10.4086/toc.2013.v009a013},
doi = {10.4086/TOC.2013.V009A013},
timestamp = {Thu, 14 Oct 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/BhaskaraDS13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/BlaisT13,
author = {Eric Blais and
Li{-}Yang Tan},
title = {Hypercontractivity Via the Entropy Method},
journal = {Theory Comput.},
volume = {9},
pages = {889--896},
year = {2013},
url = {https://doi.org/10.4086/toc.2013.v009a029},
doi = {10.4086/TOC.2013.V009A029},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/BlaisT13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/Blaser13,
author = {Markus Bl{\"{a}}ser},
title = {Fast Matrix Multiplication},
journal = {Theory Comput.},
volume = {5},
pages = {1--60},
year = {2013},
url = {https://doi.org/10.4086/toc.gs.2013.005},
doi = {10.4086/TOC.GS.2013.005},
timestamp = {Wed, 22 Jul 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/Blaser13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/BogdanovDVY13,
author = {Andrej Bogdanov and
Zeev Dvir and
Elad Verbin and
Amir Yehudayoff},
title = {Pseudorandomness for Width-2 Branching Programs},
journal = {Theory Comput.},
volume = {9},
pages = {283--293},
year = {2013},
url = {https://doi.org/10.4086/toc.2013.v009a007},
doi = {10.4086/TOC.2013.V009A007},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/BogdanovDVY13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/BryansCDKS13,
author = {Nathaniel Bryans and
Ehsan Chiniforooshan and
David Doty and
Lila Kari and
Shinnosuke Seki},
title = {The Power of Nondeterminism in Self-Assembly},
journal = {Theory Comput.},
volume = {9},
pages = {1--29},
year = {2013},
url = {https://doi.org/10.4086/toc.2013.v009a001},
doi = {10.4086/TOC.2013.V009A001},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/BryansCDKS13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/ChungMV13,
author = {Kai{-}Min Chung and
Michael Mitzenmacher and
Salil P. Vadhan},
title = {Why Simple Hash Functions Work: Exploiting the Entropy in a Data Stream},
journal = {Theory Comput.},
volume = {9},
pages = {897--945},
year = {2013},
url = {https://doi.org/10.4086/toc.2013.v009a030},
doi = {10.4086/TOC.2013.V009A030},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/ChungMV13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/FeffermanSUV13,
author = {Bill Fefferman and
Ronen Shaltiel and
Christopher Umans and
Emanuele Viola},
title = {On Beating the Hybrid Argument},
journal = {Theory Comput.},
volume = {9},
pages = {809--843},
year = {2013},
url = {https://doi.org/10.4086/toc.2013.v009a026},
doi = {10.4086/TOC.2013.V009A026},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/FeffermanSUV13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/FeigeMV13,
author = {Uriel Feige and
Elchanan Mossel and
Dan Vilenchik},
title = {Complete Convergence of Message Passing Algorithms for Some Satisfiability
Problems},
journal = {Theory Comput.},
volume = {9},
pages = {617--651},
year = {2013},
url = {https://doi.org/10.4086/toc.2013.v009a019},
doi = {10.4086/TOC.2013.V009A019},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/FeigeMV13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/GottesmanI13,
author = {Daniel Gottesman and
Sandy Irani},
title = {The Quantum and Classical Complexity of Translationally Invariant
Tiling and Hamiltonian Problems},
journal = {Theory Comput.},
volume = {9},
pages = {31--116},
year = {2013},
url = {https://doi.org/10.4086/toc.2013.v009a002},
doi = {10.4086/TOC.2013.V009A002},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/GottesmanI13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/GuruswamiS13,
author = {Venkatesan Guruswami and
Ali Kemal Sinop},
title = {Improved Inapproximability Results for Maximum k-Colorable Subgraph},
journal = {Theory Comput.},
volume = {9},
pages = {413--435},
year = {2013},
url = {https://doi.org/10.4086/toc.2013.v009a011},
doi = {10.4086/TOC.2013.V009A011},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/GuruswamiS13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/Hastad13,
author = {Johan H{\aa}stad},
title = {Satisfying Degree-d Equations over GF[2]\({}^{\mbox{n}}\)},
journal = {Theory Comput.},
volume = {9},
pages = {845--862},
year = {2013},
url = {https://doi.org/10.4086/toc.2013.v009a027},
doi = {10.4086/TOC.2013.V009A027},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/Hastad13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/Hrubes13,
author = {Pavel Hrubes},
title = {On the Real {\(\tau\)}-Conjecture and the Distribution of Complex
Roots},
journal = {Theory Comput.},
volume = {9},
pages = {403--411},
year = {2013},
url = {https://doi.org/10.4086/toc.2013.v009a010},
doi = {10.4086/TOC.2013.V009A010},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/Hrubes13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/Kane13,
author = {Daniel M. Kane},
title = {A Monotone Function Given By a Low-Depth Decision Tree That Is Not
an Approximate Junta},
journal = {Theory Comput.},
volume = {9},
pages = {587--592},
year = {2013},
url = {https://doi.org/10.4086/toc.2013.v009a017},
doi = {10.4086/TOC.2013.V009A017},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/Kane13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/KhotS13,
author = {Subhash Khot and
Muli Safra},
title = {A Two-Prover One-Round Game with Strong Soundness},
journal = {Theory Comput.},
volume = {9},
pages = {863--887},
year = {2013},
url = {https://doi.org/10.4086/toc.2013.v009a028},
doi = {10.4086/TOC.2013.V009A028},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/KhotS13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/LeviRR13,
author = {Reut Levi and
Dana Ron and
Ronitt Rubinfeld},
title = {Testing Properties of Collections of Distributions},
journal = {Theory Comput.},
volume = {9},
pages = {295--347},
year = {2013},
url = {https://doi.org/10.4086/toc.2013.v009a008},
doi = {10.4086/TOC.2013.V009A008},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/LeviRR13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/MertensM13,
author = {Stephan Mertens and
Cristopher Moore},
title = {The Complexity of the Fermionant and Immanants of Constant Width [Note]},
journal = {Theory Comput.},
volume = {9},
pages = {273--282},
year = {2013},
url = {https://doi.org/10.4086/toc.2013.v009a006},
doi = {10.4086/TOC.2013.V009A006},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/MertensM13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/MosselO13,
author = {Elchanan Mossel and
Ryan O'Donnell},
title = {Special Issue on Analysis of Boolean Functions: Guest Editors' Foreword},
journal = {Theory Comput.},
volume = {9},
pages = {579--585},
year = {2013},
url = {https://doi.org/10.4086/toc.2013.v009a016},
doi = {10.4086/TOC.2013.V009A016},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/MosselO13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/NordstromH13,
author = {Jakob Nordstr{\"{o}}m and
Johan H{\aa}stad},
title = {Towards an Optimal Separation of Space and Length in Resolution},
journal = {Theory Comput.},
volume = {9},
pages = {471--557},
year = {2013},
url = {https://doi.org/10.4086/toc.2013.v009a014},
doi = {10.4086/TOC.2013.V009A014},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/NordstromH13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/Ron-ZewiS13,
author = {Noga Ron{-}Zewi and
Madhu Sudan},
title = {A New Upper Bound on the Query Complexity of Testing Generalized Reed-Muller
Codes},
journal = {Theory Comput.},
volume = {9},
pages = {783--807},
year = {2013},
url = {https://doi.org/10.4086/toc.2013.v009a025},
doi = {10.4086/TOC.2013.V009A025},
timestamp = {Tue, 14 Jun 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/Ron-ZewiS13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/SheldonY13,
author = {Daniel Sheldon and
Neal E. Young},
title = {Hamming Approximation of {NP} Witnesses},
journal = {Theory Comput.},
volume = {9},
pages = {685--702},
year = {2013},
url = {https://doi.org/10.4086/toc.2013.v009a022},
doi = {10.4086/TOC.2013.V009A022},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/SheldonY13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/Sherstov13,
author = {Alexander A. Sherstov},
title = {Making Polynomials Robust to Noise},
journal = {Theory Comput.},
volume = {9},
pages = {593--615},
year = {2013},
url = {https://doi.org/10.4086/toc.2013.v009a018},
doi = {10.4086/TOC.2013.V009A018},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/Sherstov13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/Sherstov13a,
author = {Alexander A. Sherstov},
title = {Approximating the {AND-OR} Tree},
journal = {Theory Comput.},
volume = {9},
pages = {653--663},
year = {2013},
url = {https://doi.org/10.4086/toc.2013.v009a020},
doi = {10.4086/TOC.2013.V009A020},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/Sherstov13a.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/Svensson13,
author = {Ola Svensson},
title = {Hardness of Vertex Deletion and Project Scheduling},
journal = {Theory Comput.},
volume = {9},
pages = {759--781},
year = {2013},
url = {https://doi.org/10.4086/toc.2013.v009a024},
doi = {10.4086/TOC.2013.V009A024},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/Svensson13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/Wenner13,
author = {Cenny Wenner},
title = {Circumventing d-to-1 for Approximation Resistance of Satisfiable Predicates
Strictly Containing Parity of Width at Least Four},
journal = {Theory Comput.},
volume = {9},
pages = {703--757},
year = {2013},
url = {https://doi.org/10.4086/toc.2013.v009a023},
doi = {10.4086/TOC.2013.V009A023},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/Wenner13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/AnagnostopoulosDK12,
author = {Aris Anagnostopoulos and
Anirban Dasgupta and
Ravi Kumar},
title = {A Constant-Factor Approximation Algorithm for Co-clustering},
journal = {Theory Comput.},
volume = {8},
number = {1},
pages = {597--622},
year = {2012},
url = {https://doi.org/10.4086/toc.2012.v008a026},
doi = {10.4086/TOC.2012.V008A026},
timestamp = {Tue, 21 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/toc/AnagnostopoulosDK12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/AroraHK12,
author = {Sanjeev Arora and
Elad Hazan and
Satyen Kale},
title = {The Multiplicative Weights Update Method: a Meta-Algorithm and Applications},
journal = {Theory Comput.},
volume = {8},
number = {1},
pages = {121--164},
year = {2012},
url = {https://doi.org/10.4086/toc.2012.v008a006},
doi = {10.4086/TOC.2012.V008A006},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/AroraHK12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/BahmaniMM12,
author = {Bahman Bahmani and
Aranyak Mehta and
Rajeev Motwani},
title = {Online Graph Edge-Coloring in the Random-Order Arrival Model},
journal = {Theory Comput.},
volume = {8},
number = {1},
pages = {567--595},
year = {2012},
url = {https://doi.org/10.4086/toc.2012.v008a025},
doi = {10.4086/TOC.2012.V008A025},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/BahmaniMM12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/BansalCKP12,
author = {Nikhil Bansal and
Ho{-}Leung Chan and
Dmitriy Katz and
Kirk Pruhs},
title = {Improved Bounds for Speed Scaling in Devices Obeying the Cube-Root
Rule},
journal = {Theory Comput.},
volume = {8},
number = {1},
pages = {209--229},
year = {2012},
url = {https://doi.org/10.4086/toc.2012.v008a009},
doi = {10.4086/TOC.2012.V008A009},
timestamp = {Tue, 15 Feb 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/toc/BansalCKP12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/BansalKNS12,
author = {Nikhil Bansal and
Nitish Korula and
Viswanath Nagarajan and
Aravind Srinivasan},
title = {Solving Packing Integer Programs via Randomized Rounding with Alterations},
journal = {Theory Comput.},
volume = {8},
number = {1},
pages = {533--565},
year = {2012},
url = {https://doi.org/10.4086/toc.2012.v008a024},
doi = {10.4086/TOC.2012.V008A024},
timestamp = {Tue, 15 Feb 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/toc/BansalKNS12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/BansalW12,
author = {Nikhil Bansal and
Ryan Williams},
title = {Regularity Lemmas and Combinatorial Algorithms},
journal = {Theory Comput.},
volume = {8},
number = {1},
pages = {69--94},
year = {2012},
url = {https://doi.org/10.4086/toc.2012.v008a004},
doi = {10.4086/TOC.2012.V008A004},
timestamp = {Tue, 15 Feb 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/toc/BansalW12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/BenabbasGMT12,
author = {Siavosh Benabbas and
Konstantinos Georgiou and
Avner Magen and
Madhur Tulsiani},
title = {{SDP} Gaps from Pairwise Independence},
journal = {Theory Comput.},
volume = {8},
number = {1},
pages = {269--289},
year = {2012},
url = {https://doi.org/10.4086/toc.2012.v008a012},
doi = {10.4086/TOC.2012.V008A012},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/BenabbasGMT12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/BhattacharyaGGM12,
author = {Sayan Bhattacharya and
Gagan Goel and
Sreenivas Gollapudi and
Kamesh Munagala},
title = {Budget-Constrained Auctions with Heterogeneous Items},
journal = {Theory Comput.},
volume = {8},
number = {1},
pages = {429--460},
year = {2012},
url = {https://doi.org/10.4086/toc.2012.v008a020},
doi = {10.4086/TOC.2012.V008A020},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/BhattacharyaGGM12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/BuhrmanRSW12,
author = {Harry Buhrman and
Oded Regev and
Giannicola Scarpa and
Ronald de Wolf},
title = {Near-Optimal and Explicit Bell Inequality Violations},
journal = {Theory Comput.},
volume = {8},
number = {1},
pages = {623--645},
year = {2012},
url = {https://doi.org/10.4086/toc.2012.v008a027},
doi = {10.4086/TOC.2012.V008A027},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/BuhrmanRSW12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/ChekuriIM12,
author = {Chandra Chekuri and
Sungjin Im and
Benjamin Moseley},
title = {Online Scheduling to Minimize Maximum Response Time and Maximum Delay
Factor},
journal = {Theory Comput.},
volume = {8},
number = {1},
pages = {165--195},
year = {2012},
url = {https://doi.org/10.4086/toc.2012.v008a007},
doi = {10.4086/TOC.2012.V008A007},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/ChekuriIM12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/ChuzhoyK12,
author = {Julia Chuzhoy and
Sanjeev Khanna},
title = {An O(k\({}^{\mbox{3}}\)log n)-Approximation Algorithm for Vertex-Connectivity
Survivable Network Design},
journal = {Theory Comput.},
volume = {8},
number = {1},
pages = {401--413},
year = {2012},
url = {https://doi.org/10.4086/toc.2012.v008a018},
doi = {10.4086/TOC.2012.V008A018},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/ChuzhoyK12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/DughmiRS12,
author = {Shaddin Dughmi and
Tim Roughgarden and
Mukund Sundararajan},
title = {Revenue Submodularity},
journal = {Theory Comput.},
volume = {8},
number = {1},
pages = {95--119},
year = {2012},
url = {https://doi.org/10.4086/toc.2012.v008a005},
doi = {10.4086/TOC.2012.V008A005},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/DughmiRS12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/FelzenszwalbH12,
author = {Pedro F. Felzenszwalb and
Daniel P. Huttenlocher},
title = {Distance Transforms of Sampled Functions},
journal = {Theory Comput.},
volume = {8},
number = {1},
pages = {415--428},
year = {2012},
url = {https://doi.org/10.4086/toc.2012.v008a019},
doi = {10.4086/TOC.2012.V008A019},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/FelzenszwalbH12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/Gall12,
author = {Fran{\c{c}}ois Le Gall},
title = {Quantum Private Information Retrieval with Sublinear Communication
Complexity},
journal = {Theory Comput.},
volume = {8},
number = {1},
pages = {369--374},
year = {2012},
url = {https://doi.org/10.4086/toc.2012.v008a016},
doi = {10.4086/TOC.2012.V008A016},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/Gall12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/GoelP12,
author = {Ashish Goel and
Ian Post},
title = {One Tree Suffices: {A} Simultaneous O(1)-Approximation for Single-Sink
Buy-at-Bulk},
journal = {Theory Comput.},
volume = {8},
number = {1},
pages = {351--368},
year = {2012},
url = {https://doi.org/10.4086/toc.2012.v008a015},
doi = {10.4086/TOC.2012.V008A015},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/GoelP12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/GoldreichI12,
author = {Oded Goldreich and
Rani Izsak},
title = {Monotone Circuits: One-Way Functions versus Pseudorandom Generators},
journal = {Theory Comput.},
volume = {8},
number = {1},
pages = {231--238},
year = {2012},
url = {https://doi.org/10.4086/toc.2012.v008a010},
doi = {10.4086/TOC.2012.V008A010},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/GoldreichI12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/GuruswamiZ12,
author = {Venkatesan Guruswami and
Yuan Zhou},
title = {Tight Bounds on the Approximability of Almost-Satisfiable Horn {SAT}
and Exact Hitting Set},
journal = {Theory Comput.},
volume = {8},
number = {1},
pages = {239--267},
year = {2012},
url = {https://doi.org/10.4086/toc.2012.v008a011},
doi = {10.4086/TOC.2012.V008A011},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/GuruswamiZ12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/Har-PeledIM12,
author = {Sariel Har{-}Peled and
Piotr Indyk and
Rajeev Motwani},
title = {Approximate Nearest Neighbor: Towards Removing the Curse of Dimensionality},
journal = {Theory Comput.},
volume = {8},
number = {1},
pages = {321--350},
year = {2012},
url = {https://doi.org/10.4086/toc.2012.v008a014},
doi = {10.4086/TOC.2012.V008A014},
timestamp = {Tue, 07 May 2024 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/Har-PeledIM12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/HavivR12,
author = {Ishay Haviv and
Oded Regev},
title = {Tensor-based Hardness of the Shortest Vector Problem to within Almost
Polynomial Factors},
journal = {Theory Comput.},
volume = {8},
number = {1},
pages = {513--531},
year = {2012},
url = {https://doi.org/10.4086/toc.2012.v008a023},
doi = {10.4086/TOC.2012.V008A023},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/HavivR12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/JainKKSSZ12,
author = {Rahul Jain and
Iordanis Kerenidis and
Greg Kuperberg and
Miklos Santha and
Or Sattath and
Shengyu Zhang},
title = {On the Power of a Unique Quantum Witness},
journal = {Theory Comput.},
volume = {8},
number = {1},
pages = {375--400},
year = {2012},
url = {https://doi.org/10.4086/toc.2012.v008a017},
doi = {10.4086/TOC.2012.V008A017},
timestamp = {Tue, 21 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/toc/JainKKSSZ12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/KasherK12,
author = {Roy Kasher and
Julia Kempe},
title = {Two-Source Extractors Secure Against Quantum Adversaries},
journal = {Theory Comput.},
volume = {8},
number = {1},
pages = {461--486},
year = {2012},
url = {https://doi.org/10.4086/toc.2012.v008a021},
doi = {10.4086/TOC.2012.V008A021},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/KasherK12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/KhullerG12,
author = {Samir Khuller and
Sudipto Guha},
title = {Special Issue in Honor of Rajeev Motwani {(1962-2009):} Guest Editors'
Foreword},
journal = {Theory Comput.},
volume = {8},
number = {1},
pages = {53--54},
year = {2012},
url = {https://doi.org/10.4086/toc.2012.v008a002},
doi = {10.4086/TOC.2012.V008A002},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/KhullerG12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/MelkebeekW12,
author = {Dieter van Melkebeek and
Thomas Watson},
title = {Time-Space Efficient Simulations of Quantum Computations},
journal = {Theory Comput.},
volume = {8},
number = {1},
pages = {1--51},
year = {2012},
url = {https://doi.org/10.4086/toc.2012.v008a001},
doi = {10.4086/TOC.2012.V008A001},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/MelkebeekW12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/Micciancio12,
author = {Daniele Micciancio},
title = {Inapproximability of the Shortest Vector Problem: Toward a Deterministic
Reduction},
journal = {Theory Comput.},
volume = {8},
number = {1},
pages = {487--512},
year = {2012},
url = {https://doi.org/10.4086/toc.2012.v008a022},
doi = {10.4086/TOC.2012.V008A022},
timestamp = {Mon, 05 Feb 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/toc/Micciancio12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/Raghavan12,
author = {Prabhakar Raghavan},
title = {Rajeev Motwani {(1962-2009)}},
journal = {Theory Comput.},
volume = {8},
number = {1},
pages = {55--68},
year = {2012},
url = {https://doi.org/10.4086/toc.2012.v008a003},
doi = {10.4086/TOC.2012.V008A003},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/Raghavan12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/ReichardtS12,
author = {Ben Reichardt and
Robert Spalek},
title = {Span-Program-Based Quantum Algorithm for Evaluating Formulas},
journal = {Theory Comput.},
volume = {8},
number = {1},
pages = {291--319},
year = {2012},
url = {https://doi.org/10.4086/toc.2012.v008a013},
doi = {10.4086/TOC.2012.V008A013},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/ReichardtS12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/Sherstov12,
author = {Alexander A. Sherstov},
title = {The Communication Complexity of Gap Hamming Distance},
journal = {Theory Comput.},
volume = {8},
number = {1},
pages = {197--208},
year = {2012},
url = {https://doi.org/10.4086/toc.2012.v008a008},
doi = {10.4086/TOC.2012.V008A008},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/Sherstov12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/AaronsonM11,
author = {Scott Aaronson and
Dieter van Melkebeek},
title = {On Circuit Lower Bounds from Derandomization},
journal = {Theory Comput.},
volume = {7},
number = {1},
pages = {177--184},
year = {2011},
url = {https://doi.org/10.4086/toc.2011.v007a012},
doi = {10.4086/TOC.2011.V007A012},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/AaronsonM11.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/Amano11,
author = {Kazuyuki Amano},
title = {Tight Bounds on the Average Sensitivity of k-CNF},
journal = {Theory Comput.},
volume = {7},
number = {1},
pages = {45--48},
year = {2011},
url = {https://doi.org/10.4086/toc.2011.v007a004},
doi = {10.4086/TOC.2011.V007A004},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/Amano11.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/AustrinKS11,
author = {Per Austrin and
Subhash Khot and
Muli Safra},
title = {Inapproximability of Vertex Cover and Independent Set in Bounded Degree
Graphs},
journal = {Theory Comput.},
volume = {7},
number = {1},
pages = {27--43},
year = {2011},
url = {https://doi.org/10.4086/toc.2011.v007a003},
doi = {10.4086/TOC.2011.V007A003},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/AustrinKS11.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/BeigiSW11,
author = {Salman Beigi and
Peter W. Shor and
John Watrous},
title = {Quantum Interactive Proofs with Short Messages},
journal = {Theory Comput.},
volume = {7},
number = {1},
pages = {101--117},
year = {2011},
url = {https://doi.org/10.4086/toc.2011.v007a007},
doi = {10.4086/TOC.2011.V007A007},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/BeigiSW11.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/BhattacharyyaCSX11,
author = {Arnab Bhattacharyya and
Victor Chen and
Madhu Sudan and
Ning Xie},
title = {Testing Linear-Invariant Non-Linear Properties},
journal = {Theory Comput.},
volume = {7},
number = {1},
pages = {75--99},
year = {2011},
url = {https://doi.org/10.4086/toc.2011.v007a006},
doi = {10.4086/TOC.2011.V007A006},
timestamp = {Tue, 14 Jun 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/BhattacharyyaCSX11.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/DolevR11,
author = {Elya Dolev and
Dana Ron},
title = {Distribution-Free Testing for Monomials with a Sublinear Number of
Queries},
journal = {Theory Comput.},
volume = {7},
number = {1},
pages = {155--176},
year = {2011},
url = {https://doi.org/10.4086/toc.2011.v007a011},
doi = {10.4086/TOC.2011.V007A011},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/DolevR11.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/DruckerW11,
author = {Andrew Drucker and
Ronald de Wolf},
title = {Quantum Proofs for Classical Theorems},
journal = {Theory Comput.},
volume = {2},
pages = {1--54},
year = {2011},
url = {https://doi.org/10.4086/toc.gs.2011.002},
doi = {10.4086/TOC.GS.2011.002},
timestamp = {Wed, 22 Jul 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/DruckerW11.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/DvirS11,
author = {Zeev Dvir and
Amir Shpilka},
title = {Noisy Interpolating Sets for Low-Degree Polynomials},
journal = {Theory Comput.},
volume = {7},
number = {1},
pages = {1--18},
year = {2011},
url = {https://doi.org/10.4086/toc.2011.v007a001},
doi = {10.4086/TOC.2011.V007A001},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/DvirS11.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/HatamiKP11,
author = {Pooya Hatami and
Raghav Kulkarni and
Denis Pankratov},
title = {Variations on the Sensitivity Conjecture},
journal = {Theory Comput.},
volume = {4},
pages = {1--27},
year = {2011},
url = {https://doi.org/10.4086/toc.gs.2011.004},
doi = {10.4086/TOC.GS.2011.004},
timestamp = {Wed, 22 Jul 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/HatamiKP11.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/HrubesY11,
author = {Pavel Hrubes and
Amir Yehudayoff},
title = {Arithmetic Complexity in Ring Extensions},
journal = {Theory Comput.},
volume = {7},
number = {1},
pages = {119--129},
year = {2011},
url = {https://doi.org/10.4086/toc.2011.v007a008},
doi = {10.4086/TOC.2011.V007A008},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/HrubesY11.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/JainZ11,
author = {Rahul Jain and
Shengyu Zhang},
title = {The Influence Lower Bound Via Query Elimination},
journal = {Theory Comput.},
volume = {7},
number = {1},
pages = {147--153},
year = {2011},
url = {https://doi.org/10.4086/toc.2011.v007a010},
doi = {10.4086/TOC.2011.V007A010},
timestamp = {Thu, 01 Dec 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/toc/JainZ11.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/KrauthgamerR11,
author = {Robert Krauthgamer and
Tim Roughgarden},
title = {Metric Clustering via Consistent Labeling},
journal = {Theory Comput.},
volume = {7},
number = {1},
pages = {49--74},
year = {2011},
url = {https://doi.org/10.4086/toc.2011.v007a005},
doi = {10.4086/TOC.2011.V007A005},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/KrauthgamerR11.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/Lovett11,
author = {Shachar Lovett},
title = {Computing Polynomials with Few Multiplications},
journal = {Theory Comput.},
volume = {7},
number = {1},
pages = {185--188},
year = {2011},
url = {https://doi.org/10.4086/toc.2011.v007a013},
doi = {10.4086/TOC.2011.V007A013},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/Lovett11.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/LovettMS11,
author = {Shachar Lovett and
Roy Meshulam and
Alex Samorodnitsky},
title = {Inverse Conjecture for the Gowers Norm is False},
journal = {Theory Comput.},
volume = {7},
number = {1},
pages = {131--145},
year = {2011},
url = {https://doi.org/10.4086/toc.2011.v007a009},
doi = {10.4086/TOC.2011.V007A009},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/LovettMS11.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/Nayak11,
author = {Ashwin Nayak},
title = {Inverting a Permutation is as Hard as Unordered Search},
journal = {Theory Comput.},
volume = {7},
number = {1},
pages = {19--25},
year = {2011},
url = {https://doi.org/10.4086/toc.2011.v007a002},
doi = {10.4086/TOC.2011.V007A002},
timestamp = {Mon, 18 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/Nayak11.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/Viola11,
author = {Emanuele Viola},
title = {Selected Results in Additive Combinatorics: An Exposition},
journal = {Theory Comput.},
volume = {3},
pages = {1--15},
year = {2011},
url = {https://doi.org/10.4086/toc.gs.2011.003},
doi = {10.4086/TOC.GS.2011.003},
timestamp = {Wed, 22 Jul 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/Viola11.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/Ambainis10,
author = {Andris Ambainis},
title = {A New Quantum Lower Bound Method, with an Application to a Strong
Direct Product Theorem for Quantum Search},
journal = {Theory Comput.},
volume = {6},
number = {1},
pages = {1--25},
year = {2010},
url = {https://doi.org/10.4086/toc.2010.v006a001},
doi = {10.4086/TOC.2010.V006A001},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/Ambainis10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/BeameDPW10,
author = {Paul Beame and
Matei David and
Toniann Pitassi and
Philipp Woelfel},
title = {Separating Deterministic from Randomized Multiparty Communication
Complexity},
journal = {Theory Comput.},
volume = {6},
number = {1},
pages = {201--225},
year = {2010},
url = {https://doi.org/10.4086/toc.2010.v006a009},
doi = {10.4086/TOC.2010.V006A009},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/BeameDPW10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/Ben-AroyaST10,
author = {Avraham Ben{-}Aroya and
Oded Schwartz and
Amnon Ta{-}Shma},
title = {Quantum Expanders: Motivation and Construction},
journal = {Theory Comput.},
volume = {6},
number = {1},
pages = {47--79},
year = {2010},
url = {https://doi.org/10.4086/toc.2010.v006a003},
doi = {10.4086/TOC.2010.V006A003},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/Ben-AroyaST10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/BlumEL10,
author = {Avrim Blum and
Eyal Even{-}Dar and
Katrina Ligett},
title = {Routing Without Regret: On Convergence to Nash Equilibria of Regret-Minimizing
Algorithms in Routing Games},
journal = {Theory Comput.},
volume = {6},
number = {1},
pages = {179--199},
year = {2010},
url = {https://doi.org/10.4086/toc.2010.v006a008},
doi = {10.4086/TOC.2010.V006A008},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/BlumEL10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/DvirW10,
author = {Zeev Dvir and
Avi Wigderson},
title = {Monotone Expanders: Constructions and Applications},
journal = {Theory Comput.},
volume = {6},
number = {1},
pages = {291--308},
year = {2010},
url = {https://doi.org/10.4086/toc.2010.v006a012},
doi = {10.4086/TOC.2010.V006A012},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/DvirW10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/EnglertRW10,
author = {Matthias Englert and
Harald R{\"{a}}cke and
Matthias Westermann},
title = {Reordering Buffers for General Metric Spaces},
journal = {Theory Comput.},
volume = {6},
number = {1},
pages = {27--46},
year = {2010},
url = {https://doi.org/10.4086/toc.2010.v006a002},
doi = {10.4086/TOC.2010.V006A002},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/EnglertRW10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/FeigeV10,
author = {Uriel Feige and
Jan Vondr{\'{a}}k},
title = {The Submodular Welfare Problem with Demand Queries},
journal = {Theory Comput.},
volume = {6},
number = {1},
pages = {247--290},
year = {2010},
url = {https://doi.org/10.4086/toc.2010.v006a011},
doi = {10.4086/TOC.2010.V006A011},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/FeigeV10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/GavinskyS10,
author = {Dmitry Gavinsky and
Alexander A. Sherstov},
title = {A Separation of {NP} and coNP in Multiparty Communication Complexity},
journal = {Theory Comput.},
volume = {6},
number = {1},
pages = {227--245},
year = {2010},
url = {https://doi.org/10.4086/toc.2010.v006a010},
doi = {10.4086/TOC.2010.V006A010},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/GavinskyS10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/GoyalS10,
author = {Navin Goyal and
Michael E. Saks},
title = {Rounds vs. Queries Tradeoff in Noisy Computation},
journal = {Theory Comput.},
volume = {6},
number = {1},
pages = {113--134},
year = {2010},
url = {https://doi.org/10.4086/toc.2010.v006a006},
doi = {10.4086/TOC.2010.V006A006},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/GoyalS10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/Lee10,
author = {Homin K. Lee},
title = {Decision Trees and Influence: an Inductive Proof of the {OSSS} Inequality},
journal = {Theory Comput.},
volume = {6},
number = {1},
pages = {81--84},
year = {2010},
url = {https://doi.org/10.4086/toc.2010.v006a004},
doi = {10.4086/TOC.2010.V006A004},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/Lee10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/Marx10,
author = {D{\'{a}}niel Marx},
title = {Can You Beat Treewidth?},
journal = {Theory Comput.},
volume = {6},
number = {1},
pages = {85--112},
year = {2010},
url = {https://doi.org/10.4086/toc.2010.v006a005},
doi = {10.4086/TOC.2010.V006A005},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/Marx10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/Raz10,
author = {Ran Raz},
title = {Elusive Functions and Lower Bounds for Arithmetic Circuits},
journal = {Theory Comput.},
volume = {6},
number = {1},
pages = {135--177},
year = {2010},
url = {https://doi.org/10.4086/toc.2010.v006a007},
doi = {10.4086/TOC.2010.V006A007},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/Raz10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/AaronsonBDFS09,
author = {Scott Aaronson and
Salman Beigi and
Andrew Drucker and
Bill Fefferman and
Peter W. Shor},
title = {The Power of Unentanglement},
journal = {Theory Comput.},
volume = {5},
number = {1},
pages = {1--42},
year = {2009},
url = {https://doi.org/10.4086/toc.2009.v005a001},
doi = {10.4086/TOC.2009.V005A001},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/AaronsonBDFS09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/Ben-SassonV09,
author = {Eli Ben{-}Sasson and
Michael Viderman},
title = {Tensor Products of Weakly Smooth Codes are Robust},
journal = {Theory Comput.},
volume = {5},
number = {1},
pages = {239--255},
year = {2009},
url = {https://doi.org/10.4086/toc.2009.v005a012},
doi = {10.4086/TOC.2009.V005A012},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/Ben-SassonV09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/ChildsCJY09,
author = {Andrew M. Childs and
Richard Cleve and
Stephen P. Jordan and
David L. Yonge{-}Mallo},
title = {Discrete-Query Quantum Algorithm for {NAND} Trees},
journal = {Theory Comput.},
volume = {5},
number = {1},
pages = {119--123},
year = {2009},
url = {https://doi.org/10.4086/toc.2009.v005a005},
doi = {10.4086/TOC.2009.V005A005},
timestamp = {Tue, 21 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/toc/ChildsCJY09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/Dachman-SoledLMSWW09,
author = {Dana Dachman{-}Soled and
Homin K. Lee and
Tal Malkin and
Rocco A. Servedio and
Andrew Wan and
Hoeteck Wee},
title = {Optimal Cryptographic Hardness of Learning Monotone Functions},
journal = {Theory Comput.},
volume = {5},
number = {1},
pages = {257--282},
year = {2009},
url = {https://doi.org/10.4086/toc.2009.v005a013},
doi = {10.4086/TOC.2009.V005A013},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/Dachman-SoledLMSWW09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/Fortnow09,
author = {Lance Fortnow},
title = {A Simple Proof of Toda's Theorem},
journal = {Theory Comput.},
volume = {5},
number = {1},
pages = {135--140},
year = {2009},
url = {https://doi.org/10.4086/toc.2009.v005a007},
doi = {10.4086/TOC.2009.V005A007},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/Fortnow09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/GlasnerS09,
author = {Dana Glasner and
Rocco A. Servedio},
title = {Distribution-Free Testing Lower Bound for Basic Boolean Functions},
journal = {Theory Comput.},
volume = {5},
number = {1},
pages = {191--216},
year = {2009},
url = {https://doi.org/10.4086/toc.2009.v005a010},
doi = {10.4086/TOC.2009.V005A010},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/GlasnerS09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/Holenstein09,
author = {Thomas Holenstein},
title = {Parallel Repetition: Simplification and the No-Signaling Case},
journal = {Theory Comput.},
volume = {5},
number = {1},
pages = {141--172},
year = {2009},
url = {https://doi.org/10.4086/toc.2009.v005a008},
doi = {10.4086/TOC.2009.V005A008},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/Holenstein09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/KhotO09,
author = {Subhash Khot and
Ryan O'Donnell},
title = {{SDP} Gaps and UGC-hardness for Max-Cut-Gain},
journal = {Theory Comput.},
volume = {5},
number = {1},
pages = {83--117},
year = {2009},
url = {https://doi.org/10.4086/toc.2009.v005a004},
doi = {10.4086/TOC.2009.V005A004},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/KhotO09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/Lovett09,
author = {Shachar Lovett},
title = {Unconditional Pseudorandom Generators for Low Degree Polynomials},
journal = {Theory Comput.},
volume = {5},
number = {1},
pages = {69--82},
year = {2009},
url = {https://doi.org/10.4086/toc.2009.v005a003},
doi = {10.4086/TOC.2009.V005A003},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/Lovett09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/MoranNS09,
author = {Tal Moran and
Moni Naor and
Gil Segev},
title = {Deterministic History-Independent Strategies for Storing Information
on Write-Once Memories},
journal = {Theory Comput.},
volume = {5},
number = {1},
pages = {43--67},
year = {2009},
url = {https://doi.org/10.4086/toc.2009.v005a002},
doi = {10.4086/TOC.2009.V005A002},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/MoranNS09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/NewmanR09,
author = {Ilan Newman and
Yuri Rabinovich},
title = {Hard Metrics from Cayley Graphs of Abelian Groups},
journal = {Theory Comput.},
volume = {5},
number = {1},
pages = {125--134},
year = {2009},
url = {https://doi.org/10.4086/toc.2009.v005a006},
doi = {10.4086/TOC.2009.V005A006},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/NewmanR09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/VassilevskaWY09,
author = {Virginia Vassilevska and
Ryan Williams and
Raphael Yuster},
title = {All Pairs Bottleneck Paths and Max-Min Matrix Products in Truly Subcubic
Time},
journal = {Theory Comput.},
volume = {5},
number = {1},
pages = {173--189},
year = {2009},
url = {https://doi.org/10.4086/toc.2009.v005a009},
doi = {10.4086/TOC.2009.V005A009},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/VassilevskaWY09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/Watrous09,
author = {John Watrous},
title = {Semidefinite Programs for Completely Bounded Norms},
journal = {Theory Comput.},
volume = {5},
number = {1},
pages = {217--238},
year = {2009},
url = {https://doi.org/10.4086/toc.2009.v005a011},
doi = {10.4086/TOC.2009.V005A011},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/Watrous09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/Ajtai08,
author = {Mikl{\'{o}}s Ajtai},
title = {Optimal lower bounds for the Korkine-Zolotareff parameters of a lattice
and for Schnorr's algorithm for the shortest vector problem},
journal = {Theory Comput.},
volume = {4},
number = {1},
pages = {21--51},
year = {2008},
url = {https://doi.org/10.4086/toc.2008.v004a002},
doi = {10.4086/TOC.2008.V004A002},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/Ajtai08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/AnshelevichDTW08,
author = {Elliot Anshelevich and
Anirban Dasgupta and
{\'{E}}va Tardos and
Tom Wexler},
title = {Near-Optimal Network Design with Selfish Agents},
journal = {Theory Comput.},
volume = {4},
number = {1},
pages = {77--109},
year = {2008},
url = {https://doi.org/10.4086/toc.2008.v004a004},
doi = {10.4086/TOC.2008.V004A004},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/AnshelevichDTW08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/BruhnCHKS08,
author = {Henning Bruhn and
Jakub Cern{\'{y}} and
Alexander Hall and
Petr Kolman and
Jir{\'{\i}} Sgall},
title = {Single Source Multiroute Flows and Cuts on Uniform Capacity Networks},
journal = {Theory Comput.},
volume = {4},
number = {1},
pages = {1--20},
year = {2008},
url = {https://doi.org/10.4086/toc.2008.v004a001},
doi = {10.4086/TOC.2008.V004A001},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/BruhnCHKS08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/FarhiGG08,
author = {Edward Farhi and
Jeffrey Goldstone and
Sam Gutmann},
title = {A Quantum Algorithm for the Hamiltonian {NAND} Tree},
journal = {Theory Comput.},
volume = {4},
number = {1},
pages = {169--190},
year = {2008},
url = {https://doi.org/10.4086/toc.2008.v004a008},
doi = {10.4086/TOC.2008.V004A008},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/FarhiGG08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/JayramKS08,
author = {T. S. Jayram and
Ravi Kumar and
D. Sivakumar},
title = {The One-Way Communication Complexity of Hamming Distance},
journal = {Theory Comput.},
volume = {4},
number = {1},
pages = {129--135},
year = {2008},
url = {https://doi.org/10.4086/toc.2008.v004a006},
doi = {10.4086/TOC.2008.V004A006},
timestamp = {Mon, 08 Mar 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/toc/JayramKS08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/Nagarajan08,
author = {Viswanath Nagarajan},
title = {On the {LP} Relaxation of the Asymmetric Traveling Salesman Path Problem},
journal = {Theory Comput.},
volume = {4},
number = {1},
pages = {191--193},
year = {2008},
url = {https://doi.org/10.4086/toc.2008.v004a009},
doi = {10.4086/TOC.2008.V004A009},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/Nagarajan08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/Trevisan08,
author = {Luca Trevisan},
title = {Approximation Algorithms for Unique Games},
journal = {Theory Comput.},
volume = {4},
number = {1},
pages = {111--128},
year = {2008},
url = {https://doi.org/10.4086/toc.2008.v004a005},
doi = {10.4086/TOC.2008.V004A005},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/Trevisan08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/ViolaW08,
author = {Emanuele Viola and
Avi Wigderson},
title = {Norms, {XOR} Lemmas, and Lower Bounds for Polynomials and Protocols},
journal = {Theory Comput.},
volume = {4},
number = {1},
pages = {137--168},
year = {2008},
url = {https://doi.org/10.4086/toc.2008.v004a007},
doi = {10.4086/TOC.2008.V004A007},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/ViolaW08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/WigdersonX08,
author = {Avi Wigderson and
David Xiao},
title = {Derandomizing the Ahlswede-Winter matrix-valued Chernoff bound using
pessimistic estimators, and applications},
journal = {Theory Comput.},
volume = {4},
number = {1},
pages = {53--76},
year = {2008},
url = {https://doi.org/10.4086/toc.2008.v004a003},
doi = {10.4086/TOC.2008.V004A003},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/WigdersonX08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/Wolf08,
author = {Ronald de Wolf},
title = {A Brief Introduction to Fourier Analysis on the Boolean Cube},
journal = {Theory Comput.},
volume = {1},
pages = {1--20},
year = {2008},
url = {https://doi.org/10.4086/toc.gs.2008.001},
doi = {10.4086/TOC.GS.2008.001},
timestamp = {Wed, 22 Jul 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/Wolf08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/AaronsonK07,
author = {Scott Aaronson and
Greg Kuperberg},
title = {Quantum Versus Classical Proofs and Advice},
journal = {Theory Comput.},
volume = {3},
number = {1},
pages = {129--157},
year = {2007},
url = {https://doi.org/10.4086/toc.2007.v003a007},
doi = {10.4086/TOC.2007.V003A007},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/AaronsonK07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/AlekhnovichJPU07,
author = {Michael Alekhnovich and
Jan Johannsen and
Toniann Pitassi and
Alasdair Urquhart},
title = {An Exponential Separation between Regular and General Resolution},
journal = {Theory Comput.},
volume = {3},
number = {1},
pages = {81--102},
year = {2007},
url = {https://doi.org/10.4086/toc.2007.v003a005},
doi = {10.4086/TOC.2007.V003A005},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/AlekhnovichJPU07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/BalcanB07,
author = {Maria{-}Florina Balcan and
Avrim Blum},
title = {Approximation Algorithms and Online Mechanisms for Item Pricing},
journal = {Theory Comput.},
volume = {3},
number = {1},
pages = {179--195},
year = {2007},
url = {https://doi.org/10.4086/toc.2007.v003a009},
doi = {10.4086/TOC.2007.V003A009},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/BalcanB07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/ChekuriP07,
author = {Chandra Chekuri and
Martin P{\'{a}}l},
title = {An O(log \emph{n}) Approximation Ratio for the Asymmetric Traveling
Salesman Path Problem},
journal = {Theory Comput.},
volume = {3},
number = {1},
pages = {197--209},
year = {2007},
url = {https://doi.org/10.4086/toc.2007.v003a010},
doi = {10.4086/TOC.2007.V003A010},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/ChekuriP07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/FeigeO07,
author = {Uriel Feige and
Eran Ofek},
title = {Easily refutable subformulas of large random 3CNF formulas},
journal = {Theory Comput.},
volume = {3},
number = {1},
pages = {25--43},
year = {2007},
url = {https://doi.org/10.4086/toc.2007.v003a002},
doi = {10.4086/TOC.2007.V003A002},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/FeigeO07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/FiatS07,
author = {Amos Fiat and
Jared Saia},
title = {Censorship Resistant Peer-to-Peer Networks},
journal = {Theory Comput.},
volume = {3},
number = {1},
pages = {1--23},
year = {2007},
url = {https://doi.org/10.4086/toc.2007.v003a001},
doi = {10.4086/TOC.2007.V003A001},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/FiatS07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/HastadW07,
author = {Johan H{\aa}stad and
Avi Wigderson},
title = {The Randomized Communication Complexity of Set Disjointness},
journal = {Theory Comput.},
volume = {3},
number = {1},
pages = {211--219},
year = {2007},
url = {https://doi.org/10.4086/toc.2007.v003a011},
doi = {10.4086/TOC.2007.V003A011},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/HastadW07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/HavivRT07,
author = {Ishay Haviv and
Oded Regev and
Amnon Ta{-}Shma},
title = {On the Hardness of Satisfiability with Bounded Occurrences in the
Polynomial-Time Hierarchy},
journal = {Theory Comput.},
volume = {3},
number = {1},
pages = {45--60},
year = {2007},
url = {https://doi.org/10.4086/toc.2007.v003a003},
doi = {10.4086/TOC.2007.V003A003},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/HavivRT07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/JanzingW07,
author = {Dominik Janzing and
Pawel Wocjan},
title = {A Simple PromiseBQP-complete Matrix Problem},
journal = {Theory Comput.},
volume = {3},
number = {1},
pages = {61--79},
year = {2007},
url = {https://doi.org/10.4086/toc.2007.v003a004},
doi = {10.4086/TOC.2007.V003A004},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/JanzingW07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/MatousekS07,
author = {Jir{\'{\i}} Matousek and
Petr Skovron},
title = {Removing Degeneracy May Require a Large Dimension Increase},
journal = {Theory Comput.},
volume = {3},
number = {1},
pages = {159--177},
year = {2007},
url = {https://doi.org/10.4086/toc.2007.v003a008},
doi = {10.4086/TOC.2007.V003A008},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/MatousekS07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/RazborovY07,
author = {Alexander A. Razborov and
Sergey Yekhanin},
title = {An Omega(\emph{n}\({}^{\mbox{1/3}}\)) Lower Bound for Bilinear Group
Based Private Information Retrieval},
journal = {Theory Comput.},
volume = {3},
number = {1},
pages = {221--238},
year = {2007},
url = {https://doi.org/10.4086/toc.2007.v003a012},
doi = {10.4086/TOC.2007.V003A012},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/RazborovY07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/Zuckerman07,
author = {David Zuckerman},
title = {Linear Degree Extractors and the Inapproximability of Max Clique and
Chromatic Number},
journal = {Theory Comput.},
volume = {3},
number = {1},
pages = {103--128},
year = {2007},
url = {https://doi.org/10.4086/toc.2007.v003a006},
doi = {10.4086/TOC.2007.V003A006},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/Zuckerman07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/AroraBLT06,
author = {Sanjeev Arora and
B{\'{e}}la Bollob{\'{a}}s and
L{\'{a}}szl{\'{o}} Lov{\'{a}}sz and
Iannis Tourlakis},
title = {Proving Integrality Gaps without Knowing the Linear Program},
journal = {Theory Comput.},
volume = {2},
number = {2},
pages = {19--51},
year = {2006},
url = {https://doi.org/10.4086/toc.2006.v002a002},
doi = {10.4086/TOC.2006.V002A002},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/AroraBLT06.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/Buresh-OppenheimGHMP06,
author = {Joshua Buresh{-}Oppenheim and
Nicola Galesi and
Shlomo Hoory and
Avner Magen and
Toniann Pitassi},
title = {Rank Bounds and Integrality Gaps for Cutting Planes Procedures},
journal = {Theory Comput.},
volume = {2},
number = {4},
pages = {65--90},
year = {2006},
url = {https://doi.org/10.4086/toc.2006.v002a004},
doi = {10.4086/TOC.2006.V002A004},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/Buresh-OppenheimGHMP06.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/CharikarK06,
author = {Moses Charikar and
Robert Krauthgamer},
title = {Embedding the Ulam metric into \emph{l}\({}_{\mbox{1}}\)},
journal = {Theory Comput.},
volume = {2},
number = {11},
pages = {207--224},
year = {2006},
url = {https://doi.org/10.4086/toc.2006.v002a011},
doi = {10.4086/TOC.2006.V002A011},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/CharikarK06.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/ChekuriKS06,
author = {Chandra Chekuri and
Sanjeev Khanna and
F. Bruce Shepherd},
title = {An O(sqrt(n)) Approximation and Integrality Gap for Disjoint Paths
and Unsplittable Flow},
journal = {Theory Comput.},
volume = {2},
number = {7},
pages = {137--146},
year = {2006},
url = {https://doi.org/10.4086/toc.2006.v002a007},
doi = {10.4086/TOC.2006.V002A007},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/ChekuriKS06.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/DeshpandeRVW06,
author = {Amit Deshpande and
Luis Rademacher and
Santosh S. Vempala and
Grant Wang},
title = {Matrix Approximation and Projective Clustering via Volume Sampling},
journal = {Theory Comput.},
volume = {2},
number = {12},
pages = {225--247},
year = {2006},
url = {https://doi.org/10.4086/toc.2006.v002a012},
doi = {10.4086/TOC.2006.V002A012},
timestamp = {Thu, 14 Oct 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/DeshpandeRVW06.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/FischerF06,
author = {Eldar Fischer and
Lance Fortnow},
title = {Tolerant Versus Intolerant Testing for Boolean Properties},
journal = {Theory Comput.},
volume = {2},
number = {9},
pages = {173--183},
year = {2006},
url = {https://doi.org/10.4086/toc.2006.v002a009},
doi = {10.4086/TOC.2006.V002A009},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/FischerF06.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/GiotisG06,
author = {Ioannis Giotis and
Venkatesan Guruswami},
title = {Correlation Clustering with a Fixed Number of Clusters},
journal = {Theory Comput.},
volume = {2},
number = {13},
pages = {249--266},
year = {2006},
url = {https://doi.org/10.4086/toc.2006.v002a013},
doi = {10.4086/TOC.2006.V002A013},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/GiotisG06.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/GuptaS06,
author = {Anupam Gupta and
Aravind Srinivasan},
title = {An Improved Approximation Ratio for the Covering Steiner Problem},
journal = {Theory Comput.},
volume = {2},
number = {3},
pages = {53--64},
year = {2006},
url = {https://doi.org/10.4086/toc.2006.v002a003},
doi = {10.4086/TOC.2006.V002A003},
timestamp = {Wed, 18 Aug 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/GuptaS06.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/JacksonS06,
author = {Jeffrey C. Jackson and
Rocco A. Servedio},
title = {On Learning Random {DNF} Formulas Under the Uniform Distribution},
journal = {Theory Comput.},
volume = {2},
number = {8},
pages = {147--172},
year = {2006},
url = {https://doi.org/10.4086/toc.2006.v002a008},
doi = {10.4086/TOC.2006.V002A008},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/JacksonS06.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/KlivansS06,
author = {Adam R. Klivans and
Amir Shpilka},
title = {Learning Restricted Models of Arithmetic Circuits},
journal = {Theory Comput.},
volume = {2},
number = {10},
pages = {185--206},
year = {2006},
url = {https://doi.org/10.4086/toc.2006.v002a010},
doi = {10.4086/TOC.2006.V002A010},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/KlivansS06.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/Raz06,
author = {Ran Raz},
title = {Separation of Multilinear Circuit and Formula Size},
journal = {Theory Comput.},
volume = {2},
number = {6},
pages = {121--135},
year = {2006},
url = {https://doi.org/10.4086/toc.2006.v002a006},
doi = {10.4086/TOC.2006.V002A006},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/Raz06.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/RozenmanSW06,
author = {Eyal Rozenman and
Aner Shalev and
Avi Wigderson},
title = {Iterative Construction of Cayley Expander Graphs},
journal = {Theory Comput.},
volume = {2},
number = {5},
pages = {91--120},
year = {2006},
url = {https://doi.org/10.4086/toc.2006.v002a005},
doi = {10.4086/TOC.2006.V002A005},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/RozenmanSW06.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/SpalekS06,
author = {Robert Spalek and
Mario Szegedy},
title = {All Quantum Adversary Methods are Equivalent},
journal = {Theory Comput.},
volume = {2},
number = {1},
pages = {1--18},
year = {2006},
url = {https://doi.org/10.4086/toc.2006.v002a001},
doi = {10.4086/TOC.2006.V002A001},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/SpalekS06.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/Aaronson05,
author = {Scott Aaronson},
title = {Limitations of Quantum Advice and One-Way Communication},
journal = {Theory Comput.},
volume = {1},
number = {1},
pages = {1--28},
year = {2005},
url = {https://doi.org/10.4086/toc.2005.v001a001},
doi = {10.4086/TOC.2005.V001A001},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/Aaronson05.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/AaronsonA05,
author = {Scott Aaronson and
Andris Ambainis},
title = {Quantum Search of Spatial Regions},
journal = {Theory Comput.},
volume = {1},
number = {1},
pages = {47--79},
year = {2005},
url = {https://doi.org/10.4086/toc.2005.v001a004},
doi = {10.4086/TOC.2005.V001A004},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/AaronsonA05.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/Ajtai05,
author = {Mikl{\'{o}}s Ajtai},
title = {A Non-linear Time Lower Bound for Boolean Branching Programs},
journal = {Theory Comput.},
volume = {1},
number = {1},
pages = {149--176},
year = {2005},
url = {https://doi.org/10.4086/toc.2005.v001a008},
doi = {10.4086/TOC.2005.V001A008},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/Ajtai05.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/AlonS05,
author = {Noga Alon and
Asaf Shapira},
title = {Linear Equations, Arithmetic Progressions and Hypergraph Property
Testing},
journal = {Theory Comput.},
volume = {1},
number = {1},
pages = {177--216},
year = {2005},
url = {https://doi.org/10.4086/toc.2005.v001a009},
doi = {10.4086/TOC.2005.V001A009},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/AlonS05.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/Ambainis05,
author = {Andris Ambainis},
title = {Polynomial Degree and Lower Bounds in Quantum Complexity: Collision
and Element Distinctness with Small Range},
journal = {Theory Comput.},
volume = {1},
number = {1},
pages = {37--46},
year = {2005},
url = {https://doi.org/10.4086/toc.2005.v001a003},
doi = {10.4086/TOC.2005.V001A003},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/Ambainis05.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/AzarBBM05,
author = {Yossi Azar and
Avrim Blum and
David P. Bunde and
Yishay Mansour},
title = {Combining Online Algorithms for Acceptance and Rejection},
journal = {Theory Comput.},
volume = {1},
number = {1},
pages = {105--117},
year = {2005},
url = {https://doi.org/10.4086/toc.2005.v001a006},
doi = {10.4086/TOC.2005.V001A006},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/AzarBBM05.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/HastadK05,
author = {Johan H{\aa}stad and
Subhash Khot},
title = {Query Efficient PCPs with Perfect Completeness},
journal = {Theory Comput.},
volume = {1},
number = {1},
pages = {119--148},
year = {2005},
url = {https://doi.org/10.4086/toc.2005.v001a007},
doi = {10.4086/TOC.2005.V001A007},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/HastadK05.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/HoyerS05,
author = {Peter H{\o}yer and
Robert Spalek},
title = {Quantum Fan-out is Powerful},
journal = {Theory Comput.},
volume = {1},
number = {1},
pages = {81--103},
year = {2005},
url = {https://doi.org/10.4086/toc.2005.v001a005},
doi = {10.4086/TOC.2005.V001A005},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/HoyerS05.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/Kutin05,
author = {Samuel Kutin},
title = {Quantum Lower Bound for the Collision Problem with Small Range},
journal = {Theory Comput.},
volume = {1},
number = {1},
pages = {29--36},
year = {2005},
url = {https://doi.org/10.4086/toc.2005.v001a002},
doi = {10.4086/TOC.2005.V001A002},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/Kutin05.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-07-31 06:37 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:
