default search action
Search dblp for Publications
export results for "toc:db/journals/eccc/eccc19.bht:"
@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} }
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.