Volume 19, 2012
export record as
dblp key:
journals/eccc/BhattacharyyaFL12 export record as
dblp key:
journals/eccc/KawachiRW12 export record as
dblp key:
Pratik Worah :
Rank Bounds for a Hierarchy of Lovász and Schrijver.
3
export record as
dblp key:
journals/eccc/VillagraNYN12 export record as
dblp key:
journals/eccc/PapakonstantinouY12 export record as
dblp key:
Gregory Valiant :
Finding Correlations in Subquadratic Time, with Applications to Learning Parities and Juntas with Noise.
6
export record as
dblp key:
export record as
dblp key:
journals/eccc/KarpinskiS12 export record as
dblp key:
export record as
dblp key:
journals/eccc/GoldwasserR12 export record as
dblp key:
export record as
dblp key:
journals/eccc/Goldreich12 Oded Goldreich :
On the Effect of the Proximity Parameter on Property Testers.
12
export record as
dblp key:
export record as
dblp key:
journals/eccc/MittmannSS12 export record as
dblp key:
journals/eccc/AtseriasD12 export record as
dblp key:
export record as
dblp key:
journals/eccc/GuruswamiN12 export record as
dblp key:
export record as
dblp key:
Eric Miles ,
Emanuele Viola :
On the complexity of constructing pseudorandom functions (especially when they don't exist).
19
export record as
dblp key:
journals/eccc/Micciancio12 Daniele Micciancio :
Inapproximability of the Shortest Vector Problem: Toward a Deterministic Reduction.
20
export record as
dblp key:
journals/eccc/Goldreich12a export record as
dblp key:
journals/eccc/ChakrabartiCMT12 export record as
dblp key:
journals/eccc/LaplanteLR12 export record as
dblp key:
journals/eccc/AaronsonC12 export record as
dblp key:
journals/eccc/EickmeyerHV12 export record as
dblp key:
export record as
dblp key:
journals/eccc/AllenderCLPT12 export record as
dblp key:
journals/eccc/AllenderDFHT12 export record as
dblp key:
Shachar Lovett :
An exposition of Sanders quasi-polynomial Freiman-Ruzsa theorem.
29
export record as
dblp key:
journals/eccc/ChakrabartyS12 export record as
dblp key:
export record as
dblp key:
journals/eccc/KuhnertKW12 export record as
dblp key:
export record as
dblp key:
journals/eccc/BhowmickDL12 export record as
dblp key:
journals/eccc/GuruswamiX12 export record as
dblp key:
export record as
dblp key:
journals/eccc/KerenidisLLRX12 export record as
dblp key:
Stasys Jukna :
Clique Problem, Cutting Plane Proofs, and Communication Complexity.
39
export record as
dblp key:
Sangxia Huang :
Approximation Resistance on Satisfiable Instances for Predicates Strictly Dominating Parity.
40
export record as
dblp key:
Stasys Jukna :
Limitations of Incremental Dynamic Programs.
41
export record as
dblp key:
export record as
dblp key:
journals/eccc/BrakerskiK12 export record as
dblp key:
export record as
dblp key:
journals/eccc/Ben-SassonCGT12 export record as
dblp key:
Madhu Sudan ,
Noga Zewi :
A new upper bound on the query complexity for testing generalized Reed-Muller codes.
46
export record as
dblp key:
export record as
dblp key:
Alan Guo ,
Madhu Sudan :
Some closure features of locally testable affine-invariant properties.
48
export record as
dblp key:
journals/eccc/Ben-SassonRS12 export record as
dblp key:
journals/eccc/Ben-AroyaC12 export record as
dblp key:
journals/eccc/GavinskyLSS12 export record as
dblp key:
journals/eccc/MahmoodyX12 export record as
dblp key:
Ankur Moitra :
A Singly-Exponential Time Algorithm for Computing Nonnegative Rank.
53
export record as
dblp key:
journals/eccc/AllenderBFL12 export record as
dblp key:
export record as
dblp key:
journals/eccc/ServedioTT12 export record as
dblp key:
journals/eccc/ImpagliazzoMZ12 export record as
dblp key:
journals/eccc/ApplebaumIK12 export record as
dblp key:
journals/eccc/SanthanamW12 export record as
dblp key:
journals/eccc/GopalanMR12 export record as
dblp key:
export record as
dblp key:
journals/eccc/KomargodskiR12 export record as
dblp key:
journals/eccc/KulkarniS12 export record as
dblp key:
journals/eccc/FeldmanGRVX12 export record as
dblp key:
journals/eccc/MahmoodyMP12 export record as
dblp key:
Jinyu Huang :
Parallel Complexity for Matroid Intersection and Matroid Parity Problems.
66
export record as
dblp key:
export record as
dblp key:
export record as
dblp key:
export record as
dblp key:
export record as
dblp key:
export record as
dblp key:
export record as
dblp key:
journals/eccc/GuruswamiW12 export record as
dblp key:
journals/eccc/GuruswamiZ12 export record as
dblp key:
journals/eccc/AwasthiJMR12 export record as
dblp key:
journals/eccc/AwasthiJMR12a export record as
dblp key:
journals/eccc/ChakrabortyS12 export record as
dblp key:
journals/eccc/ArvindKKV12 export record as
dblp key:
journals/eccc/BeyersdorffDKMSSTV12 export record as
dblp key:
journals/eccc/AydinliogluM12 export record as
dblp key:
Neeraj Kayal :
An exponential lower bound for the sum of powers of bounded degree polynomials.
81
export record as
dblp key:
journals/eccc/CheraghchiGV12 export record as
dblp key:
Thomas Steinke :
Pseudorandomness for Permutation Branching Programs Without the Group Theory.
83
export record as
dblp key:
journals/eccc/Santhanam12 Rahul Santhanam :
Ironic Complicity: Satisfiability Algorithms and Circuit Lower Bounds.
84
export record as
dblp key:
export record as
dblp key:
export record as
dblp key:
journals/eccc/AfshaniADCLM12 export record as
dblp key:
export record as
dblp key:
export record as
dblp key:
journals/eccc/BlondinKM12 export record as
dblp key:
journals/eccc/Yakaryilmaz12 export record as
dblp key:
Pavol Duris :
A Note On the Hierarchy of One-way Data-Independent Multi-Head Finite Automata.
92
export record as
dblp key:
export record as
dblp key:
export record as
dblp key:
journals/eccc/Ben-AroyaS12 export record as
dblp key:
journals/eccc/AtseriasO12 export record as
dblp key:
journals/eccc/BogdanovG12 export record as
dblp key:
export record as
dblp key:
journals/eccc/Leonardos12 Nikos Leonardos :
An improved lower bound for the randomized decision tree complexity of recursive majority.
99
export record as
dblp key:
export record as
dblp key:
journals/eccc/GoldreichGR12 export record as
dblp key:
journals/eccc/KoppartyS12 export record as
dblp key:
journals/eccc/BhattacharyyaY12 export record as
dblp key:
journals/eccc/FranklinGOS12 export record as
dblp key:
journals/eccc/TulsianiW12 export record as
dblp key:
export record as
dblp key:
export record as
dblp key:
journals/eccc/ChattopadhyayS12 export record as
dblp key:
export record as
dblp key:
Siu On Chan :
Approximation Resistance from Pairwise Independent Subgroups.
110
export record as
dblp key:
journals/eccc/GuruswamiS12 export record as
dblp key:
Andrew Drucker :
New Limits to Classical and Quantum Instance Compression.
112
export record as
dblp key:
journals/eccc/AgrawalSS12 export record as
dblp key:
Mikhail Anokhin :
Constructing a Pseudo-Free Family of Finite Computational Groups under the General Integer Factoring Intractability Assumption.
114
export record as
dblp key:
Michael A. Forbes ,
Amir Shpilka :
Quasipolynomial-time Identity Testing of Non-Commutative and Read-Once Oblivious Algebraic Branching Programs.
115
export record as
dblp key:
Luca Trevisan :
A Derandomized Switching Lemma and an Improved Derandomization of AC0.
116
export record as
dblp key:
export record as
dblp key:
journals/eccc/WigdersonY12 export record as
dblp key:
journals/eccc/BonacinaG12 Ilario Bonacina ,
Nicola Galesi :
Pseudo-partitions, Transversality and Locality: A Combinatorial Characterization for the Space Measure in Algebraic Proof Systems.
119
export record as
dblp key:
Boaz Barak :
Proof vs. Truth in Computational Complexity.
120
export record as
dblp key:
Pavel Hrubes :
A note on the real $\tau$-conjecture and the distribution of roots.
121
export record as
dblp key:
journals/eccc/AusielloCL12 export record as
dblp key:
journals/eccc/GopalanMRTV12 export record as
dblp key:
Massimo Lauria :
A rank lower bound for cutting planes proofs of Ramsey Theorem.
124
export record as
dblp key:
journals/eccc/JafargholiJMRV12 export record as
dblp key:
export record as
dblp key:
journals/eccc/ChattopadhyayKK12 export record as
dblp key:
journals/eccc/FrancoisM12 export record as
dblp key:
journals/eccc/HaitnerOZ12 export record as
dblp key:
journals/eccc/Yakaryilmaz12a export record as
dblp key:
journals/eccc/BravermanM12 export record as
dblp key:
journals/eccc/FilmusLNRT12 export record as
dblp key:
export record as
dblp key:
journals/eccc/RazborovV12 export record as
dblp key:
journals/eccc/Ben-SassonRTW12 export record as
dblp key:
export record as
dblp key:
Johan Håstad :
On the correlation of parity and small-depth circuits.
137
export record as
dblp key:
export record as
dblp key:
export record as
dblp key:
Mark Zhandry :
How to Construct Quantum Random Functions.
140
export record as
dblp key:
journals/eccc/ItsyksonS12 export record as
dblp key:
export record as
dblp key:
journals/eccc/BravermanRWY12 export record as
dblp key:
journals/eccc/ServedioV12 export record as
dblp key:
Cenny Wenner :
Circumventing d-to-1 for Approximation Resistance of Satisfiable Predicates Strictly Containing Parity of Width at Least Four.
145
export record as
dblp key:
journals/eccc/GuruswamiX12a export record as
dblp key:
Xin Li :
New Independent Source Extractors with Exponential Improvement.
147
export record as
dblp key:
journals/eccc/Ben-SassonGKKS12 export record as
dblp key:
export record as
dblp key:
journals/eccc/ElberfeldST12 export record as
dblp key:
export record as
dblp key:
export record as
dblp key:
export record as
dblp key:
journals/eccc/ChakrabortyFGM12 export record as
dblp key:
journals/eccc/CanonneRS12 export record as
dblp key:
journals/eccc/BogdanovL12 export record as
dblp key:
journals/eccc/BogdanovL12a export record as
dblp key:
journals/eccc/BhaskaraDS12 export record as
dblp key:
journals/eccc/Ben-SassonV12 export record as
dblp key:
export record as
dblp key:
journals/eccc/BeyersdorffGL12 export record as
dblp key:
journals/eccc/BockenhauerHKKSS12 export record as
dblp key:
Avishay Tal :
Properties and Applications of Boolean Function Composition.
163
export record as
dblp key:
journals/eccc/OstrovskyV12 export record as
dblp key:
journals/eccc/AlbrechtFFHP12 export record as
dblp key:
journals/eccc/HaramatyS12 export record as
dblp key:
journals/eccc/PapakonstantinouRV12 export record as
dblp key:
Michael Viderman :
Strong LTCs with inverse polylogarithmic rate and soundness.
168
export record as
dblp key:
export record as
dblp key:
journals/eccc/AaronsonH12 export record as
dblp key:
journals/eccc/BravermanGPW12 export record as
dblp key:
journals/eccc/CheraghchiGM12 export record as
dblp key:
export record as
dblp key:
export record as
dblp key:
export record as
dblp key:
journals/eccc/KarpinskiLS12 export record as
dblp key:
journals/eccc/BravermanGPW12a export record as
dblp key:
export record as
dblp key:
journals/eccc/BrodyBKLS12 export record as
dblp key:
journals/eccc/Even-ZoharL12 export record as
dblp key:
export record as
dblp key:
journals/eccc/BermanHKN12 export record as
dblp key:
export record as
dblp key:
journals/eccc/BhattacharyyaFHHL12 export record as
dblp key:
export record as
dblp key:
data released under the ODC-BY 1.0 license
