ask others

Electronic Colloquium on Computational Complexity, Volume 19

> Home > Journals > Electronic Colloquium on Computational Complexity

Volume 19, 2012

- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/BhattacharyyaFL12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/BhattacharyyaFL12
Arnab Bhattacharyya, Eldar Fischer, Shachar Lovett:
Testing Low Complexity Affine-Invariant Properties. 1
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/KawachiRW12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/KawachiRW12
Akinori Kawachi, Benjamin Rossman, Osamu Watanabe:
Query Complexity and Error Tolerance of Witness Finding Algorithms. 2
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/Worah12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/Worah12
Pratik Worah:
Rank Bounds for a Hierarchy of Lovász and Schrijver. 3
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/VillagraNYN12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/VillagraNYN12
Marcos Villagra, Masaki Nakanishi, Shigeru Yamashita, Yasuhiko Nakashima:
Tensor Rank and Strong Quantum Nondeterminism in Multiparty Communication. 4
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/PapakonstantinouY12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/PapakonstantinouY12
Periklis A. Papakonstantinou, Guang Yang:
A remark on one-wayness versus pseudorandomness. 5
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/Valiant12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/Valiant12
Gregory Valiant:
Finding Correlations in Subquadratic Time, with Applications to Learning Parities and Juntas with Noise. 6
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/ChenK12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/ChenK12
Ruiwen Chen, Valentine Kabanets:
Lower Bounds against Weakly Uniform Circuits. 7
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/KarpinskiS12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/KarpinskiS12
Marek Karpinski, Richard Schmied:
On Approximation Lower Bounds for TSP with Bounded Metrics. 8
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/ManyemU12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/ManyemU12
Prabhu Manyem, Julien Ugon:
Computational Complexity, NP Completeness and Optimization Duality: A Survey. 9
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/GoldwasserR12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/GoldwasserR12
Shafi Goldwasser, Guy N. Rothblum:
How to Compute in the Presence of Leakage. 10
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/Bshouty12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/Bshouty12
Nader H. Bshouty:
Testers and their Applications. 11
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/Goldreich12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/Goldreich12
Oded Goldreich:
On the Effect of the Proximity Parameter on Property Testers. 12
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/FederS12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/FederS12
Tomás Feder, Carlos S. Subi:
Packing Edge-Disjoint Triangles in Given Graphs. 13
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/MittmannSS12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/MittmannSS12
Johannes Mittmann, Nitin Saxena, Peter Scheiblechner:
Algebraic Independence in Positive Characteristic - A p-Adic Calculus. 14
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/AtseriasD12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/AtseriasD12
Albert Atserias, Anuj Dawar:
Degree Lower Bounds of Tower-Type for Approximating Formulas with Parity Quantifiers. 15
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/DeM12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/DeM12
Anindya De, Elchanan Mossel:
Explicit Optimal hardness via Gaussian stability results. 16
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/GuruswamiN12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/GuruswamiN12
Venkatesan Guruswami, Srivatsan Narayanan:
Combinatorial limitations of a strong form of list decoding. 17
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/FlumM12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/FlumM12
Jörg Flum, Moritz Müller:
Some definitorial suggestions for parameterized proof complexity. 18
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/MilesV12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/MilesV12
Eric Miles, Emanuele Viola:
On the complexity of constructing pseudorandom functions (especially when they don't exist). 19
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/Micciancio12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/Micciancio12
Daniele Micciancio:
Inapproximability of the Shortest Vector Problem: Toward a Deterministic Reduction. 20
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/Goldreich12a
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/Goldreich12a
Oded Goldreich:
Two-Sided Error Proximity Oblivious Testing. 21
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/ChakrabartiCMT12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/ChakrabartiCMT12
Amit Chakrabarti, Graham Cormode, Andrew McGregor, Justin Thaler:
Annotations in Data Streams. 22
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/LaplanteLR12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/LaplanteLR12
Sophie Laplante, Virginie Lerays, Jérémie Roland:
Classical and quantum partition bound and detector inefficiency. 23
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/AaronsonC12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/AaronsonC12
Scott Aaronson, Paul Christiano:
Quantum Money from Hidden Subspaces. 24
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/EickmeyerHV12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/EickmeyerHV12
Kord Eickmeyer, Kristoffer Arnsfelt Hansen, Elad Verbin:
Approximating the minmax value of 3-player games within a constant is as hard as detecting planted cliques. 25
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/Watson12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/Watson12
Thomas Watson:
Time Hierarchies for Sampling Distributions. 26
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/AllenderCLPT12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/AllenderCLPT12
Eric Allender, Shiteng Chen, Tiancheng Lou, Periklis A. Papakonstantinou, Bangsheng Tang:
Time-space tradeoffs for width-parameterized SAT: Algorithms and lower bounds. 27
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/AllenderDFHT12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/AllenderDFHT12
Eric Allender, George Davie, Luke Friedman, Samuel Hopkins, Iddo Tzameret:
Kolmogorov Complexity, Circuits, and the Strength of Formal Theories of Arithmetic. 28
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/Lovett12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/Lovett12
Shachar Lovett:
An exposition of Sanders quasi-polynomial Freiman-Ruzsa theorem. 29
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/ChakrabartyS12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/ChakrabartyS12
Deeparnab Chakrabarty, C. Seshadhri:
Optimal bounds for monotonicity and Lipschitz testing over the hypercube. 30
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/GurT12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/GurT12
Tom Gur, Omer Tamuz:
Testing Booleanity and the Uncertainty Principle. 31
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/KuhnertKW12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/KuhnertKW12
Sebastian Kuhnert, Johannes Köbler, Osamu Watanabe:
Interval graph representation with given interval and intersection lengths. 32
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/GuptaKQ12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/GuptaKQ12
Ankit Gupta, Neeraj Kayal, Youming Qiao:
Random Arithmetic Formulas can be Reconstructed Efficiently. 33
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/BhowmickDL12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/BhowmickDL12
Abhishek Bhowmick, Zeev Dvir, Shachar Lovett:
New Lower Bounds for Matching Vector Codes. 34
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/CzumajGRSSS12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/CzumajGRSSS12
Artur Czumaj, Oded Goldreich, Dana Ron, C. Seshadhri, Asaf Shapira, Christian Sohler:
Finding Cycles and Trees in Sublinear Time. 35
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/GuruswamiX12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/GuruswamiX12
Venkatesan Guruswami, Chaoping Xing:
Folded Codes from Function Field Towers and Improved Optimal Rate List Decoding. 36
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/Sherstov12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/Sherstov12
Alexander A. Sherstov:
Making Polynomials Robust to Noise. 37
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/KerenidisLLRX12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/KerenidisLLRX12
Iordanis Kerenidis, Sophie Laplante, Virginie Lerays, Jérémie Roland, David Xiao:
Lower bounds on information complexity via zero-communication protocols and applications. 38
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/Jukna12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/Jukna12
Stasys Jukna:
Clique Problem, Cutting Plane Proofs, and Communication Complexity. 39
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/Huang12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/Huang12
Sangxia Huang:
Approximation Resistance on Satisfiable Instances for Predicates Strictly Dominating Parity. 40
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/Jukna12a
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/Jukna12a
Stasys Jukna:
Limitations of Incremental Dynamic Programs. 41
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/BeckIL12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/BeckIL12
Chris Beck, Russell Impagliazzo, Shachar Lovett:
Large Deviation Bounds for Decision Trees and Sampling Lower Bounds for AC0-circuits. 42
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/BrakerskiK12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/BrakerskiK12
Zvika Brakerski, Yael Tauman Kalai:
Efficient Interactive Coding Against Adversarial Noise. 43
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/Kopparty12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/Kopparty12
Swastik Kopparty:
List-Decoding Multiplicity Codes. 44
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/Ben-SassonCGT12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/Ben-SassonCGT12
Eli Ben-Sasson, Alessandro Chiesa, Daniel Genkin, Eran Tromer:
On the Concrete-Efficiency Threshold of Probabilistically-Checkable Proofs. 45
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/SudanZ12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/SudanZ12
Madhu Sudan, Noga Zewi:
A new upper bound on the query complexity for testing generalized Reed-Muller codes. 46
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/Viola12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/Viola12
Emanuele Viola:
Extractors for Turing-machine sources. 47
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/GuoS12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/GuoS12
Alan Guo, Madhu Sudan:
Some closure features of locally testable affine-invariant properties. 48
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/Ben-SassonRS12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/Ben-SassonRS12
Eli Ben-Sasson, Noga Ron-Zewi, Madhu Sudan:
Sparse affine-invariant linear codes are locally testable. 49
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/Ben-AroyaC12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/Ben-AroyaC12
Avraham Ben-Aroya, Gil Cohen:
Gradual Small-Bias Sample Spaces. 50
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/GavinskyLSS12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/GavinskyLSS12
Dmitry Gavinsky, Shachar Lovett, Michael E. Saks, Srikanth Srinivasan:
A Tail Bound for Read-k Families of Functions. 51
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/MahmoodyX12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/MahmoodyX12
Mohammad Mahmoody, David Xiao:
Languages with Efficient Zero-Knowledge PCPs are in SZK. 52
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/Moitra12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/Moitra12
Ankur Moitra:
A Singly-Exponential Time Algorithm for Computing Nonnegative Rank. 53
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/AllenderBFL12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/AllenderBFL12
Eric Allender, Harry Buhrman, Luke Friedman, Bruno Loff:
Reductions to the set of random strings: the resource-bounded case. 54
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/LeviRR12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/LeviRR12
Reut Levi, Dana Ron, Ronitt Rubinfeld:
Testing Similar Means. 55
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/ServedioTT12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/ServedioTT12
Rocco A. Servedio, Li-Yang Tan, Justin Thaler:
Attribute-Efficient Learning and Weight-Degree Tradeoffs for Polynomial Threshold Functions. 56
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/ImpagliazzoMZ12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/ImpagliazzoMZ12
Russell Impagliazzo, Raghu Meka, David Zuckerman:
Pseudorandomness from Shrinkage. 57
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/ApplebaumIK12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/ApplebaumIK12
Benny Applebaum, Yuval Ishai, Eyal Kushilevitz:
How to Garble Arithmetic Circuits. 58
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/SanthanamW12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/SanthanamW12
Rahul Santhanam, Ryan Williams:
Uniform Circuits, Lower Bounds, and QBF Algorithms. 59
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/GopalanMR12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/GopalanMR12
Parikshit Gopalan, Raghu Meka, Omer Reingold:
DNF Sparsification and a Faster Deterministic Counting. 60
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/HrubesY12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/HrubesY12
Pavel Hrubes, Amir Yehudayoff:
Formulas are exponentially stronger than monotone circuits in non-commutative setting. 61
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/KomargodskiR12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/KomargodskiR12
Ilan Komargodski, Ran Raz:
Average-Case Lower Bounds for Formula Size. 62
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/KulkarniS12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/KulkarniS12
Raghav Kulkarni, Miklos Santha:
Query complexity of matroids. 63
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/FeldmanGRVX12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/FeldmanGRVX12
Vitaly Feldman, Elena Grigorescu, Lev Reyzin, Santosh Vempala, Ying Xiao:
Statistical Algorithms and a Lower Bound for Planted Clique. 64
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/MahmoodyMP12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/MahmoodyMP12
Mohammad Mahmoody, Hemanta K. Maji, Manoj Prabhakaran:
Limits of Random Oracles in Secure Computation. 65
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/Huang12a
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/Huang12a
Jinyu Huang:
Parallel Complexity for Matroid Intersection and Matroid Parity Problems. 66
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/BeiCZ12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/BeiCZ12
Xiaohui Bei, Ning Chen, Shengyu Zhang:
On the Complexity of Trial and Error. 67
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/AroraIKS12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/AroraIKS12
Manuel Arora, Gábor Ivanyos, Marek Karpinski, Nitin Saxena:
Deterministic Polynomial Factoring and Association Schemes. 68
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/SaisHH12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/SaisHH12
Lakhdar Saïs, Mohand-Said Hacid, François Hantry:
On the complexity of computing minimal unsatisfiable LTL formulas. 69
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/Watson12a
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/Watson12a
Thomas Watson:
The Complexity of Estimating Min-Entropy. 70
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/SetoT12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/SetoT12
Kazuhisa Seto, Suguru Tamaki:
A Satisfiability Algorithm and Average-Case Hardness for Formulas over the Full Binary Basis. 71
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/DeDFS12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/DeDFS12
Anindya De, Ilias Diakonikolas, Vitaly Feldman, Rocco A. Servedio:
Nearly optimal solutions for the Chow Parameters Problem and low-weight approximation of halfspaces. 72
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/GuruswamiW12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/GuruswamiW12
Venkatesan Guruswami, Carol Wang:
Linear-algebraic list decoding for variants of Reed-Solomon codes. 73
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/GuruswamiZ12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/GuruswamiZ12
Venkatesan Guruswami, Yuan Zhou:
Approximating Bounded Occurrence Ordering CSPs. 74
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/AwasthiJMR12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/AwasthiJMR12
Pranjal Awasthi, Madhav Jha, Marco Molinaro, Sofya Raskhodnikova:
Limitations of Local Filters of Lipschitz and Monotone Functions. 75
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/AwasthiJMR12a
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/AwasthiJMR12a
Pranjal Awasthi, Madhav Jha, Marco Molinaro, Sofya Raskhodnikova:
Testing Lipschitz Functions on Hypergrid Domains. 76
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/ChakrabortyS12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/ChakrabortyS12
Chiranjit Chakraborty, Rahul Santhanam:
Instance Compression for the Polynomial Hierarchy and Beyond. 77
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/ArvindKKV12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/ArvindKKV12
Vikraman Arvind, Sebastian Kuhnert, Johannes Köbler, Yadu Vasudev:
Approximate Graph Isomorphism. 78
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/BeyersdorffDKMSSTV12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/BeyersdorffDKMSSTV12
Olaf Beyersdorff, Samir Datta, Andreas Krebs, Meena Mahajan, Gido Scharfenberger-Fabian, Karteek Sreenivasaiah, Michael Thomas, Heribert Vollmer:
Verifying Proofs in Constant Depth. 79
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/AydinliogluM12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/AydinliogluM12
Baris Aydinlioglu, Dieter van Melkebeek:
Nondeterministic Circuit Lower Bounds from Mildly Derandomizing Arthur-Merlin Games. 80
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/Kayal12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/Kayal12
Neeraj Kayal:
An exponential lower bound for the sum of powers of bounded degree polynomials. 81
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/CheraghchiGV12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/CheraghchiGV12
Mahdi Cheraghchi, Venkatesan Guruswami, Ameya Velingker:
Restricted Isometry of Fourier Matrices and List Decodability of Random Linear Codes. 82
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/Steinke12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/Steinke12
Thomas Steinke:
Pseudorandomness for Permutation Branching Programs Without the Group Theory. 83
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/Santhanam12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/Santhanam12
Rahul Santhanam:
Ironic Complicity: Satisfiability Algorithms and Circuit Lower Bounds. 84
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/ItoV12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/ItoV12
Tsuyoshi Ito, Thomas Vidick:
A multi-prover interactive proof for NEXP sound against entangled provers. 85
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/DolevFG12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/DolevFG12
Shlomi Dolev, Nova Fandina, Dan Gutfreund:
Succinct Permanent is NEXP-hard with Many Hard Instances. 86
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/AfshaniADCLM12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/AfshaniADCLM12
Peyman Afshani, Manindra Agrawal, Benjamin Doerr, Carola Winzen, Kasper Green Larsen, Kurt Mehlhorn:
The Deterministic and Randomized Query Complexity of a Simple Guessing Game. 87
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/DinurK12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/DinurK12
Irit Dinur, Gillat Kol:
Covering CSPs. 88
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/Boppana12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/Boppana12
Meena Boppana:
Lattice Variant of the Sensitivity Conjecture. 89
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/BlondinKM12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/BlondinKM12
Michael Blondin, Andreas Krebs, Pierre McKenzie:
The Complexity of Intersecting Finite Automata Having Few Final States. 90
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/Yakaryilmaz12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/Yakaryilmaz12
Abuzer Yakaryilmaz:
One-counter verifiers for decidable languages. 91
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/Duris12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/Duris12
Pavol Duris:
A Note On the Hierarchy of One-way Data-Independent Multi-Head Finite Automata. 92
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/JutlaKR12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/JutlaKR12
Charanjit S. Jutla, Vijay Kumar, Atri Rudra:
On the Circuit Complexity of Composite Galois Field Transformations. 93
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/AroraBMS12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/AroraBMS12
Sanjeev Arora, Arnab Bhattacharyya, Rajsekar Manokaran, Sushant Sachdeva:
Testing Permanent Oracles - Revisited. 94
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/Ben-AroyaS12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/Ben-AroyaS12
Avraham Ben-Aroya, Igor Shinkar:
A Note on Subspace Evasive Sets. 95
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/AtseriasO12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/AtseriasO12
Albert Atserias, Sergi Oliva:
Bounded-width QBF is PSPACE-complete. 96
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/BogdanovG12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/BogdanovG12
Andrej Bogdanov, Siyao Guo:
Sparse extractor families for all the entropy. 97
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/GuptaKKS12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/GuptaKKS12
Ankit Gupta, Pritish Kamath, Neeraj Kayal, Ramprasad Saptharishi:
An exponential lower bound for homogeneous depth four arithmetic circuits with bounded bottom fanin. 98
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/Leonardos12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/Leonardos12
Nikos Leonardos:
An improved lower bound for the randomized decision tree complexity of recursive majority. 99
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/Jirotka12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/Jirotka12
Tomas Jirotka:
NP Search Problems. 100
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/GoldreichGR12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/GoldreichGR12
Oded Goldreich, Shafi Goldwasser, Dana Ron:
On the possibilities and limitations of pseudodeterministic algorithms. 101
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/KoppartyS12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/KoppartyS12
Swastik Kopparty, Srikanth Srinivasan:
Certifying Polynomials for $\mathrm{AC}^0[\oplus]$ circuits, with applications. 102
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/BhattacharyyaY12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/BhattacharyyaY12
Arnab Bhattacharyya, Yuichi Yoshida:
Testing Assignments of Boolean CSPs. 103
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/FranklinGOS12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/FranklinGOS12
Matthew K. Franklin, Ran Gelles, Rafail Ostrovsky, Leonard J. Schulman:
Optimal Coding for Streaming Authentication and Interactive Communication. 104
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/TulsianiW12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/TulsianiW12
Madhur Tulsiani, Pratik Worah:
$LS_+$ Lower Bounds from Pairwise Independence. 105
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/GuoS12a
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/GuoS12a
Alan Guo, Madhu Sudan:
New affine-invariant codes from lifting. 106
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/JubaW12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/JubaW12
Brendan Juba, Ryan Williams:
Massive Online Teaching to Bounded Learners. 107
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/ChattopadhyayS12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/ChattopadhyayS12
Arkadev Chattopadhyay, Rahul Santhanam:
Lower Bounds on Interactive Compressibility by Constant-Depth Circuits. 108
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/KhotST12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/KhotST12
Subhash Khot, Muli Safra, Madhur Tulsiani:
Towards An Optimal Query Efficient PCP? 109
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/Chan12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/Chan12
Siu On Chan:
Approximation Resistance from Pairwise Independent Subgroups. 110
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/GuruswamiS12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/GuruswamiS12
Venkatesan Guruswami, Ali Kemal Sinop:
Faster SDP hierarchy solvers for local rounding algorithms. 111
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/Drucker12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/Drucker12
Andrew Drucker:
New Limits to Classical and Quantum Instance Compression. 112
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/AgrawalSS12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/AgrawalSS12
Manindra Agrawal, Chandan Saha, Nitin Saxena:
Quasi-polynomial Hitting-set for Set-depth-$\Delta$ Formulas. 113
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/Anokhin12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/Anokhin12
Mikhail Anokhin:
Constructing a Pseudo-Free Family of Finite Computational Groups under the General Integer Factoring Intractability Assumption. 114
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/ForbesS12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/ForbesS12
Michael A. Forbes, Amir Shpilka:
Quasipolynomial-time Identity Testing of Non-Commutative and Read-Once Oblivious Algebraic Branching Programs. 115
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/Trevisan12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/Trevisan12
Luca Trevisan:
A Derandomized Switching Lemma and an Improved Derandomization of AC0. 116
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/MagninR12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/MagninR12
Loïck Magnin, Jérémie Roland:
Explicit relation between all lower bound techniques for quantum query complexity. 117
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/WigdersonY12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/WigdersonY12
Avi Wigderson, Amir Yehudayoff:
Population Recovery and Partial Identification. 118
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/BonacinaG12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/BonacinaG12
Ilario Bonacina, Nicola Galesi:
Pseudo-partitions, Transversality and Locality: A Combinatorial Characterization for the Space Measure in Algebraic Proof Systems. 119
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/Barak12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/Barak12
Boaz Barak:
Proof vs. Truth in Computational Complexity. 120
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/Hrubes12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/Hrubes12
Pavel Hrubes:
A note on the real $\tau$-conjecture and the distribution of roots. 121
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/AusielloCL12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/AusielloCL12
Giorgio Ausiello, Francesco Cristiano, Luigi Laura:
Syntactic Isomorphism of CNF Boolean Formulas is Graph Isomorphism Complete. 122
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/GopalanMRTV12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/GopalanMRTV12
Parikshit Gopalan, Raghu Meka, Omer Reingold, Luca Trevisan, Salil P. Vadhan:
Better pseudorandom generators from milder pseudorandom restrictions. 123
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/Lauria12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/Lauria12
Massimo Lauria:
A rank lower bound for cutting planes proofs of Ramsey Theorem. 124
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/JafargholiJMRV12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/JafargholiJMRV12
Zahra Jafargholi, Hamidreza Jahanjou, Eric Miles, Jaideep Ramachandran, Emanuele Viola:
From RAM to SAT. 125
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/KintaliM12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/KintaliM12
Shiva Kintali, Sinziana Munteanu:
Computing Bounded Path Decompositions in Logspace. 126
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/ChattopadhyayKK12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/ChattopadhyayKK12
Eshan Chattopadhyay, Adam R. Klivans, Pravesh Kothari:
An Explicit VC-Theorem for Low-Degree Polynomials. 127
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/FrancoisM12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/FrancoisM12
Nathanaël François, Frédéric Magniez:
Streaming Complexity of Checking Priority Queues. 128
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/HaitnerOZ12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/HaitnerOZ12
Iftach Haitner, Eran Omri, Hila Zarosim:
On the Power of Random Oracles. 129
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/Yakaryilmaz12a
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/Yakaryilmaz12a
Abuzer Yakaryilmaz:
Public-qubits versus private-coins. 130
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/BravermanM12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/BravermanM12
Mark Braverman, Ankur Moitra:
An Information Complexity Approach to Extended Formulations. 131
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/FilmusLNRT12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/FilmusLNRT12
Yuval Filmus, Massimo Lauria, Jakob Nordström, Noga Ron-Zewi, Neil Thapen:
Space Complexity in Polynomial Calculus. 132
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/AlonC12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/AlonC12
Noga Alon, Gil Cohen:
On Rigid Matrices and Subspace Polynomials. 133
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/RazborovV12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/RazborovV12
Alexander A. Razborov, Emanuele Viola:
Real Advantage. 134
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/Ben-SassonRTW12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/Ben-SassonRTW12
Eli Ben-Sasson, Noga Ron-Zewi, Madhur Tulsiani, Julia Wolf:
Sampling-based proofs of almost-periodicity results and algorithmic applications. 135
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/BonehZ12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/BonehZ12
Dan Boneh, Mark Zhandry:
Quantum-Secure Message Authentication Codes. 136
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/Hastad12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/Hastad12
Johan Håstad:
On the correlation of parity and small-depth circuits. 137
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/DvirSW12
- ask others