| Hits ?▲ |
Authors |
Title |
Venue |
Year |
Link |
Author keywords |
| 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 | Arnab Bhattacharyya, Eldar Fischer, Shachar Lovett |
Testing Low Complexity Affine-Invariant Properties. |
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 | Ruiwen Chen, Valentine Kabanets |
Lower Bounds against Weakly Uniform Circuits. |
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 | Pratik Worah |
Rank Bounds for a Hierarchy of Lovász and Schrijver. |
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 | 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 |
|
| 1 | Venkatesan Guruswami, Ali Kemal Sinop |
Lasserre Hierarchy, Higher Eigenvalues, and Approximation Schemes for Quadratic Integer Programming with PSD Objectives. |
Electronic Colloquium on Computational Complexity (ECCC) |
2011 |
DBLP BibTeX RDF |
|
| 1 | Varun Kanade, Thomas Steinke |
Learning Hurdles for Sleeping Experts. |
Electronic Colloquium on Computational Complexity (ECCC) |
2011 |
DBLP BibTeX RDF |
|
| 1 | Nader H. Bshouty, Hanna Mazzawi |
Algorithms for the Coin Weighing Problems with the Presence of Noise. |
Electronic Colloquium on Computational Complexity (ECCC) |
2011 |
DBLP BibTeX RDF |
|
| 1 | Pinyan Lu |
Complexity Dichotomies of Counting Problems. |
Electronic Colloquium on Computational Complexity (ECCC) |
2011 |
DBLP BibTeX RDF |
|
| 1 | Mahdi Cheraghchi, Adam Klivans, Pravesh Kothari, Homin K. Lee |
Submodular Functions Are Noise Stable. |
Electronic Colloquium on Computational Complexity (ECCC) |
2011 |
DBLP BibTeX RDF |
|
| 1 | Anindya De, Thomas Watson |
Extractors and Lower Bounds for Locally Samplable Sources. |
Electronic Colloquium on Computational Complexity (ECCC) |
2011 |
DBLP BibTeX RDF |
|
| 1 | Benny Applebaum, Andrej Bogdanov, Alon Rosen |
A Dichotomy for Local Small-Bias Generators. |
Electronic Colloquium on Computational Complexity (ECCC) |
2011 |
DBLP BibTeX RDF |
|
| 1 | Rahul Santhanam, Srikanth Srinivasan |
On the Limits of Sparsification. |
Electronic Colloquium on Computational Complexity (ECCC) |
2011 |
DBLP BibTeX RDF |
|
| 1 | Michael Elberfeld, Andreas Jakoby, Till Tantau |
Algorithmic Meta Theorems for Circuit Classes of Constant and Logarithmic Depth. |
Electronic Colloquium on Computational Complexity (ECCC) |
2011 |
DBLP BibTeX RDF |
|
| 1 | Mark Braverman |
Interactive information complexity. |
Electronic Colloquium on Computational Complexity (ECCC) |
2011 |
DBLP BibTeX RDF |
|
| 1 | Krzysztof Fleszar, Christian Glaßer, Fabian Lipp, Christian Reitwießner, Maximilian Witek |
The Complexity of Solving Multiobjective Optimization Problems and its Relation to Multivalued Functions. |
Electronic Colloquium on Computational Complexity (ECCC) |
2011 |
DBLP BibTeX RDF |
|
| 1 | Sergei Artemenko, Ronen Shaltiel |
Lower bounds on the query complexity of non-uniform and adaptive reductions showing hardness amplification. |
Electronic Colloquium on Computational Complexity (ECCC) |
2011 |
DBLP BibTeX RDF |
|
| 1 | Andrew Drucker |
Efficient Probabilistically Checkable Debates. |
Electronic Colloquium on Computational Complexity (ECCC) |
2011 |
DBLP BibTeX RDF |
|
| 1 | Eli Ben-Sasson, Shachar Lovett, Noga Zewi |
An additive combinatorics approach to the log-rank conjecture in communication complexity. |
Electronic Colloquium on Computational Complexity (ECCC) |
2011 |
DBLP BibTeX RDF |
|
| 1 | Yang Li |
BQP and PPAD. |
Electronic Colloquium on Computational Complexity (ECCC) |
2011 |
DBLP BibTeX RDF |
|
| 1 | Scott Aaronson |
Why Philosophers Should Care About Computational Complexity. |
Electronic Colloquium on Computational Complexity (ECCC) |
2011 |
DBLP BibTeX RDF |
|
| 1 | Gil Cohen, Ran Raz, Gil Segev |
Non-Malleable Extractors with Short Seeds and Applications to Privacy Amplification. |
Electronic Colloquium on Computational Complexity (ECCC) |
2011 |
DBLP BibTeX RDF |
|
| 1 | Rahul Jain |
New strong direct product results in communication complexity. |
Electronic Colloquium on Computational Complexity (ECCC) |
2011 |
DBLP BibTeX RDF |
|
| 1 | Mohammad Iftekhar Husain, Steve Ko, Atri Rudra, Steve Uurtamo |
Storage Enforcement with Kolmogorov Complexity and List Decoding. |
Electronic Colloquium on Computational Complexity (ECCC) |
2011 |
DBLP BibTeX RDF |
|
| 1 | Arnab Bhattacharyya, Elena Grigorescu, Prasad Raghavendra, Asaf Shapira |
Testing Odd-Cycle-Freeness in Boolean Functions. |
Electronic Colloquium on Computational Complexity (ECCC) |
2011 |
DBLP BibTeX RDF |
|
| 1 | Greg Kuperberg, Shachar Lovett, Ron Peled |
Probabilistic existence of rigid combinatorial structures. |
Electronic Colloquium on Computational Complexity (ECCC) |
2011 |
DBLP BibTeX RDF |
|
| 1 | Rohit Gurjar, Arpita Korwar, Jochen Messner, Simon Straub, Thomas Thierauf |
Planarizing Gadgets for Perfect Matching do not Exist. |
Electronic Colloquium on Computational Complexity (ECCC) |
2011 |
DBLP BibTeX RDF |
|
| 1 | Scott Aaronson |
Impossibility of Succinct Quantum Proofs for Collision-Freeness. |
Electronic Colloquium on Computational Complexity (ECCC) |
2011 |
DBLP BibTeX RDF |
|
| 1 | Ronen Shaltiel |
Dispersers for affine sources with sub-polynomial entropy. |
Electronic Colloquium on Computational Complexity (ECCC) |
2011 |
DBLP BibTeX RDF |
|
| 1 | Anna Gál, Kristoffer Arnsfelt Hansen, Michal Koucký, Pavel Pudlák, Emanuele Viola |
Tight bounds on computing error-correcting codes by bounded-depth circuits with arbitrary gates. |
Electronic Colloquium on Computational Complexity (ECCC) |
2011 |
DBLP BibTeX RDF |
|
| 1 | Noga Alon, Amir Shpilka, Chris Umans |
On Sunflowers and Matrix Multiplication. |
Electronic Colloquium on Computational Complexity (ECCC) |
2011 |
DBLP BibTeX RDF |
|
| 1 | Shubhangi Saraf, Sergey Yekhanin |
Noisy Interpolation of Sparse Polynomials, and Applications. |
Electronic Colloquium on Computational Complexity (ECCC) |
2011 |
DBLP BibTeX RDF |
|
| 1 | Neeraj Kayal |
Affine projections of polynomials. |
Electronic Colloquium on Computational Complexity (ECCC) |
2011 |
DBLP BibTeX RDF |
|
| 1 | Maurice J. Jansen, Rahul Santhanam |
Marginal Hitting Sets Imply Super-Polynomial Lower Bounds for Permanent. |
Electronic Colloquium on Computational Complexity (ECCC) |
2011 |
DBLP BibTeX RDF |
|
| 1 | Rahul Jain, Shengyu Zhang |
The influence lower bound via query elimination. |
Electronic Colloquium on Computational Complexity (ECCC) |
2011 |
DBLP BibTeX RDF |
|
| 1 | Chandan Saha, Ramprasad Saptharishi, Nitin Saxena |
A Case of Depth-3 Identity Testing, Sparse Factorization and Duality. |
Electronic Colloquium on Computational Complexity (ECCC) |
2011 |
DBLP BibTeX RDF |
|
| 1 | Eli Ben-Sasson, Elena Grigorescu, Ghid Maatouk, Amir Shpilka, Madhu Sudan |
On Sums of Locally Testable Affine Invariant Properties. |
Electronic Colloquium on Computational Complexity (ECCC) |
2011 |
DBLP BibTeX RDF |
|
| 1 | Thomas Watson |
Advice Lower Bounds for the Dense Model Theorem. |
Electronic Colloquium on Computational Complexity (ECCC) |
2011 |
DBLP BibTeX RDF |
|
| 1 | Salil P. Vadhan, Colin Jia Zheng |
Characterizing Pseudoentropy and Simplifying Pseudorandom Generator Constructions. |
Electronic Colloquium on Computational Complexity (ECCC) |
2011 |
DBLP BibTeX RDF |
|
| 1 | Andrej Bogdanov, Periklis A. Papakonstantinou, Andrew Wan |
Pseudorandomness for read-once formulas. |
Electronic Colloquium on Computational Complexity (ECCC) |
2011 |
DBLP BibTeX RDF |
|
| 1 | Andris Ambainis, Xiaoming Sun |
New separation between s(f) and bs(f). |
Electronic Colloquium on Computational Complexity (ECCC) |
2011 |
DBLP BibTeX RDF |
|
| 1 | Anil Ada, Arkadev Chattopadhyay, Omar Fawzi, Phuong Nguyen |
The NOF Multiparty Communication Complexity of Composed Functions. |
Electronic Colloquium on Computational Complexity (ECCC) |
2011 |
DBLP BibTeX RDF |
|
| 1 | Danny Hermelin, Xi Wu |
Weak Compositions and Their Applications to Polynomial Lower-Bounds for Kernelization. |
Electronic Colloquium on Computational Complexity (ECCC) |
2011 |
DBLP BibTeX RDF |
|
| 1 | Guy Moshkovitz |
Complexity Lower Bounds through Balanced Graph Properties. |
Electronic Colloquium on Computational Complexity (ECCC) |
2011 |
DBLP BibTeX RDF |
|
| 1 | Hamed Hatami, Shachar Lovett |
Correlation testing for affine invariant properties on Fpn in the high error regime. |
Electronic Colloquium on Computational Complexity (ECCC) |
2011 |
DBLP BibTeX RDF |
|
| 1 | Christoph Behle, Andreas Krebs, Stephanie Reifferscheid |
Typed Monoids - An Eilenberg-like Theorem for non regular Languages. |
Electronic Colloquium on Computational Complexity (ECCC) |
2011 |
DBLP BibTeX RDF |
|
| 1 | Benny Applebaum |
Pseudorandom Generators with Long Stretch and Low locality from Random Local One-Way Functions. |
Electronic Colloquium on Computational Complexity (ECCC) |
2011 |
DBLP BibTeX RDF |
|
| 1 | Zeev Dvir, Shachar Lovett |
Subspace Evasive Sets. |
Electronic Colloquium on Computational Complexity (ECCC) |
2011 |
DBLP BibTeX RDF |
|
| 1 | Valentine Kabanets, Osamu Watanabe |
Is the Valiant-Vazirani Isolation Lemma Improvable? |
Electronic Colloquium on Computational Complexity (ECCC) |
2011 |
DBLP BibTeX RDF |
|
| 1 | Frederic Green, Daniel Kreymer, Emanuele Viola |
In Brute-Force Search of Correlation Bounds for Polynomials. |
Electronic Colloquium on Computational Complexity (ECCC) |
2011 |
DBLP BibTeX RDF |
|
| 1 | Marcel R. Ackermann, Johannes Blömer, Christoph Scholz |
Hardness and Non-Approximability of Bregman Clustering Problems. |
Electronic Colloquium on Computational Complexity (ECCC) |
2011 |
DBLP BibTeX RDF |
|
| 1 | Graham Cormode, Michael Mitzenmacher, Justin Thaler |
Streaming Graph Computations with a Helpful Advisor. |
Electronic Colloquium on Computational Complexity (ECCC) |
2011 |
DBLP BibTeX RDF |
|
| 1 | Marius Zimand |
On the optimal compression of sets in PSPACE. |
Electronic Colloquium on Computational Complexity (ECCC) |
2011 |
DBLP BibTeX RDF |
|
| 1 | Emanuele Viola |
Extractors for circuit sources. |
Electronic Colloquium on Computational Complexity (ECCC) |
2011 |
DBLP BibTeX RDF |
|
| 1 | Noga Alon, Shachar Lovett |
Almost k-wise vs. k-wise independent permutations, and uniformity for general group actions. |
Electronic Colloquium on Computational Complexity (ECCC) |
2011 |
DBLP BibTeX RDF |
|
| 1 | Serge Gaspers, Stefan Szeider |
The Parameterized Complexity of Local Consistency. |
Electronic Colloquium on Computational Complexity (ECCC) |
2011 |
DBLP BibTeX RDF |
|
| 1 | Andrej Bogdanov, Alon Rosen |
Input locality and hardness amplification. |
Electronic Colloquium on Computational Complexity (ECCC) |
2011 |
DBLP BibTeX RDF |
|
| 1 | Pavel Hrubes, Iddo Tzameret |
Short Proofs for the Determinant Identities. |
Electronic Colloquium on Computational Complexity (ECCC) |
2011 |
DBLP BibTeX RDF |
|
| 1 | Fabian Wagner |
Graphs of Bounded Treewidth can be Canonized in AC1. |
Electronic Colloquium on Computational Complexity (ECCC) |
2011 |
DBLP BibTeX RDF |
|
| 1 | Amit Chakrabarti, Graham Cormode, Andrew McGregor |
Robust Lower Bounds for Communication and Stream Computation. |
Electronic Colloquium on Computational Complexity (ECCC) |
2011 |
DBLP BibTeX RDF |
|
| 1 | Arkadev Chattopadhyay, Shachar Lovett |
Linear systems over abelian groups. |
Electronic Colloquium on Computational Complexity (ECCC) |
2011 |
DBLP BibTeX RDF |
|
![[Valid RSS]](Pics/valid-rss.png "Validate my RSS feed")