| Hits ?▲ |
Authors |
Title |
Venue |
Year |
Link |
Author keywords |
| 1 | Eric Allender, Harry Buhrman, Luke Friedman, Bruno Loff |
Reductions to the set of random strings: the resource-bounded case.  |
Electronic Colloquium on Computational Complexity (ECCC)  |
2012 |
DBLP BibTeX RDF |
|
| 1 | Mohammad Mahmoody, David Xiao |
Languages with Efficient Zero-Knowledge PCPs are in SZK. |
Electronic Colloquium on Computational Complexity (ECCC) |
2012 |
DBLP BibTeX RDF |
|
| 1 | Iordanis Kerenidis, Sophie Laplante, Virginie Lerays, Jérémie Roland, David Xiao |
Lower bounds on information complexity via zero-communication protocols and applications. |
Electronic Colloquium on Computational Complexity (ECCC) |
2012 |
DBLP BibTeX RDF |
|
| 1 | Shachar Lovett |
An exposition of Sanders quasi-polynomial Freiman-Ruzsa theorem. |
Electronic Colloquium on Computational Complexity (ECCC) |
2012 |
DBLP BibTeX RDF |
|
| 1 | Eric Miles, Emanuele Viola |
On the complexity of constructing pseudorandom functions (especially when they don't exist). |
Electronic Colloquium on Computational Complexity (ECCC) |
2012 |
DBLP BibTeX RDF |
|
| 1 | Deeparnab Chakrabarty, C. Seshadhri |
Optimal bounds for monotonicity and Lipschitz testing over the hypercube. |
Electronic Colloquium on Computational Complexity (ECCC) |
2012 |
DBLP BibTeX RDF |
|
| 1 | Venkatesan Guruswami, Srivatsan Narayanan |
Combinatorial limitations of a strong form of list decoding. |
Electronic Colloquium on Computational Complexity (ECCC) |
2012 |
DBLP BibTeX RDF |
|
| 1 | Johannes Mittmann, Nitin Saxena, Peter Scheiblechner |
Algebraic Independence in Positive Characteristic - A p-Adic Calculus. |
Electronic Colloquium on Computational Complexity (ECCC) |
2012 |
DBLP BibTeX RDF |
|
| 1 | Sangxia Huang |
Approximation Resistance on Satisfiable Instances for Predicates Strictly Dominating Parity. |
Electronic Colloquium on Computational Complexity (ECCC) |
2012 |
DBLP BibTeX RDF |
|
| 1 | Tom Gur, Omer Tamuz |
Testing Booleanity and the Uncertainty Principle. |
Electronic Colloquium on Computational Complexity (ECCC) |
2012 |
DBLP BibTeX RDF |
|
| 1 | Chris Beck, Russell Impagliazzo, Shachar Lovett |
Large Deviation Bounds for Decision Trees and Sampling Lower Bounds for AC0-circuits. |
Electronic Colloquium on Computational Complexity (ECCC) |
2012 |
DBLP BibTeX RDF |
|
| 1 | Stasys Jukna |
Clique Problem, Cutting Plane Proofs, and Communication Complexity. |
Electronic Colloquium on Computational Complexity (ECCC) |
2012 |
DBLP BibTeX RDF |
|
| 1 | Daniele Micciancio |
Inapproximability of the Shortest Vector Problem: Toward a Deterministic Reduction. |
Electronic Colloquium on Computational Complexity (ECCC) |
2012 |
DBLP BibTeX RDF |
|
| 1 | Tomás Feder, Carlos S. Subi |
Packing Edge-Disjoint Triangles in Given Graphs. |
Electronic Colloquium on Computational Complexity (ECCC) |
2012 |
DBLP BibTeX RDF |
|
| 1 | Akinori Kawachi, Benjamin Rossman, Osamu Watanabe |
Query Complexity and Error Tolerance of Witness Finding Algorithms. |
Electronic Colloquium on Computational Complexity (ECCC) |
2012 |
DBLP BibTeX RDF |
|
| 1 | Rocco A. Servedio, Li-Yang Tan, Justin Thaler |
Attribute-Efficient Learning and Weight-Degree Tradeoffs for Polynomial Threshold Functions. |
Electronic Colloquium on Computational Complexity (ECCC) |
2012 |
DBLP BibTeX RDF |
|
| 1 | Stasys Jukna |
Limitations of Incremental Dynamic Programs. |
Electronic Colloquium on Computational Complexity (ECCC) |
2012 |
DBLP BibTeX RDF |
|
| 1 | Amit Chakrabarti, Graham Cormode, Andrew McGregor, Justin Thaler |
Annotations in Data Streams. |
Electronic Colloquium on Computational Complexity (ECCC) |
2012 |
DBLP BibTeX RDF |
|
| 1 | Ankit Gupta, Neeraj Kayal, Youming Qiao |
Random Arithmetic Formulas can be Reconstructed Efficiently. |
Electronic Colloquium on Computational Complexity (ECCC) |
2012 |
DBLP BibTeX RDF |
|
| 1 | Eric Allender, George Davie, Luke Friedman, Samuel Hopkins, Iddo Tzameret |
Kolmogorov Complexity, Circuits, and the Strength of Formal Theories of Arithmetic. |
Electronic Colloquium on Computational Complexity (ECCC) |
2012 |
DBLP BibTeX RDF |
|
| 1 | Artur Czumaj, Oded Goldreich, Dana Ron, C. Seshadhri, Asaf Shapira, Christian Sohler |
Finding Cycles and Trees in Sublinear Time. |
Electronic Colloquium on Computational Complexity (ECCC) |
2012 |
DBLP BibTeX RDF |
|
| 1 | Thomas Watson |
Time Hierarchies for Sampling Distributions. |
Electronic Colloquium on Computational Complexity (ECCC) |
2012 |
DBLP BibTeX RDF |
|
| 1 | Emanuele Viola |
Extractors for Turing-machine sources. |
Electronic Colloquium on Computational Complexity (ECCC) |
2012 |
DBLP BibTeX RDF |
|
| 1 | Arnab Bhattacharyya, Eldar Fischer, Shachar Lovett |
Testing Low Complexity Affine-Invariant Properties. |
Electronic Colloquium on Computational Complexity (ECCC) |
2012 |
DBLP BibTeX RDF |
|
| 1 | Parikshit Gopalan, Raghu Meka, Omer Reingold |
DNF Sparsification and a Faster Deterministic Counting. |
Electronic Colloquium on Computational Complexity (ECCC) |
2012 |
DBLP BibTeX RDF |
|
| 1 | Venkatesan Guruswami, Chaoping Xing |
Folded Codes from Function Field Towers and Improved Optimal Rate List Decoding. |
Electronic Colloquium on Computational Complexity (ECCC) |
2012 |
DBLP BibTeX RDF |
|
| 1 | Alexander A. Sherstov |
Making Polynomials Robust to Noise. |
Electronic Colloquium on Computational Complexity (ECCC) |
2012 |
DBLP BibTeX RDF |
|
| 1 | Periklis A. Papakonstantinou, Guang Yang |
A remark on one-wayness versus pseudorandomness. |
Electronic Colloquium on Computational Complexity (ECCC) |
2012 |
DBLP BibTeX RDF |
|
| 1 | Prabhu Manyem, Julien Ugon |
Computational Complexity, NP Completeness and Optimization Duality: A Survey. |
Electronic Colloquium on Computational Complexity (ECCC) |
2012 |
DBLP BibTeX RDF |
|
| 1 | Reut Levi, Dana Ron, Ronitt Rubinfeld |
Testing Similar Means. |
Electronic Colloquium on Computational Complexity (ECCC) |
2012 |
DBLP BibTeX RDF |
|
| 1 | Ruiwen Chen, Valentine Kabanets |
Lower Bounds against Weakly Uniform Circuits. |
Electronic Colloquium on Computational Complexity (ECCC) |
2012 |
DBLP BibTeX RDF |
|
| 1 | Alan Guo, Madhu Sudan |
Some closure features of locally testable affine-invariant properties. |
Electronic Colloquium on Computational Complexity (ECCC) |
2012 |
DBLP BibTeX RDF |
|
| 1 | Dmitry Gavinsky, Shachar Lovett, Michael E. Saks, Srikanth Srinivasan |
A Tail Bound for Read-k Families of Functions. |
Electronic Colloquium on Computational Complexity (ECCC) |
2012 |
DBLP BibTeX RDF |
|
| 1 | Zvika Brakerski, Yael Tauman Kalai |
Efficient Interactive Coding Against Adversarial Noise. |
Electronic Colloquium on Computational Complexity (ECCC) |
2012 |
DBLP BibTeX RDF |
|
| 1 | Anindya De, Elchanan Mossel |
Explicit Optimal hardness via Gaussian stability results. |
Electronic Colloquium on Computational Complexity (ECCC) |
2012 |
DBLP BibTeX RDF |
|
| 1 | Gregory Valiant |
Finding Correlations in Subquadratic Time, with Applications to Learning Parities and Juntas with Noise. |
Electronic Colloquium on Computational Complexity (ECCC) |
2012 |
DBLP BibTeX RDF |
|
| 1 | Marcos Villagra, Masaki Nakanishi, Shigeru Yamashita, Yasuhiko Nakashima |
Tensor Rank and Strong Quantum Nondeterminism in Multiparty Communication. |
Electronic Colloquium on Computational Complexity (ECCC) |
2012 |
DBLP BibTeX RDF |
|
| 1 | Eric Allender, Shiteng Chen, Tiancheng Lou, Periklis A. Papakonstantinou, Bangsheng Tang |
Time-space tradeoffs for width-parameterized SAT: Algorithms and lower bounds. |
Electronic Colloquium on Computational Complexity (ECCC) |
2012 |
DBLP BibTeX RDF |
|
| 1 | Raghav Kulkarni, Miklos Santha |
Query complexity of matroids. |
Electronic Colloquium on Computational Complexity (ECCC) |
2012 |
DBLP BibTeX RDF |
|
| 1 | Abhishek Bhowmick, Zeev Dvir, Shachar Lovett |
New Lower Bounds for Matching Vector Codes. |
Electronic Colloquium on Computational Complexity (ECCC) |
2012 |
DBLP BibTeX RDF |
|
| 1 | Benny Applebaum, Yuval Ishai, Eyal Kushilevitz |
How to Garble Arithmetic Circuits. |
Electronic Colloquium on Computational Complexity (ECCC) |
2012 |
DBLP BibTeX RDF |
|
| 1 | Eli Ben-Sasson, Noga Ron-Zewi, Madhu Sudan |
Sparse affine-invariant linear codes are locally testable. |
Electronic Colloquium on Computational Complexity (ECCC) |
2012 |
DBLP BibTeX RDF |
|
| 1 | Swastik Kopparty |
List-Decoding Multiplicity Codes. |
Electronic Colloquium on Computational Complexity (ECCC) |
2012 |
DBLP BibTeX RDF |
|
| 1 | Jörg Flum, Moritz Müller |
Some definitorial suggestions for parameterized proof complexity. |
Electronic Colloquium on Computational Complexity (ECCC) |
2012 |
DBLP BibTeX RDF |
|
| 1 | Vitaly Feldman, Elena Grigorescu, Lev Reyzin, Santosh Vempala, Ying Xiao |
Statistical Algorithms and a Lower Bound for Planted Clique. |
Electronic Colloquium on Computational Complexity (ECCC) |
2012 |
DBLP BibTeX RDF |
|
| 1 | Albert Atserias, Anuj Dawar |
Degree Lower Bounds of Tower-Type for Approximating Formulas with Parity Quantifiers. |
Electronic Colloquium on Computational Complexity (ECCC) |
2012 |
DBLP BibTeX RDF |
|
| 1 | Eli Ben-Sasson, Alessandro Chiesa, Daniel Genkin, Eran Tromer |
On the Concrete-Efficiency Threshold of Probabilistically-Checkable Proofs. |
Electronic Colloquium on Computational Complexity (ECCC) |
2012 |
DBLP BibTeX RDF |
|
| 1 | Avraham Ben-Aroya, Gil Cohen |
Gradual Small-Bias Sample Spaces. |
Electronic Colloquium on Computational Complexity (ECCC) |
2012 |
DBLP BibTeX RDF |
|
| 1 | Oded Goldreich |
On the Effect of the Proximity Parameter on Property Testers. |
Electronic Colloquium on Computational Complexity (ECCC) |
2012 |
DBLP BibTeX RDF |
|
| 1 | Scott Aaronson, Paul Christiano |
Quantum Money from Hidden Subspaces. |
Electronic Colloquium on Computational Complexity (ECCC) |
2012 |
DBLP BibTeX RDF |
|
| 1 | Rahul Santhanam, Ryan Williams |
Uniform Circuits, Lower Bounds, and QBF Algorithms. |
Electronic Colloquium on Computational Complexity (ECCC) |
2012 |
DBLP BibTeX RDF |
|
| 1 | Shafi Goldwasser, Guy N. Rothblum |
How to Compute in the Presence of Leakage. |
Electronic Colloquium on Computational Complexity (ECCC) |
2012 |
DBLP BibTeX RDF |
|
| 1 | Pratik Worah |
Rank Bounds for a Hierarchy of Lovász and Schrijver. |
Electronic Colloquium on Computational Complexity (ECCC) |
2012 |
DBLP BibTeX RDF |
|
| 1 | Nader H. Bshouty |
Testers and their Applications. |
Electronic Colloquium on Computational Complexity (ECCC) |
2012 |
DBLP BibTeX RDF |
|
| 1 | Sophie Laplante, Virginie Lerays, Jérémie Roland |
Classical and quantum partition bound and detector inefficiency. |
Electronic Colloquium on Computational Complexity (ECCC) |
2012 |
DBLP BibTeX RDF |
|
| 1 | 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. |
Electronic Colloquium on Computational Complexity (ECCC) |
2012 |
DBLP BibTeX RDF |
|
| 1 | Pavel Hrubes, Amir Yehudayoff |
Formulas are exponentially stronger than monotone circuits in non-commutative setting. |
Electronic Colloquium on Computational Complexity (ECCC) |
2012 |
DBLP BibTeX RDF |
|
| 1 | Ilan Komargodski, Ran Raz |
Average-Case Lower Bounds for Formula Size. |
Electronic Colloquium on Computational Complexity (ECCC) |
2012 |
DBLP BibTeX RDF |
|
| 1 | Marek Karpinski, Richard Schmied |
On Approximation Lower Bounds for TSP with Bounded Metrics. |
Electronic Colloquium on Computational Complexity (ECCC) |
2012 |
DBLP BibTeX RDF |
|
| 1 | Russell Impagliazzo, Raghu Meka, David Zuckerman |
Pseudorandomness from Shrinkage. |
Electronic Colloquium on Computational Complexity (ECCC) |
2012 |
DBLP BibTeX RDF |
|
| 1 | Ankur Moitra |
A Singly-Exponential Time Algorithm for Computing Nonnegative Rank. |
Electronic Colloquium on Computational Complexity (ECCC) |
2012 |
DBLP BibTeX RDF |
|
| 1 | Oded Goldreich |
Two-Sided Error Proximity Oblivious Testing. |
Electronic Colloquium on Computational Complexity (ECCC) |
2012 |
DBLP BibTeX RDF |
|
| 1 | Madhu Sudan, Noga Zewi |
A new upper bound on the query complexity for testing generalized Reed-Muller codes. |
Electronic Colloquium on Computational Complexity (ECCC) |
2012 |
DBLP BibTeX RDF |
|
| 1 | Sebastian Kuhnert, Johannes Köbler, Osamu Watanabe |
Interval graph representation with given interval and intersection lengths. |
Electronic Colloquium on Computational Complexity (ECCC) |
2012 |
DBLP BibTeX RDF |
|
| 1 | Gilad Asharov, Yehuda Lindell |
A Full Proof of the BGW Protocol for Perfectly-Secure Multiparty Computation. |
Electronic Colloquium on Computational Complexity (ECCC) |
2011 |
DBLP BibTeX RDF |
|
| 1 | Richard Beigel, Bin Fu |
A Dense Hierarchy of Sublinear Time Approximation Schemes for Bin Packing. |
Electronic Colloquium on Computational Complexity (ECCC) |
2011 |
DBLP BibTeX RDF |
|
| 1 | Ronitt Rubinfeld, Asaf Shapira |
Sublinear Time Algorithms. |
Electronic Colloquium on Computational Complexity (ECCC) |
2011 |
DBLP BibTeX RDF |
|
| 1 | Brett Hemenway, Rafail Ostrovsky, Martin Strauss, Mary Wootters |
Public Key Locally Decodable Codes with Short Keys. |
Electronic Colloquium on Computational Complexity (ECCC) |
2011 |
DBLP BibTeX RDF |
|
| 1 | Christoph Behle, Andreas Krebs |
Regular Languages in MAJ[>] with three variables. |
Electronic Colloquium on Computational Complexity (ECCC) |
2011 |
DBLP BibTeX RDF |
|
| 1 | Christoph Behle, Andreas Krebs, Klaus-Jörn Lange, Pierre McKenzie |
Low uniform versions of NC1. |
Electronic Colloquium on Computational Complexity (ECCC) |
2011 |
DBLP BibTeX RDF |
|
| 1 | Vikraman Arvind, Partha Mukhopadhyay, Prajakta Nimbhorkar, Yadu Vasudev |
Expanding Generator Sets for Solvable Permutation Groups. |
Electronic Colloquium on Computational Complexity (ECCC) |
2011 |
DBLP BibTeX RDF |
|
| 1 | Michael Viderman |
Linear time decoding of regular expander codes. |
Electronic Colloquium on Computational Complexity (ECCC) |
2011 |
DBLP BibTeX RDF |
|
| 1 | Zeev Dvir, Guillaume Malod, Sylvain Perifel, Amir Yehudayoff |
Separating multilinear branching programs and formulas. |
Electronic Colloquium on Computational Complexity (ECCC) |
2011 |
DBLP BibTeX RDF |
|
| 1 | Scott Aaronson |
A Linear-Optical Proof that the Permanent is #P-Hard. |
Electronic Colloquium on Computational Complexity (ECCC) |
2011 |
DBLP BibTeX RDF |
|
| 1 | Irit Dinur, Tali Kaufman |
Dense locally testable codes cannot have constant rate and distance. |
Electronic Colloquium on Computational Complexity (ECCC) |
2011 |
DBLP BibTeX RDF |
|
| 1 | Brady Garvin, Derrick Stolee, Raghunath Tewari, N. V. Vinodchandran |
ReachFewL = ReachUL. |
Electronic Colloquium on Computational Complexity (ECCC) |
2011 |
DBLP BibTeX RDF |
|
| 1 | Malte Beecken, Johannes Mittmann, Nitin Saxena |
Algebraic Independence and Blackbox Identity Testing. |
Electronic Colloquium on Computational Complexity (ECCC) |
2011 |
DBLP BibTeX RDF |
|
| 1 | Zeev Dvir, Anup Rao, Avi Wigderson, Amir Yehudayoff |
Restriction Access. |
Electronic Colloquium on Computational Complexity (ECCC) |
2011 |
DBLP BibTeX RDF |
|
| 1 | Miklós Ajtai |
Secure Computation with Information Leaking to an Adversary. |
Electronic Colloquium on Computational Complexity (ECCC) |
2011 |
DBLP BibTeX RDF |
|
| 1 | Piotr Indyk, Reut Levi, Ronitt Rubinfeld |
Approximating and Testing k-Histogram Distributions in Sub-linear time. |
Electronic Colloquium on Computational Complexity (ECCC) |
2011 |
DBLP BibTeX RDF |
|
| 1 | Michael A. Forbes, Amir Shpilka |
On Identity Testing of Tensors, Low-rank Recovery and Compressed Sensing. |
Electronic Colloquium on Computational Complexity (ECCC) |
2011 |
DBLP BibTeX RDF |
|
| 1 | Valentin E. Brimkov, Andrew Leach, Jimmy Wu, Michael Mastroianni |
On the Approximability of a Geometric Set Cover Problem. |
Electronic Colloquium on Computational Complexity (ECCC) |
2011 |
DBLP BibTeX RDF |
|
| 1 | Maurice J. Jansen, Rahul Santhanam |
Stronger Lower Bounds and Randomness-Hardness Tradeoffs using Associated Algebraic Complexity Classes. |
Electronic Colloquium on Computational Complexity (ECCC) |
2011 |
DBLP BibTeX RDF |
|
| 1 | Yijia Chen, Jörg Flum |
Listings and logics. |
Electronic Colloquium on Computational Complexity (ECCC) |
2011 |
DBLP BibTeX RDF |
|
| 1 | Sebastian Müller, Iddo Tzameret |
Average-Case Separation in Proof Complexity: Short Propositional Refutations for Random 3CNF Formulas. |
Electronic Colloquium on Computational Complexity (ECCC) |
2011 |
DBLP BibTeX RDF |
|
| 1 | Oded Goldreich |
Two Comments on Targeted Canonical Derandomizers. |
Electronic Colloquium on Computational Complexity (ECCC) |
2011 |
DBLP BibTeX RDF |
|
| 1 | Masaki Yamamoto |
A tighter lower bound on the circuit size of the hardest Boolean functions. |
Electronic Colloquium on Computational Complexity (ECCC) |
2011 |
DBLP BibTeX RDF |
|
| 1 | Ludwig Staiger |
Exact constructive dimension. |
Electronic Colloquium on Computational Complexity (ECCC) |
2011 |
DBLP BibTeX RDF |
|
| 1 | Vikraman Arvind, Yadu Vasudev |
Isomorphism Testing of Boolean Functions Computable by Constant Depth Circuits. |
Electronic Colloquium on Computational Complexity (ECCC) |
2011 |
DBLP BibTeX RDF |
|
| 1 | Ludwig Staiger |
Oscillation-free Chaitin h-random sequences. |
Electronic Colloquium on Computational Complexity (ECCC) |
2011 |
DBLP BibTeX RDF |
|
| 1 | Ankit Gupta, Neeraj Kayal, Satyanarayana V. Lokam |
Reconstruction of Depth-4 Multilinear Circuits with Top fanin 2. |
Electronic Colloquium on Computational Complexity (ECCC) |
2011 |
DBLP BibTeX RDF |
|
| 1 | Xin Li |
Design Extractors, Non-Malleable Condensers and Privacy Amplification. |
Electronic Colloquium on Computational Complexity (ECCC) |
2011 |
DBLP BibTeX RDF |
|
| 1 | Shubhangi Saraf, Ilya Volkovich |
Black-Box Identity Testing of Depth-4 Multilinear Circuits. |
Electronic Colloquium on Computational Complexity (ECCC) |
2011 |
DBLP BibTeX RDF |
|
| 1 | Pavol Duris |
On Computational Power of Partially Blind Automata. |
Electronic Colloquium on Computational Complexity (ECCC) |
2011 |
DBLP BibTeX RDF |
|
| 1 | Pavel Hrubes |
How much commutativity is needed to prove polynomial identities? |
Electronic Colloquium on Computational Complexity (ECCC) |
2011 |
DBLP BibTeX RDF |
|
| 1 | Pavel Pudlák |
A lower bound on the size of resolution proofs of the Ramsey theorem. |
Electronic Colloquium on Computational Complexity (ECCC) |
2011 |
DBLP BibTeX RDF |
|
| 1 | Oded Goldreich, Ron Rothblum |
Enhancements of Trapdoor Permutations. |
Electronic Colloquium on Computational Complexity (ECCC) |
2011 |
DBLP BibTeX RDF |
|
| 1 | Boaz Barak, Prasad Raghavendra, David Steurer |
Rounding Semidefinite Programming Hierarchies via Global Correlation. |
Electronic Colloquium on Computational Complexity (ECCC) |
2011 |
DBLP BibTeX RDF |
|
| 1 | Joshua A. Grochow |
Lie algebra conjugacy. |
Electronic Colloquium on Computational Complexity (ECCC) |
2011 |
DBLP BibTeX RDF |
|
| 1 | Mark Braverman |
Towards deterministic tree code constructions. |
Electronic Colloquium on Computational Complexity (ECCC) |
2011 |
DBLP BibTeX RDF |
|
![[Valid RSS]](Pics/valid-rss.png "Validate my RSS feed")