Stop the war!Остановите войну!
for scientists:
default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDSearch dblp for Publications
export results for "toc:db/journals/eccc/eccc19.bht:"
download as .bib file
@article{DBLP:journals/eccc/AaronsonC12,
author = {Scott Aaronson and
Paul F. Christiano},
title = {Quantum Money from Hidden Subspaces},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-024}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/024},
eprinttype = {ECCC},
eprint = {TR12-024},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/AaronsonC12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/AaronsonH12,
author = {Scott Aaronson and
Travis Hance},
title = {Generalizing and Derandomizing Gurvits's Approximation Algorithm for
the Permanent},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-170}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/170},
eprinttype = {ECCC},
eprint = {TR12-170},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/AaronsonH12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/AfshaniADCLM12,
author = {Peyman Afshani and
Manindra Agrawal and
Benjamin Doerr and
Carola Winzen and
Kasper Green Larsen and
Kurt Mehlhorn},
title = {The Deterministic and Randomized Query Complexity of a Simple Guessing
Game},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-087}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/087},
eprinttype = {ECCC},
eprint = {TR12-087},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/AfshaniADCLM12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/AgrawalSS12,
author = {Manindra Agrawal and
Chandan Saha and
Nitin Saxena},
title = {Quasi-polynomial Hitting-set for Set-depth-{\textdollar}{\textbackslash}Delta{\textdollar}
Formulas},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-113}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/113},
eprinttype = {ECCC},
eprint = {TR12-113},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/AgrawalSS12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/AiDSW12,
author = {Albert Ai and
Zeev Dvir and
Shubhangi Saraf and
Avi Wigderson},
title = {Sylvester-Gallai type theorems for approximate collinearity},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-139}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/139},
eprinttype = {ECCC},
eprint = {TR12-139},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/AiDSW12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/AlbrechtFFHP12,
author = {Martin R. Albrecht and
Pooya Farshim and
Jean{-}Charles Faug{\`{e}}re and
Gottfried Herold and
Ludovic Perret},
title = {Polly Cracker, Revisited},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-165}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/165},
eprinttype = {ECCC},
eprint = {TR12-165},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/AlbrechtFFHP12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/AllenderBFL12,
author = {Eric Allender and
Harry Buhrman and
Luke Friedman and
Bruno Loff},
title = {Reductions to the set of random strings: the resource-bounded case},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-054}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/054},
eprinttype = {ECCC},
eprint = {TR12-054},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/AllenderBFL12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/AllenderCLPT12,
author = {Eric Allender and
Shiteng Chen and
Tiancheng Lou and
Periklis A. Papakonstantinou and
Bangsheng Tang},
title = {Time-space tradeoffs for width-parameterized {SAT:} Algorithms and
lower bounds},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-027}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/027},
eprinttype = {ECCC},
eprint = {TR12-027},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/AllenderCLPT12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/AllenderDFHT12,
author = {Eric Allender and
George Davie and
Luke Friedman and
Samuel Hopkins and
Iddo Tzameret},
title = {Kolmogorov Complexity, Circuits, and the Strength of Formal Theories
of Arithmetic},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-028}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/028},
eprinttype = {ECCC},
eprint = {TR12-028},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/AllenderDFHT12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/AlonC12,
author = {Noga Alon and
Gil Cohen},
title = {On Rigid Matrices and Subspace Polynomials},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-133}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/133},
eprinttype = {ECCC},
eprint = {TR12-133},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/AlonC12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/AlonV12,
author = {Noga Alon and
Santosh S. Vempala},
title = {The Approximate Rank of a Matrix and its Algorithmic Applications},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-169}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/169},
eprinttype = {ECCC},
eprint = {TR12-169},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/AlonV12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/Anokhin12,
author = {Mikhail Anokhin},
title = {Constructing a Pseudo-Free Family of Finite Computational Groups under
the General Integer Factoring Intractability Assumption},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-114}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/114},
eprinttype = {ECCC},
eprint = {TR12-114},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/Anokhin12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ApplebaumIK12,
author = {Benny Applebaum and
Yuval Ishai and
Eyal Kushilevitz},
title = {How to Garble Arithmetic Circuits},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-058}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/058},
eprinttype = {ECCC},
eprint = {TR12-058},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ApplebaumIK12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/AroraBMS12,
author = {Sanjeev Arora and
Arnab Bhattacharyya and
Rajsekar Manokaran and
Sushant Sachdeva},
title = {Testing Permanent Oracles - Revisited},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-094}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/094},
eprinttype = {ECCC},
eprint = {TR12-094},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/AroraBMS12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/AroraIKS12,
author = {Manuel Arora and
G{\'{a}}bor Ivanyos and
Marek Karpinski and
Nitin Saxena},
title = {Deterministic Polynomial Factoring and Association Schemes},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-068}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/068},
eprinttype = {ECCC},
eprint = {TR12-068},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/AroraIKS12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ArvindKKV12,
author = {Vikraman Arvind and
Sebastian Kuhnert and
Johannes K{\"{o}}bler and
Yadu Vasudev},
title = {Approximate Graph Isomorphism},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-078}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/078},
eprinttype = {ECCC},
eprint = {TR12-078},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ArvindKKV12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/AtseriasD12,
author = {Albert Atserias and
Anuj Dawar},
title = {Degree Lower Bounds of Tower-Type for Approximating Formulas with
Parity Quantifiers},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-015}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/015},
eprinttype = {ECCC},
eprint = {TR12-015},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/AtseriasD12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/AtseriasO12,
author = {Albert Atserias and
Sergi Oliva},
title = {Bounded-width {QBF} is PSPACE-complete},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-096}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/096},
eprinttype = {ECCC},
eprint = {TR12-096},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/AtseriasO12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/AusielloCL12,
author = {Giorgio Ausiello and
Francesco Cristiano and
Luigi Laura},
title = {Syntactic Isomorphism of {CNF} Boolean Formulas is Graph Isomorphism
Complete},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-122}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/122},
eprinttype = {ECCC},
eprint = {TR12-122},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/AusielloCL12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/AwasthiJMR12,
author = {Pranjal Awasthi and
Madhav Jha and
Marco Molinaro and
Sofya Raskhodnikova},
title = {Limitations of Local Filters of Lipschitz and Monotone Functions},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-075}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/075},
eprinttype = {ECCC},
eprint = {TR12-075},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/AwasthiJMR12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/AwasthiJMR12a,
author = {Pranjal Awasthi and
Madhav Jha and
Marco Molinaro and
Sofya Raskhodnikova},
title = {Testing Lipschitz Functions on Hypergrid Domains},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-076}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/076},
eprinttype = {ECCC},
eprint = {TR12-076},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/AwasthiJMR12a.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/AydinliogluM12,
author = {Baris Aydinlioglu and
Dieter van Melkebeek},
title = {Nondeterministic Circuit Lower Bounds from Mildly Derandomizing Arthur-Merlin
Games},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-080}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/080},
eprinttype = {ECCC},
eprint = {TR12-080},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/AydinliogluM12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/Barak12,
author = {Boaz Barak},
title = {Proof vs. Truth in Computational Complexity},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-120}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/120},
eprinttype = {ECCC},
eprint = {TR12-120},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/Barak12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/BarhumH12,
author = {Kfir Barhum and
Thomas Holenstein},
title = {A Cookbook for Black-Box Separations and a Recipe for UOWHFs},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-173}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/173},
eprinttype = {ECCC},
eprint = {TR12-173},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/BarhumH12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/BeameCM12,
author = {Paul Beame and
Rapha{\"{e}}l Clifford and
Widad Machmouchi},
title = {Sliding Windows With Limited Storage},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-178}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/178},
eprinttype = {ECCC},
eprint = {TR12-178},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/BeameCM12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/BeckIL12,
author = {Chris Beck and
Russell Impagliazzo and
Shachar Lovett},
title = {Large Deviation Bounds for Decision Trees and Sampling Lower Bounds
for AC0-circuits},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-042}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/042},
eprinttype = {ECCC},
eprint = {TR12-042},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/BeckIL12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/BeiCZ12,
author = {Xiaohui Bei and
Ning Chen and
Shengyu Zhang},
title = {On the Complexity of Trial and Error},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-067}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/067},
eprinttype = {ECCC},
eprint = {TR12-067},
timestamp = {Thu, 01 Dec 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/eccc/BeiCZ12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/Ben-AroyaC12,
author = {Avraham Ben{-}Aroya and
Gil Cohen},
title = {Gradual Small-Bias Sample Spaces},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-050}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/050},
eprinttype = {ECCC},
eprint = {TR12-050},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/Ben-AroyaC12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/Ben-AroyaS12,
author = {Avraham Ben{-}Aroya and
Igor Shinkar},
title = {A Note on Subspace Evasive Sets},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-095}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/095},
eprinttype = {ECCC},
eprint = {TR12-095},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/Ben-AroyaS12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/Ben-SassonCGT12,
author = {Eli Ben{-}Sasson and
Alessandro Chiesa and
Daniel Genkin and
Eran Tromer},
title = {On the Concrete-Efficiency Threshold of Probabilistically-Checkable
Proofs},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-045}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/045},
eprinttype = {ECCC},
eprint = {TR12-045},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/Ben-SassonCGT12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/Ben-SassonGKKS12,
author = {Eli Ben{-}Sasson and
Ariel Gabizon and
Yohay Kaplan and
Swastik Kopparty and
Shubhangi Saraf},
title = {A new family of locally correctable codes based on degree-lifted algebraic
geometry codes},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-148}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/148},
eprinttype = {ECCC},
eprint = {TR12-148},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/Ben-SassonGKKS12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/Ben-SassonRS12,
author = {Eli Ben{-}Sasson and
Noga Ron{-}Zewi and
Madhu Sudan},
title = {Sparse affine-invariant linear codes are locally testable},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-049}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/049},
eprinttype = {ECCC},
eprint = {TR12-049},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/Ben-SassonRS12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/Ben-SassonRTW12,
author = {Eli Ben{-}Sasson and
Noga Ron{-}Zewi and
Madhur Tulsiani and
Julia Wolf},
title = {Sampling-based proofs of almost-periodicity results and algorithmic
applications},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-135}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/135},
eprinttype = {ECCC},
eprint = {TR12-135},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/Ben-SassonRTW12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/Ben-SassonV12,
author = {Eli Ben{-}Sasson and
Michael Viderman},
title = {A Combinatorial Characterization of smooth LTCs and Applications},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-159}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/159},
eprinttype = {ECCC},
eprint = {TR12-159},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/Ben-SassonV12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/BermanHKN12,
author = {Itay Berman and
Iftach Haitner and
Ilan Komargodski and
Moni Naor},
title = {Hardness Preserving Reductions via Cuckoo Hashing},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-182}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/182},
eprinttype = {ECCC},
eprint = {TR12-182},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/BermanHKN12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/BeyersdorffDKMSSTV12,
author = {Olaf Beyersdorff and
Samir Datta and
Andreas Krebs and
Meena Mahajan and
Gido Scharfenberger{-}Fabian and
Karteek Sreenivasaiah and
Michael Thomas and
Heribert Vollmer},
title = {Verifying Proofs in Constant Depth},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-079}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/079},
eprinttype = {ECCC},
eprint = {TR12-079},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/BeyersdorffDKMSSTV12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/BeyersdorffGL12,
author = {Olaf Beyersdorff and
Nicola Galesi and
Massimo Lauria},
title = {A Characterization of Tree-Like Resolution Size},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-161}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/161},
eprinttype = {ECCC},
eprint = {TR12-161},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/BeyersdorffGL12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/BhaskaraDS12,
author = {Aditya Bhaskara and
Devendra Desai and
Srikanth Srinivasan},
title = {Optimal Hitting Sets for Combinatorial Shapes},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-158}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/158},
eprinttype = {ECCC},
eprint = {TR12-158},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/BhaskaraDS12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/BhattacharyyaFHHL12,
author = {Arnab Bhattacharyya and
Eldar Fischer and
Hamed Hatami and
Pooya Hatami and
Shachar Lovett},
title = {Every locally characterized affine-invariant property is testable},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-184}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/184},
eprinttype = {ECCC},
eprint = {TR12-184},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/BhattacharyyaFHHL12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/BhattacharyyaFL12,
author = {Arnab Bhattacharyya and
Eldar Fischer and
Shachar Lovett},
title = {Testing Low Complexity Affine-Invariant Properties},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-001}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/001},
eprinttype = {ECCC},
eprint = {TR12-001},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/BhattacharyyaFL12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/BhattacharyyaY12,
author = {Arnab Bhattacharyya and
Yuichi Yoshida},
title = {Testing Assignments of Boolean CSPs},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-103}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/103},
eprinttype = {ECCC},
eprint = {TR12-103},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/BhattacharyyaY12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/BhowmickDL12,
author = {Abhishek Bhowmick and
Zeev Dvir and
Shachar Lovett},
title = {New Lower Bounds for Matching Vector Codes},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-034}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/034},
eprinttype = {ECCC},
eprint = {TR12-034},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/BhowmickDL12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/Blaser12,
author = {Markus Bl{\"{a}}ser},
title = {Noncommutativity makes determinants hard},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-142}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/142},
eprinttype = {ECCC},
eprint = {TR12-142},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/Blaser12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/BlondinKM12,
author = {Michael Blondin and
Andreas Krebs and
Pierre McKenzie},
title = {The Complexity of Intersecting Finite Automata Having Few Final States},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-090}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/090},
eprinttype = {ECCC},
eprint = {TR12-090},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/BlondinKM12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/BockenhauerHKKSS12,
author = {Hans{-}Joachim B{\"{o}}ckenhauer and
Juraj Hromkovic and
Dennis Komm and
Sacha Krug and
Jasmin Smula and
Andreas Sprock},
title = {The String Guessing Problem as a Method to Prove Lower Bounds on the
Advice Complexity},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-162}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/162},
eprinttype = {ECCC},
eprint = {TR12-162},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/BockenhauerHKKSS12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/BogdanovG12,
author = {Andrej Bogdanov and
Siyao Guo},
title = {Sparse extractor families for all the entropy},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-097}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/097},
eprinttype = {ECCC},
eprint = {TR12-097},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/BogdanovG12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/BogdanovL12,
author = {Andrej Bogdanov and
Chin Ho Lee},
title = {Limits of provable security for homomorphic encryption},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-156}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/156},
eprinttype = {ECCC},
eprint = {TR12-156},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/BogdanovL12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/BogdanovL12a,
author = {Andrej Bogdanov and
Chin Ho Lee},
title = {On the depth complexity of homomorphic encryption schemes},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-157}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/157},
eprinttype = {ECCC},
eprint = {TR12-157},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/BogdanovL12a.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/BonacinaG12,
author = {Ilario Bonacina and
Nicola Galesi},
title = {Pseudo-partitions, Transversality and Locality: {A} Combinatorial
Characterization for the Space Measure in Algebraic Proof Systems},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-119}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/119},
eprinttype = {ECCC},
eprint = {TR12-119},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/BonacinaG12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/BonehZ12,
author = {Dan Boneh and
Mark Zhandry},
title = {Quantum-Secure Message Authentication Codes},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-136}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/136},
eprinttype = {ECCC},
eprint = {TR12-136},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/BonehZ12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/Boppana12,
author = {Meena Boppana},
title = {Lattice Variant of the Sensitivity Conjecture},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-089}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/089},
eprinttype = {ECCC},
eprint = {TR12-089},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/Boppana12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/BrakerskiK12,
author = {Zvika Brakerski and
Yael Tauman Kalai},
title = {Efficient Interactive Coding Against Adversarial Noise},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-043}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/043},
eprinttype = {ECCC},
eprint = {TR12-043},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/BrakerskiK12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/BravermanGPW12,
author = {Mark Braverman and
Ankit Garg and
Denis Pankratov and
Omri Weinstein},
title = {From Information to Exact Communication},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-171}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/171},
eprinttype = {ECCC},
eprint = {TR12-171},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/BravermanGPW12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/BravermanGPW12a,
author = {Mark Braverman and
Ankit Garg and
Denis Pankratov and
Omri Weinstein},
title = {Information lower bounds via self-reducibility},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-177}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/177},
eprinttype = {ECCC},
eprint = {TR12-177},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/BravermanGPW12a.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/BravermanM12,
author = {Mark Braverman and
Ankur Moitra},
title = {An Information Complexity Approach to Extended Formulations},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-131}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/131},
eprinttype = {ECCC},
eprint = {TR12-131},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/BravermanM12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/BravermanRWY12,
author = {Mark Braverman and
Anup Rao and
Omri Weinstein and
Amir Yehudayoff},
title = {Direct Products in Communication Complexity},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-143}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/143},
eprinttype = {ECCC},
eprint = {TR12-143},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/BravermanRWY12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/BrodyBKLS12,
author = {Joshua Brody and
Harry Buhrman and
Michal Kouck{\'{y}} and
Bruno Loff and
Florian Speelman},
title = {Towards a Reverse Newman's Theorem in Interactive Information Complexity},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-179}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/179},
eprinttype = {ECCC},
eprint = {TR12-179},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/BrodyBKLS12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/BrodyCK12,
author = {Joshua Brody and
Amit Chakrabarti and
Ranganath Kondapally},
title = {Certifying Equality With Limited Interaction},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-153}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/153},
eprinttype = {ECCC},
eprint = {TR12-153},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/BrodyCK12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/Bshouty12,
author = {Nader H. Bshouty},
title = {Testers and their Applications},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-011}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/011},
eprinttype = {ECCC},
eprint = {TR12-011},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/Bshouty12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/CanonneRS12,
author = {Cl{\'{e}}ment L. Canonne and
Dana Ron and
Rocco A. Servedio},
title = {Testing probability distributions using conditional samples},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-155}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/155},
eprinttype = {ECCC},
eprint = {TR12-155},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/CanonneRS12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ChakrabartiCMT12,
author = {Amit Chakrabarti and
Graham Cormode and
Andrew McGregor and
Justin Thaler},
title = {Annotations in Data Streams},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-022}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/022},
eprinttype = {ECCC},
eprint = {TR12-022},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ChakrabartiCMT12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ChakrabartyS12,
author = {Deeparnab Chakrabarty and
C. Seshadhri},
title = {Optimal bounds for monotonicity and Lipschitz testing over the hypercube},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-030}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/030},
eprinttype = {ECCC},
eprint = {TR12-030},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ChakrabartyS12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ChakrabortyFGM12,
author = {Sourav Chakraborty and
Eldar Fischer and
Yonatan Goldhirsh and
Arie Matsliah},
title = {On the Power of Conditional Samples in Distribution Testing},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-154}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/154},
eprinttype = {ECCC},
eprint = {TR12-154},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ChakrabortyFGM12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ChakrabortyS12,
author = {Chiranjit Chakraborty and
Rahul Santhanam},
title = {Instance Compression for the Polynomial Hierarchy and Beyond},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-077}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/077},
eprinttype = {ECCC},
eprint = {TR12-077},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ChakrabortyS12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/Chan12,
author = {Siu On Chan},
title = {Approximation Resistance from Pairwise Independent Subgroups},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-110}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/110},
eprinttype = {ECCC},
eprint = {TR12-110},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/Chan12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ChanP12,
author = {Siu Man Chan and
Aaron Potechin},
title = {Tight Bounds for Monotone Switching Networks via Fourier Analysis},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-185}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/185},
eprinttype = {ECCC},
eprint = {TR12-185},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ChanP12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ChattopadhyayKK12,
author = {Eshan Chattopadhyay and
Adam R. Klivans and
Pravesh Kothari},
title = {An Explicit VC-Theorem for Low-Degree Polynomials},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-127}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/127},
eprinttype = {ECCC},
eprint = {TR12-127},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ChattopadhyayKK12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ChattopadhyayS12,
author = {Arkadev Chattopadhyay and
Rahul Santhanam},
title = {Lower Bounds on Interactive Compressibility by Constant-Depth Circuits},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-108}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/108},
eprinttype = {ECCC},
eprint = {TR12-108},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ChattopadhyayS12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ChenK12,
author = {Ruiwen Chen and
Valentine Kabanets},
title = {Lower Bounds against Weakly Uniform Circuits},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-007}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/007},
eprinttype = {ECCC},
eprint = {TR12-007},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ChenK12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/CheraghchiGM12,
author = {Mahdi Cheraghchi and
Anna G{\'{a}}l and
Andrew Mills},
title = {Correctness and Corruption of Locally Decodable Codes},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-172}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/172},
eprinttype = {ECCC},
eprint = {TR12-172},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/CheraghchiGM12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/CheraghchiGV12,
author = {Mahdi Cheraghchi and
Venkatesan Guruswami and
Ameya Velingker},
title = {Restricted Isometry of Fourier Matrices and List Decodability of Random
Linear Codes},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-082}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/082},
eprinttype = {ECCC},
eprint = {TR12-082},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/CheraghchiGV12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/CookEMT12,
author = {James Cook and
Omid Etesami and
Rachel Miller and
Luca Trevisan},
title = {On the One-Way Function Candidate Proposed by Goldreich},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-175}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/175},
eprinttype = {ECCC},
eprint = {TR12-175},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/CookEMT12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/CzumajGRSSS12,
author = {Artur Czumaj and
Oded Goldreich and
Dana Ron and
C. Seshadhri and
Asaf Shapira and
Christian Sohler},
title = {Finding Cycles and Trees in Sublinear Time},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-035}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/035},
eprinttype = {ECCC},
eprint = {TR12-035},
timestamp = {Mon, 26 Jun 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/CzumajGRSSS12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/DeDFS12,
author = {Anindya De and
Ilias Diakonikolas and
Vitaly Feldman and
Rocco A. Servedio},
title = {Nearly optimal solutions for the Chow Parameters Problem and low-weight
approximation of halfspaces},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-072}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/072},
eprinttype = {ECCC},
eprint = {TR12-072},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/DeDFS12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/DeDS12,
author = {Anindya De and
Ilias Diakonikolas and
Rocco A. Servedio},
title = {Inverse Problems in Approximate Uniform Generation},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-152}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/152},
eprinttype = {ECCC},
eprint = {TR12-152},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/DeDS12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/DeDS12a,
author = {Anindya De and
Ilias Diakonikolas and
Rocco A. Servedio},
title = {The Inverse Shapley Value Problem},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-181}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/181},
eprinttype = {ECCC},
eprint = {TR12-181},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/DeDS12a.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/DeM12,
author = {Anindya De and
Elchanan Mossel},
title = {Explicit Optimal hardness via Gaussian stability results},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-016}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/016},
eprinttype = {ECCC},
eprint = {TR12-016},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/DeM12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/DinurK12,
author = {Irit Dinur and
Gillat Kol},
title = {Covering CSPs},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-088}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/088},
eprinttype = {ECCC},
eprint = {TR12-088},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/DinurK12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/DolevFG12,
author = {Shlomi Dolev and
Nova Fandina and
Dan Gutfreund},
title = {Succinct Permanent is NEXP-hard with Many Hard Instances},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-086}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/086},
eprinttype = {ECCC},
eprint = {TR12-086},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/DolevFG12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/Drucker12,
author = {Andrew Drucker},
title = {New Limits to Classical and Quantum Instance Compression},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-112}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/112},
eprinttype = {ECCC},
eprint = {TR12-112},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/Drucker12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/Duris12,
author = {Pavol Duris},
title = {A Note On the Hierarchy of One-way Data-Independent Multi-Head Finite
Automata},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-092}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/092},
eprinttype = {ECCC},
eprint = {TR12-092},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/Duris12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/DvirSW12,
author = {Zeev Dvir and
Shubhangi Saraf and
Avi Wigderson},
title = {Improved rank bounds for design matrices and a new proof of Kelly's
theorem},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-138}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/138},
eprinttype = {ECCC},
eprint = {TR12-138},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/DvirSW12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/EickmeyerHV12,
author = {Kord Eickmeyer and
Kristoffer Arnsfelt Hansen and
Elad Verbin},
title = {Approximating the minmax value of 3-player games within a constant
is as hard as detecting planted cliques},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-025}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/025},
eprinttype = {ECCC},
eprint = {TR12-025},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/EickmeyerHV12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ElberfeldST12,
author = {Michael Elberfeld and
Christoph Stockhusen and
Till Tantau},
title = {On the Space Complexity of Parameterized Problems},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-150}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/150},
eprinttype = {ECCC},
eprint = {TR12-150},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ElberfeldST12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/Even-ZoharL12,
author = {Chaim Even{-}Zohar and
Shachar Lovett},
title = {The Freiman-Ruzsa Theorem in Finite Fields},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-180}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/180},
eprinttype = {ECCC},
eprint = {TR12-180},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/Even-ZoharL12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/FederS12,
author = {Tom{\'{a}}s Feder and
Carlos S. Subi},
title = {Packing Edge-Disjoint Triangles in Given Graphs},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-013}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/013},
eprinttype = {ECCC},
eprint = {TR12-013},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/FederS12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/FeldmanGRVX12,
author = {Vitaly Feldman and
Elena Grigorescu and
Lev Reyzin and
Santosh S. Vempala and
Ying Xiao},
title = {Statistical Algorithms and a Lower Bound for Planted Clique},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-064}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/064},
eprinttype = {ECCC},
eprint = {TR12-064},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/FeldmanGRVX12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/FilmusLNRT12,
author = {Yuval Filmus and
Massimo Lauria and
Jakob Nordstr{\"{o}}m and
Noga Ron{-}Zewi and
Neil Thapen},
title = {Space Complexity in Polynomial Calculus},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-132}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/132},
eprinttype = {ECCC},
eprint = {TR12-132},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/FilmusLNRT12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/FlumM12,
author = {J{\"{o}}rg Flum and
Moritz M{\"{u}}ller},
title = {Some definitorial suggestions for parameterized proof complexity},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-018}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/018},
eprinttype = {ECCC},
eprint = {TR12-018},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/FlumM12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ForbesS12,
author = {Michael A. Forbes and
Amir Shpilka},
title = {Quasipolynomial-time Identity Testing of Non-Commutative and Read-Once
Oblivious Algebraic Branching Programs},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-115}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/115},
eprinttype = {ECCC},
eprint = {TR12-115},
timestamp = {Tue, 30 May 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ForbesS12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/FrancoisM12,
author = {Nathana{\"{e}}l Fran{\c{c}}ois and
Fr{\'{e}}d{\'{e}}ric Magniez},
title = {Streaming Complexity of Checking Priority Queues},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-128}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/128},
eprinttype = {ECCC},
eprint = {TR12-128},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/FrancoisM12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/FranklinGOS12,
author = {Matthew K. Franklin and
Ran Gelles and
Rafail Ostrovsky and
Leonard J. Schulman},
title = {Optimal Coding for Streaming Authentication and Interactive Communication},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-104}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/104},
eprinttype = {ECCC},
eprint = {TR12-104},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/FranklinGOS12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/GanorKR12,
author = {Anat Ganor and
Ilan Komargodski and
Ran Raz},
title = {The Spectrum of Small DeMorgan Formulas},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-174}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/174},
eprinttype = {ECCC},
eprint = {TR12-174},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/GanorKR12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/GavinskyLSS12,
author = {Dmitry Gavinsky and
Shachar Lovett and
Michael E. Saks and
Srikanth Srinivasan},
title = {A Tail Bound for Read-k Families of Functions},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-051}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/051},
eprinttype = {ECCC},
eprint = {TR12-051},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/GavinskyLSS12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/Goldreich12,
author = {Oded Goldreich},
title = {On the Effect of the Proximity Parameter on Property Testers},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-012}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/012},
eprinttype = {ECCC},
eprint = {TR12-012},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/Goldreich12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/Goldreich12a,
author = {Oded Goldreich},
title = {Two-Sided Error Proximity Oblivious Testing},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-021}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/021},
eprinttype = {ECCC},
eprint = {TR12-021},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/Goldreich12a.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/GoldreichGR12,
author = {Oded Goldreich and
Shafi Goldwasser and
Dana Ron},
title = {On the possibilities and limitations of pseudodeterministic algorithms},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-101}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/101},
eprinttype = {ECCC},
eprint = {TR12-101},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/GoldreichGR12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/GoldwasserR12,
author = {Shafi Goldwasser and
Guy N. Rothblum},
title = {How to Compute in the Presence of Leakage},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-010}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/010},
eprinttype = {ECCC},
eprint = {TR12-010},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/GoldwasserR12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/GopalanMR12,
author = {Parikshit Gopalan and
Raghu Meka and
Omer Reingold},
title = {{DNF} Sparsification and a Faster Deterministic Counting},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-060}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/060},
eprinttype = {ECCC},
eprint = {TR12-060},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/GopalanMR12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/GopalanMRTV12,
author = {Parikshit Gopalan and
Raghu Meka and
Omer Reingold and
Luca Trevisan and
Salil P. Vadhan},
title = {Better pseudorandom generators from milder pseudorandom restrictions},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-123}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/123},
eprinttype = {ECCC},
eprint = {TR12-123},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/GopalanMRTV12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/GreenKV12,
author = {Frederic Green and
Daniel Kreymer and
Emanuele Viola},
title = {Block-symmetric polynomials correlate with parity better than symmetric},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-160}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/160},
eprinttype = {ECCC},
eprint = {TR12-160},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/GreenKV12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/GuoKS12,
author = {Alan Guo and
Swastik Kopparty and
Madhu Sudan},
title = {New affine-invariant codes from lifting},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-149}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/149},
eprinttype = {ECCC},
eprint = {TR12-149},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/GuoKS12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/GuoS12,
author = {Alan Guo and
Madhu Sudan},
title = {Some closure features of locally testable affine-invariant properties},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-048}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/048},
eprinttype = {ECCC},
eprint = {TR12-048},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/GuoS12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/GuoS12a,
author = {Alan Guo and
Madhu Sudan},
title = {New affine-invariant codes from lifting},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-106}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/106},
eprinttype = {ECCC},
eprint = {TR12-106},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/GuoS12a.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/GuptaKKS12,
author = {Ankit Gupta and
Pritish Kamath and
Neeraj Kayal and
Ramprasad Saptharishi},
title = {An exponential lower bound for homogeneous depth four arithmetic circuits
with bounded bottom fanin},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-098}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/098},
eprinttype = {ECCC},
eprint = {TR12-098},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/GuptaKKS12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/GuptaKQ12,
author = {Ankit Gupta and
Neeraj Kayal and
Youming Qiao},
title = {Random Arithmetic Formulas can be Reconstructed Efficiently},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-033}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/033},
eprinttype = {ECCC},
eprint = {TR12-033},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/GuptaKQ12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/GurT12,
author = {Tom Gur and
Omer Tamuz},
title = {Testing Booleanity and the Uncertainty Principle},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-031}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/031},
eprinttype = {ECCC},
eprint = {TR12-031},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/GurT12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/GuruswamiN12,
author = {Venkatesan Guruswami and
Srivatsan Narayanan},
title = {Combinatorial limitations of a strong form of list decoding},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-017}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/017},
eprinttype = {ECCC},
eprint = {TR12-017},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/GuruswamiN12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/GuruswamiS12,
author = {Venkatesan Guruswami and
Ali Kemal Sinop},
title = {Faster {SDP} hierarchy solvers for local rounding algorithms},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-111}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/111},
eprinttype = {ECCC},
eprint = {TR12-111},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/GuruswamiS12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/GuruswamiW12,
author = {Venkatesan Guruswami and
Carol Wang},
title = {Linear-algebraic list decoding for variants of Reed-Solomon codes},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-073}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/073},
eprinttype = {ECCC},
eprint = {TR12-073},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/GuruswamiW12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/GuruswamiX12,
author = {Venkatesan Guruswami and
Chaoping Xing},
title = {Folded Codes from Function Field Towers and Improved Optimal Rate
List Decoding},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-036}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/036},
eprinttype = {ECCC},
eprint = {TR12-036},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/GuruswamiX12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/GuruswamiX12a,
author = {Venkatesan Guruswami and
Chaoping Xing},
title = {List decoding Reed-Solomon, Algebraic-Geometric, and Gabidulin subcodes
up to the Singleton bound},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-146}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/146},
eprinttype = {ECCC},
eprint = {TR12-146},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/GuruswamiX12a.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/GuruswamiZ12,
author = {Venkatesan Guruswami and
Yuan Zhou},
title = {Approximating Bounded Occurrence Ordering CSPs},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-074}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/074},
eprinttype = {ECCC},
eprint = {TR12-074},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/GuruswamiZ12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/HaitnerOZ12,
author = {Iftach Haitner and
Eran Omri and
Hila Zarosim},
title = {On the Power of Random Oracles},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-129}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/129},
eprinttype = {ECCC},
eprint = {TR12-129},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/HaitnerOZ12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/HaramatyS12,
author = {Elad Haramaty and
Madhu Sudan},
title = {Deterministic Compression with Uncertain Priors},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-166}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/166},
eprinttype = {ECCC},
eprint = {TR12-166},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/HaramatyS12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/Hastad12,
author = {Johan H{\aa}stad},
title = {On the correlation of parity and small-depth circuits},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-137}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/137},
eprinttype = {ECCC},
eprint = {TR12-137},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/Hastad12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/Hrubes12,
author = {Pavel Hrubes},
title = {A note on the real {\textdollar}{\textbackslash}tau{\textdollar}-conjecture
and the distribution of roots},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-121}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/121},
eprinttype = {ECCC},
eprint = {TR12-121},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/Hrubes12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/HrubesY12,
author = {Pavel Hrubes and
Amir Yehudayoff},
title = {Formulas are exponentially stronger than monotone circuits in non-commutative
setting},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-061}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/061},
eprinttype = {ECCC},
eprint = {TR12-061},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/HrubesY12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/Huang12,
author = {Sangxia Huang},
title = {Approximation Resistance on Satisfiable Instances for Predicates Strictly
Dominating Parity},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-040}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/040},
eprinttype = {ECCC},
eprint = {TR12-040},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/Huang12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/Huang12a,
author = {Jinyu Huang},
title = {Parallel Complexity for Matroid Intersection and Matroid Parity Problems},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-066}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/066},
eprinttype = {ECCC},
eprint = {TR12-066},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/Huang12a.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ImpagliazzoMZ12,
author = {Russell Impagliazzo and
Raghu Meka and
David Zuckerman},
title = {Pseudorandomness from Shrinkage},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-057}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/057},
eprinttype = {ECCC},
eprint = {TR12-057},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ImpagliazzoMZ12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ItoV12,
author = {Tsuyoshi Ito and
Thomas Vidick},
title = {A multi-prover interactive proof for {NEXP} sound against entangled
provers},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-085}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/085},
eprinttype = {ECCC},
eprint = {TR12-085},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ItoV12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ItsyksonS12,
author = {Dmitry Itsykson and
Dmitry Sokolov},
title = {Lower bounds for myopic {DPLL} algorithms with a cut heuristic},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-141}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/141},
eprinttype = {ECCC},
eprint = {TR12-141},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ItsyksonS12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/JafargholiJMRV12,
author = {Zahra Jafargholi and
Hamidreza Jahanjou and
Eric Miles and
Jaideep Ramachandran and
Emanuele Viola},
title = {From {RAM} to {SAT}},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-125}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/125},
eprinttype = {ECCC},
eprint = {TR12-125},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/JafargholiJMRV12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/Jirotka12,
author = {Tomas Jirotka},
title = {{NP} Search Problems},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-100}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/100},
eprinttype = {ECCC},
eprint = {TR12-100},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/Jirotka12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/JubaW12,
author = {Brendan Juba and
Ryan Williams},
title = {Massive Online Teaching to Bounded Learners},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-107}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/107},
eprinttype = {ECCC},
eprint = {TR12-107},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/JubaW12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/Jukna12,
author = {Stasys Jukna},
title = {Clique Problem, Cutting Plane Proofs, and Communication Complexity},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-039}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/039},
eprinttype = {ECCC},
eprint = {TR12-039},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/Jukna12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/Jukna12a,
author = {Stasys Jukna},
title = {Limitations of Incremental Dynamic Programs},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-041}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/041},
eprinttype = {ECCC},
eprint = {TR12-041},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/Jukna12a.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/JutlaKR12,
author = {Charanjit S. Jutla and
Vijay Kumar and
Atri Rudra},
title = {On the Circuit Complexity of Composite Galois Field Transformations},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-093}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/093},
eprinttype = {ECCC},
eprint = {TR12-093},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/JutlaKR12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/KarpinskiLS12,
author = {Marek Karpinski and
Andrzej Lingas and
Dzmitry Sledneu},
title = {Optimal Cuts and Partitions in Tree Metrics in Polynomial Time},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-176}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/176},
eprinttype = {ECCC},
eprint = {TR12-176},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/KarpinskiLS12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/KarpinskiS12,
author = {Marek Karpinski and
Richard Schmied},
title = {On Approximation Lower Bounds for {TSP} with Bounded Metrics},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-008}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/008},
eprinttype = {ECCC},
eprint = {TR12-008},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/KarpinskiS12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/KawachiRW12,
author = {Akinori Kawachi and
Benjamin Rossman and
Osamu Watanabe},
title = {Query Complexity and Error Tolerance of Witness Finding Algorithms},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-002}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/002},
eprinttype = {ECCC},
eprint = {TR12-002},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/KawachiRW12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/Kayal12,
author = {Neeraj Kayal},
title = {An exponential lower bound for the sum of powers of bounded degree
polynomials},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-081}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/081},
eprinttype = {ECCC},
eprint = {TR12-081},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/Kayal12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/KerenidisLLRX12,
author = {Iordanis Kerenidis and
Sophie Laplante and
Virginie Lerays and
J{\'{e}}r{\'{e}}mie Roland and
David Xiao},
title = {Lower bounds on information complexity via zero-communication protocols
and applications},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-038}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/038},
eprinttype = {ECCC},
eprint = {TR12-038},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/KerenidisLLRX12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/KhotST12,
author = {Subhash Khot and
Muli Safra and
Madhur Tulsiani},
title = {Towards An Optimal Query Efficient PCP?},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-109}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/109},
eprinttype = {ECCC},
eprint = {TR12-109},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/KhotST12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/KhotTW12,
author = {Subhash Khot and
Madhur Tulsiani and
Pratik Worah},
title = {The Complexity of Somewhat Approximation Resistant Predicates},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-151}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/151},
eprinttype = {ECCC},
eprint = {TR12-151},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/KhotTW12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/KintaliM12,
author = {Shiva Kintali and
Sinziana Munteanu},
title = {Computing Bounded Path Decompositions in Logspace},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-126}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/126},
eprinttype = {ECCC},
eprint = {TR12-126},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/KintaliM12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/KomargodskiR12,
author = {Ilan Komargodski and
Ran Raz},
title = {Average-Case Lower Bounds for Formula Size},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-062}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/062},
eprinttype = {ECCC},
eprint = {TR12-062},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/KomargodskiR12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/Kopparty12,
author = {Swastik Kopparty},
title = {List-Decoding Multiplicity Codes},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-044}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/044},
eprinttype = {ECCC},
eprint = {TR12-044},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/Kopparty12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/KoppartyS12,
author = {Swastik Kopparty and
Srikanth Srinivasan},
title = {Certifying Polynomials for AC\({}^{\mbox{0}}\)[{\(\oplus\)}] circuits,
with applications},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-102}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/102},
eprinttype = {ECCC},
eprint = {TR12-102},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/KoppartyS12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/KrebsL12,
author = {Andreas Krebs and
Nutan Limaye},
title = {DLOGTIME-Proof Systems},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-186}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/186},
eprinttype = {ECCC},
eprint = {TR12-186},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/KrebsL12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/KuhnertKW12,
author = {Sebastian Kuhnert and
Johannes K{\"{o}}bler and
Osamu Watanabe},
title = {Interval graph representation with given interval and intersection
lengths},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-032}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/032},
eprinttype = {ECCC},
eprint = {TR12-032},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/KuhnertKW12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/KulkarniS12,
author = {Raghav Kulkarni and
Miklos Santha},
title = {Query complexity of matroids},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-063}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/063},
eprinttype = {ECCC},
eprint = {TR12-063},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/KulkarniS12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/LaplanteLR12,
author = {Sophie Laplante and
Virginie Lerays and
J{\'{e}}r{\'{e}}mie Roland},
title = {Classical and quantum partition bound and detector inefficiency},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-023}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/023},
eprinttype = {ECCC},
eprint = {TR12-023},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/LaplanteLR12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/Lauria12,
author = {Massimo Lauria},
title = {A rank lower bound for cutting planes proofs of Ramsey Theorem},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-124}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/124},
eprinttype = {ECCC},
eprint = {TR12-124},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/Lauria12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/Leonardos12,
author = {Nikos Leonardos},
title = {An improved lower bound for the randomized decision tree complexity
of recursive majority},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-099}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/099},
eprinttype = {ECCC},
eprint = {TR12-099},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/Leonardos12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/LeviRR12,
author = {Reut Levi and
Dana Ron and
Ronitt Rubinfeld},
title = {Testing Similar Means},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-055}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/055},
eprinttype = {ECCC},
eprint = {TR12-055},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/LeviRR12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/Li12,
author = {Xin Li},
title = {New Independent Source Extractors with Exponential Improvement},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-147}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/147},
eprinttype = {ECCC},
eprint = {TR12-147},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/Li12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/Lovett12,
author = {Shachar Lovett},
title = {An exposition of Sanders quasi-polynomial Freiman-Ruzsa theorem},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-029}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/029},
eprinttype = {ECCC},
eprint = {TR12-029},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/Lovett12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/MagninR12,
author = {Lo{\"{\i}}ck Magnin and
J{\'{e}}r{\'{e}}mie Roland},
title = {Explicit relation between all lower bound techniques for quantum query
complexity},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-117}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/117},
eprinttype = {ECCC},
eprint = {TR12-117},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/MagninR12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/MahmoodyMP12,
author = {Mohammad Mahmoody and
Hemanta K. Maji and
Manoj Prabhakaran},
title = {Limits of Random Oracles in Secure Computation},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-065}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/065},
eprinttype = {ECCC},
eprint = {TR12-065},
timestamp = {Wed, 17 Apr 2024 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/MahmoodyMP12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/MahmoodyX12,
author = {Mohammad Mahmoody and
David Xiao},
title = {Languages with Efficient Zero-Knowledge PCPs are in {SZK}},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-052}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/052},
eprinttype = {ECCC},
eprint = {TR12-052},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/MahmoodyX12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ManyemU12,
author = {Prabhu Manyem and
Julien Ugon},
title = {Computational Complexity, {NP} Completeness and Optimization Duality:
{A} Survey},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-009}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/009},
eprinttype = {ECCC},
eprint = {TR12-009},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ManyemU12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/Micciancio12,
author = {Daniele Micciancio},
title = {Inapproximability of the Shortest Vector Problem: Toward a Deterministic
Reduction},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-020}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/020},
eprinttype = {ECCC},
eprint = {TR12-020},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/Micciancio12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/MilesV12,
author = {Eric Miles and
Emanuele Viola},
title = {On the complexity of constructing pseudorandom functions (especially
when they don't exist)},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-019}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/019},
eprinttype = {ECCC},
eprint = {TR12-019},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/MilesV12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/MittmannSS12,
author = {Johannes Mittmann and
Nitin Saxena and
Peter Scheiblechner},
title = {Algebraic Independence in Positive Characteristic - {A} p-Adic Calculus},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-014}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/014},
eprinttype = {ECCC},
eprint = {TR12-014},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/MittmannSS12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/Moitra12,
author = {Ankur Moitra},
title = {A Singly-Exponential Time Algorithm for Computing Nonnegative Rank},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-053}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/053},
eprinttype = {ECCC},
eprint = {TR12-053},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/Moitra12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/OstrovskyV12,
author = {Rafail Ostrovsky and
Ivan Visconti},
title = {Simultaneous Resettability from Collision Resistance},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-164}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/164},
eprinttype = {ECCC},
eprint = {TR12-164},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/OstrovskyV12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/PapakonstantinouRV12,
author = {Periklis A. Papakonstantinou and
Charles Rackoff and
Yevgeniy Vahlis},
title = {How powerful are the {DDH} hard groups?},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-167}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/167},
eprinttype = {ECCC},
eprint = {TR12-167},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/PapakonstantinouRV12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/PapakonstantinouY12,
author = {Periklis A. Papakonstantinou and
Guang Yang},
title = {A remark on one-wayness versus pseudorandomness},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-005}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/005},
eprinttype = {ECCC},
eprint = {TR12-005},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/PapakonstantinouY12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/RazborovV12,
author = {Alexander A. Razborov and
Emanuele Viola},
title = {Real Advantage},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-134}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/134},
eprinttype = {ECCC},
eprint = {TR12-134},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/RazborovV12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/SaisHH12,
author = {Lakhdar Sa{\"{\i}}s and
Mohand{-}Said Hacid and
Fran{\c{c}}ois Hantry},
title = {On the complexity of computing minimal unsatisfiable {LTL} formulas},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-069}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/069},
eprinttype = {ECCC},
eprint = {TR12-069},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/SaisHH12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/Salamon12,
author = {Andr{\'{a}}s Z. Salamon},
title = {Streaming bounds from difference ramification},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-183}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/183},
eprinttype = {ECCC},
eprint = {TR12-183},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/Salamon12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/Santhanam12,
author = {Rahul Santhanam},
title = {Ironic Complicity: Satisfiability Algorithms and Circuit Lower Bounds},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-084}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/084},
eprinttype = {ECCC},
eprint = {TR12-084},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/Santhanam12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/SanthanamW12,
author = {Rahul Santhanam and
Ryan Williams},
title = {Uniform Circuits, Lower Bounds, and {QBF} Algorithms},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-059}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/059},
eprinttype = {ECCC},
eprint = {TR12-059},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/SanthanamW12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ServedioTT12,
author = {Rocco A. Servedio and
Li{-}Yang Tan and
Justin Thaler},
title = {Attribute-Efficient Learning and Weight-Degree Tradeoffs for Polynomial
Threshold Functions},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-056}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/056},
eprinttype = {ECCC},
eprint = {TR12-056},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ServedioTT12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ServedioV12,
author = {Rocco A. Servedio and
Emanuele Viola},
title = {On a special case of rigidity},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-144}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/144},
eprinttype = {ECCC},
eprint = {TR12-144},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ServedioV12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/SetoT12,
author = {Kazuhisa Seto and
Suguru Tamaki},
title = {A Satisfiability Algorithm and Average-Case Hardness for Formulas
over the Full Binary Basis},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-071}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/071},
eprinttype = {ECCC},
eprint = {TR12-071},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/SetoT12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/Sherstov12,
author = {Alexander A. Sherstov},
title = {Making Polynomials Robust to Noise},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-037}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/037},
eprinttype = {ECCC},
eprint = {TR12-037},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/Sherstov12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/Steinke12,
author = {Thomas Steinke},
title = {Pseudorandomness for Permutation Branching Programs Without the Group
Theory},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-083}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/083},
eprinttype = {ECCC},
eprint = {TR12-083},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/Steinke12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/SudanZ12,
author = {Madhu Sudan and
Noga Zewi},
title = {A new upper bound on the query complexity for testing generalized
Reed-Muller codes},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-046}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/046},
eprinttype = {ECCC},
eprint = {TR12-046},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/SudanZ12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/Tal12,
author = {Avishay Tal},
title = {Properties and Applications of Boolean Function Composition},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-163}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/163},
eprinttype = {ECCC},
eprint = {TR12-163},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/Tal12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/Trevisan12,
author = {Luca Trevisan},
title = {A Derandomized Switching Lemma and an Improved Derandomization of
{AC0}},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-116}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/116},
eprinttype = {ECCC},
eprint = {TR12-116},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/Trevisan12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/TulsianiW12,
author = {Madhur Tulsiani and
Pratik Worah},
title = {{\textdollar}LS{\_}+{\textdollar} Lower Bounds from Pairwise Independence},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-105}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/105},
eprinttype = {ECCC},
eprint = {TR12-105},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/TulsianiW12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/Valiant12,
author = {Gregory Valiant},
title = {Finding Correlations in Subquadratic Time, with Applications to Learning
Parities and Juntas with Noise},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-006}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/006},
eprinttype = {ECCC},
eprint = {TR12-006},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/Valiant12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/Viderman12,
author = {Michael Viderman},
title = {Strong LTCs with inverse polylogarithmic rate and soundness},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-168}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/168},
eprinttype = {ECCC},
eprint = {TR12-168},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/Viderman12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/VillagraNYN12,
author = {Marcos Villagra and
Masaki Nakanishi and
Shigeru Yamashita and
Yasuhiko Nakashima},
title = {Tensor Rank and Strong Quantum Nondeterminism in Multiparty Communication},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-004}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/004},
eprinttype = {ECCC},
eprint = {TR12-004},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/VillagraNYN12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/Viola12,
author = {Emanuele Viola},
title = {Extractors for Turing-machine sources},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-047}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/047},
eprinttype = {ECCC},
eprint = {TR12-047},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/Viola12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/Watson12,
author = {Thomas Watson},
title = {Time Hierarchies for Sampling Distributions},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-026}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/026},
eprinttype = {ECCC},
eprint = {TR12-026},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/Watson12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/Watson12a,
author = {Thomas Watson},
title = {The Complexity of Estimating Min-Entropy},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-070}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/070},
eprinttype = {ECCC},
eprint = {TR12-070},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/Watson12a.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/Wenner12,
author = {Cenny Wenner},
title = {Circumventing d-to-1 for Approximation Resistance of Satisfiable Predicates
Strictly Containing Parity of Width at Least Four},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-145}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/145},
eprinttype = {ECCC},
eprint = {TR12-145},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/Wenner12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/WigdersonY12,
author = {Avi Wigderson and
Amir Yehudayoff},
title = {Population Recovery and Partial Identification},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-118}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/118},
eprinttype = {ECCC},
eprint = {TR12-118},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/WigdersonY12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/Worah12,
author = {Pratik Worah},
title = {Rank Bounds for a Hierarchy of Lov{\'{a}}sz and Schrijver},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-003}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/003},
eprinttype = {ECCC},
eprint = {TR12-003},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/Worah12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/Yakaryilmaz12,
author = {Abuzer Yakaryilmaz},
title = {One-counter verifiers for decidable languages},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-091}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/091},
eprinttype = {ECCC},
eprint = {TR12-091},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/Yakaryilmaz12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/Yakaryilmaz12a,
author = {Abuzer Yakaryilmaz},
title = {Public-qubits versus private-coins},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-130}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/130},
eprinttype = {ECCC},
eprint = {TR12-130},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/Yakaryilmaz12a.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/Zhandry12,
author = {Mark Zhandry},
title = {How to Construct Quantum Random Functions},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-140}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/140},
eprinttype = {ECCC},
eprint = {TR12-140},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/Zhandry12.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-06-03 20:09 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:
