default search action
Electronic Colloquium on Computational Complexity, 2011
Volume TR11, 2011
- Scott Aaronson:
Impossibility of Succinct Quantum Proofs for Collision-Freeness. - Gil Cohen, Amir Shpilka, Avishay Tal:
On the Degree of Univariate Polynomials Over the Integers. - Yehuda Lindell:
Constant-Round Zero-Knowledge Proofs of Knowledge. - Oded Goldreich, Salil P. Vadhan:
On the complexity of computational problems regarding distributions (a survey). - Madhu Sudan:
Testing Linear Properties: Some general themes. - Sebastian Müller, Iddo Tzameret:
Average-Case Separation in Proof Complexity: Short Propositional Refutations for Random 3CNF Formulas. - Benny Applebaum:
Pseudorandom Generators with Long Stretch and Low locality from Random Local One-Way Functions. - Scott Aaronson, Andrew Drucker:
Advice Coins for Classical and Quantum Computation. - Samir Datta, Gautam Prakriya:
Planarity Testing Revisited. - Boris Alexeev, Michael A. Forbes, Jacob Tsimerman:
Tensor Rank: Some Lower and Upper Bounds. - Ming Lam Leung, Yang Li, Shengyu Zhang:
Tight bounds on the randomized communication complexity of symmetric XOR functions in one-way and SMP models. - Andrej Bogdanov, Alon Rosen:
Input locality and hardness amplification. - Ronitt Rubinfeld, Asaf Shapira:
Sublinear Time Algorithms. - Antoine Taveneaux:
Towards an axiomatic system for Kolmogorov complexity. - Marcel R. Ackermann, Johannes Blömer, Christoph Scholz:
Hardness and Non-Approximability of Bregman Clustering Problems. - Sergei Artemenko, Ronen Shaltiel:
Lower bounds on the query complexity of non-uniform and adaptive reductions showing hardness amplification. - Fengming Wang:
NEXP does not have non-uniform quasi-polynomial-size ACC circuits of o(loglog n) depth. - Jochen Messner, Thomas Thierauf:
A Kolmogorov Complexity Proof of the Lovász Local Lemma for Satisfiability. - Valentin E. Brimkov, Andrew Leach, Jimmy Wu, Michael Mastroianni:
On the Approximability of a Geometric Set Cover Problem. - Yijia Chen, Jörg Flum:
Listings and logics. - Chandan Saha, Ramprasad Saptharishi, Nitin Saxena:
A Case of Depth-3 Identity Testing, Sparse Factorization and Duality. - Malte Beecken, Johannes Mittmann, Nitin Saxena:
Algebraic Independence and Blackbox Identity Testing. - Oded Goldreich, Or Meir:
Input-Oblivious Proof Systems and a Uniform Complexity Perspective on P/poly. - Rahul Jain:
New strong direct product results in communication complexity. - Yang Li:
Monotone Rank and Separations in Computational Complexity. - Evgeny Demenkov, Alexander S. Kulikov:
An Elementary Proof of 3n-o(n) Lower Bound on the Circuit Complexity of Affine Dispersers. - Venkatesan Guruswami, Johan Håstad, Rajsekar Manokaran, Prasad Raghavendra, Moses Charikar:
Beating the Random Ordering is Hard: Every ordering CSP is approximation resistant. - Richard Beigel, Bin Fu:
A Dense Hierarchy of Sublinear Time Approximation Schemes for Bin Packing. - Hamed Hatami, Shachar Lovett:
Correlation testing for affine invariant properties on Fpn in the high error regime. - Anna Gál, Andrew Mills:
Three Query Locally Decodable Codes with Higher Correctness Require Exponential Length. - Sam Buss, Ryan Williams:
Limits on Alternation-Trading Proofs for Time-Space Lower Bounds. - Fabian Wagner:
Graphs of Bounded Treewidth can be Canonized in AC1. - Rahul Jain, Shengyu Zhang:
The influence lower bound via query elimination. - Pavol Duris, Marek Kosta:
Flip-Pushdown Automata with k Pushdown Reversals and E0L Systems are Incomparable. - Christoph Behle, Andreas Krebs, Stephanie Reifferscheid:
Typed Monoids - An Eilenberg-like Theorem for non regular Languages. - Gilad Asharov, Yehuda Lindell:
A Full Proof of the BGW Protocol for Perfectly-Secure Multiparty Computation. - Anindya De, Thomas Watson:
Extractors and Lower Bounds for Locally Samplable Sources. - Jiapeng Zhang:
On the query complexity for Showing Dense Model. - Frederic Green, Daniel Kreymer, Emanuele Viola:
In Brute-Force Search of Correlation Bounds for Polynomials. - Alexander A. Sherstov:
Strong Direct Product Theorems for Quantum Communication and Query Complexity. - Dana Ron, Gilad Tsur:
Testing Computability by Width-Two OBDDs. - Ankur Moitra:
Efficiently Coding for Interactive Communication. - Scott Aaronson:
A Linear-Optical Proof that the Permanent is #P-Hard. - Shubhangi Saraf, Sergey Yekhanin:
Noisy Interpolation of Sparse Polynomials, and Applications. - Eric Blais, Joshua Brody, Kevin Matulef:
Property Testing Lower Bounds via Communication Complexity. - Shubhangi Saraf, Ilya Volkovich:
Black-Box Identity Testing of Depth-4 Multilinear Circuits. - Oded Goldreich:
Two Comments on Targeted Canonical Derandomizers. - Arkadev Chattopadhyay, Shachar Lovett:
Linear systems over abelian groups. - Noga Alon, Shachar Lovett:
Almost k-wise vs. k-wise independent permutations, and uniformity for general group actions. - Claus-Peter Schnorr:
Accelerated Slide- and LLL-Reduction. - Thomas Vidick:
A concentration inequality for the overlap of a vector on a large set, With application to the communication complexity of the Gap-Hamming-Distance problem. - Fabian Wagner:
On the Complexity of Group Isomorphism. - 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. - Arnab Bhattacharyya, Zeev Dvir, Shubhangi Saraf, Amir Shpilka:
Tight lower bounds for 2-query LCCs over finite fields. - Irit Dinur, Tali Kaufman:
Dense locally testable codes cannot have constant rate and distance. - Emanuele Viola:
Extractors for circuit sources. - Madhav Jha, Sofya Raskhodnikova:
Testing and Reconstruction of Lipschitz Functions with Applications to Data Privacy. - Michael Viderman:
Linear time decoding of regular expander codes. - Elad Haramaty, Amir Shpilka, Madhu Sudan:
Optimal testing of multivariate polynomials over small prime fields. - Brady Garvin, Derrick Stolee, Raghunath Tewari, N. V. Vinodchandran:
ReachFewL = ReachUL. - Neeraj Kayal:
Affine projections of polynomials. - Amit Chakrabarti, Graham Cormode, Andrew McGregor:
Robust Lower Bounds for Communication and Stream Computation. - Alexander A. Sherstov:
The Communication Complexity of Gap Hamming Distance. - Mark Braverman:
Towards deterministic tree code constructions. - Boaz Barak, Prasad Raghavendra, David Steurer:
Rounding Semidefinite Programming Hierarchies via Global Correlation. - Venkatesan Guruswami, Ali Kemal Sinop:
Lasserre Hierarchy, Higher Eigenvalues, and Approximation Schemes for Quadratic Integer Programming with PSD Objectives. - Noga Alon, Amir Shpilka, Christopher Umans:
On Sunflowers and Matrix Multiplication. - L. Elisa Celis, Omer Reingold, Gil Segev, Udi Wieder:
Balls and Bins: Smaller Hash Families and Faster Evaluation. - Marius Zimand:
On the optimal compression of sets in PSPACE. - Eli Ben-Sasson, Michael Viderman:
Composition of semi-LTCs by two-wise Tensor Products. - Serge Gaspers, Stefan Szeider:
The Parameterized Complexity of Local Consistency. - Danny Hermelin, Xi Wu:
Weak Compositions and Their Applications to Polynomial Lower-Bounds for Kernelization. - Andrew Drucker:
Efficient Probabilistically Checkable Debates. - Ludwig Staiger:
Exact constructive dimension. - Arnab Bhattacharyya, Elena Grigorescu, Prasad Raghavendra, Asaf Shapira:
Testing Odd-Cycle-Freeness in Boolean Functions. - Eric Miles, Emanuele Viola:
The Advanced Encryption Standard, Candidate Pseudorandom Functions, and Natural Proofs. - Albert Atserias, Elitza N. Maneva:
Graph Isomorphism, Sherali-Adams Relaxations and Expressibility in Counting Logics. - Dana Ron, Gilad Tsur:
On Approximating the Number of Relevant Variables in a Function. - Eli Ben-Sasson, Elena Grigorescu, Ghid Maatouk, Amir Shpilka, Madhu Sudan:
On Sums of Locally Testable Affine Invariant Properties. - Mohammad Iftekhar Husain, Steven Y. Ko, Atri Rudra, Steve Uurtamo:
Storage Enforcement with Kolmogorov Complexity and List Decoding. - Vikraman Arvind, Partha Mukhopadhyay, Prajakta Nimbhorkar:
Erdos-Renyi Sequences and Deterministic construction of Expanding Cayley Graphs. - Miklós Ajtai:
Secure Computation with Information Leaking to an Adversary. - Eric Allender, Fengming Wang:
On the power of algebraic branching programs of width two. - Madhur Tulsiani, Julia Wolf:
Quadratic Goldreich-Levin Theorems. - Yijia Chen, Jörg Flum, Moritz Müller:
Hard instances of algorithms and proof systems. - Masaki Yamamoto:
A tighter lower bound on the circuit size of the hardest Boolean functions. - Michael Viderman:
A Combination of Testability and Decodability by Tensor Products. - Pavel Hrubes:
How much commutativity is needed to prove polynomial identities? - Paul Valiant:
Distribution Free Evolvability of Polynomial Functions over all Convex Loss Functions. - Mahdi Cheraghchi, Adam R. Klivans, Pravesh Kothari, Homin K. Lee:
Submodular Functions Are Noise Stable. - Edward A. Hirsch, Dmitry Itsykson, Valeria Nikolaenko, Alexander Smal:
Optimal heuristic algorithms for the image of an injective function. - Benjamin Doerr, Carola Winzen
:
Memory-Restricted Black-Box Complexity. - Pinyan Lu:
Complexity Dichotomies of Counting Problems. - Shachar Lovett:
Computing polynomials with few multiplications. - Christoph Behle, Andreas Krebs, Klaus-Jörn Lange, Pierre McKenzie:
Low uniform versions of NC1. - Gil Cohen, Ran Raz, Gil Segev:
Non-Malleable Extractors with Short Seeds and Applications to Privacy Amplification. - Thomas Watson:
Lift-and-Project Integrality Gaps for the Traveling Salesperson Problem. - Marek Karpinski, Richard Schmied, Claus Viehmann:
Tight Approximation Bounds for Vertex Cover on Dense k-Partite Hypergraphs. - Anant Jindal, Gazal Kochar, Manjish Pal:
Maximum Matchings via Glauber Dynamics. - Parikshit Gopalan, Cheng Huang, Huseyin Simitci, Sergey Yekhanin:
On the Locality of Codeword Symbols. - Angsheng Li, Yicheng Pan, Pan Peng:
Testing Conductance in General Graphs. - Miklós Ajtai:
Determinism Versus Nondeterminism with Arithmetic Tests and Computation. - Yang Li:
BQP and PPAD. - Or Meir:
Combinatorial PCPs with efficient verifiers. - Graham Cormode, Michael Mitzenmacher, Justin Thaler:
Streaming Graph Computations with a Helpful Advisor. - Andrew McGregor, Ilya Mironov, Toniann Pitassi, Omer Reingold, Kunal Talwar, Salil P. Vadhan:
The Limits of Two-Party Differential Privacy. - Pavol Duris:
On Computational Power of Partially Blind Automata. - Scott Aaronson:
Why Philosophers Should Care About Computational Complexity. - Zvika Brakerski, Vinod Vaikuntanathan:
Efficient Fully Homomorphic Encryption from (Standard) LWE. - Alessandro Chiesa, Michael A. Forbes:
Improved Soundness for QMA with Multiple Provers. - Zvika Brakerski, Craig Gentry, Vinod Vaikuntanathan:
Fully Homomorphic Encryption without Bootstrapping. - Dana Moshkovitz:
The Projection Games Conjecture and The NP-Hardness of ln n-Approximating Set-Cover. - Emanuele Viola:
Reducing 3XOR to listing triangles, an exposition. - Varun Kanade:
Computational Bottlenecks for Evolvability. - Varun Kanade, Thomas Steinke:
Learning Hurdles for Sleeping Experts. - Andris Ambainis, Xiaoming Sun:
New separation between s(f) and bs(f). - Andrej Bogdanov, Periklis A. Papakonstantinou, Andrew Wan:
Pseudorandomness for read-once formulas. - Brett Hemenway, Rafail Ostrovsky, Martin Strauss, Mary Wootters:
Public Key Locally Decodable Codes with Short Keys. - Subhash Khot, Preyas Popat, Nisheeth K. Vishnoi:
2log1-έn Hardness for Closest Vector Problem with Preprocessing. - Thomas Watson:
Advice Lower Bounds for the Dense Model Theorem. - Oded Goldreich, Rani Izsak:
Monotone Circuits: One-Way Functions versus Pseudorandom Generators. - Gillat Kol, Ran Raz:
Competing Provers Protocols for Circuit Evaluation. - Mark Braverman:
Interactive information complexity. - Nader H. Bshouty, Hanna Mazzawi:
Algorithms for the Coin Weighing Problems with the Presence of Noise. - Andrew Drucker:
Limitations of Lower-Bound Methods for the Wire Complexity of Boolean Operators. - Benny Applebaum, Andrej Bogdanov, Alon Rosen:
A Dichotomy for Local Small-Bias Generators. - Ronen Shaltiel:
Dispersers for affine sources with sub-polynomial entropy. - Michael Elberfeld, Andreas Jakoby, Till Tantau:
Algorithmic Meta Theorems for Circuit Classes of Constant and Logarithmic Depth. - Eli Ben-Sasson, Ariel Gabizon:
Extractors for Polynomials Sources over Constant-Size Fields of Small Characteristic. - Sergei A. Lozhkin, Alexander E. Shiganov:
On a Modification of Lupanov's Method with More Uniform Distribution of Fan-out. - Rahul Santhanam, Srikanth Srinivasan:
On the Limits of Sparsification. - Ludwig Staiger:
Oscillation-free Chaitin h-random sequences. - Maurice J. Jansen, Rahul Santhanam:
Marginal Hitting Sets Imply Super-Polynomial Lower Bounds for Permanent. - Zeev Dvir, Guillaume Malod, Sylvain Perifel, Amir Yehudayoff:
Separating multilinear branching programs and formulas. - Maurice J. Jansen, Rahul Santhanam:
Stronger Lower Bounds and Randomness-Hardness Tradeoffs using Associated Algebraic Complexity Classes. - Eran Gat, Shafi Goldwasser:
Probabilistic Search Algorithms with Unique Answers and Their Cryptographic Applications. - Vikraman Arvind, Yadu Vasudev:
Isomorphism Testing of Boolean Functions Computable by Constant Depth Circuits. - Guy Moshkovitz:
Complexity Lower Bounds through Balanced Graph Properties. - Zeev Dvir, Shachar Lovett:
Subspace Evasive Sets. - Vikraman Arvind, Partha Mukhopadhyay, Prajakta Nimbhorkar, Yadu Vasudev:
Expanding Generator Sets for Solvable Permutation Groups. - Salil P. Vadhan, Colin Jia Zheng:
Characterizing Pseudoentropy and Simplifying Pseudorandom Generator Constructions. - Boaz Barak, Parikshit Gopalan, Johan Håstad, Raghu Meka, Prasad Raghavendra, David Steurer:
Making the long code shorter, with applications to the Unique Games Conjecture. - Manindra Agrawal, Chandan Saha, Ramprasad Saptharishi, Nitin Saxena:
Jacobian hits circuits: Hitting-sets, lower bounds for depth-D occur-k formulas & depth-3 transcendence degree-k circuits. - Greg Kuperberg, Shachar Lovett, Ron Peled:
Probabilistic existence of rigid combinatorial structures. - Alexander A. Sherstov:
The Multiparty Communication Complexity of Set Disjointness. - Bireswar Das, Manjish Pal, Vijay Visavaliya:
The Entropy Influence Conjecture Revisited. - Michael A. Forbes, Amir Shpilka:
On Identity Testing of Tensors, Low-rank Recovery and Compressed Sensing. - Rohit Gurjar, Arpita Korwar, Jochen Messner, Simon Straub, Thomas Thierauf:
Planarizing Gadgets for Perfect Matching do not Exist. - Paul Beame, Chris Beck, Russell Impagliazzo:
Time-Space Tradeoffs in Resolution: Superpolynomial Lower Bounds for Superlinear Space. - 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. - Valentine Kabanets, Osamu Watanabe:
Is the Valiant-Vazirani Isolation Lemma Improvable? - Emanuele Viola:
The communication complexity of addition. - Ankit Gupta, Neeraj Kayal, Satyanarayana V. Lokam:
Reconstruction of Depth-4 Multilinear Circuits with Top fanin 2. - Klim Efremenko:
From Irreducible Representations to Locally Decodable Codes. - Anil Ada, Arkadev Chattopadhyay, Omar Fawzi, Phuong Nguyen:
The NOF Multiparty Communication Complexity of Composed Functions. - Marek Karpinski, Richard Schmied:
Improved Lower Bounds for the Shortest Superstring and Related Problems. - Eli Ben-Sasson, Shachar Lovett, Noga Zewi:
An additive combinatorics approach to the log-rank conjecture in communication complexity. - Matthew Anderson, Dieter van Melkebeek, Nicole Schweikardt, Luc Segoufin:
Locality from Circuit Lower Bounds. - Oded Goldreich, Ron Rothblum:
Enhancements of Trapdoor Permutations. - Zeev Dvir, Anup Rao, Avi Wigderson, Amir Yehudayoff:
Restriction Access. - Xin Li:
Design Extractors, Non-Malleable Condensers and Privacy Amplification. - Pavel Pudlák:
A lower bound on the size of resolution proofs of the Ramsey theorem. - Libor Barto, Marcin Kozik:
Robust Satisfiability of Constraint Satisfaction Problems. - Mark Braverman, Omri Weinstein:
A discrepancy lower bound for information complexity. - Elena Grigorescu, Chris Peikert:
List Decoding Barnes-Wall Lattices. - Xin Li:
Non-Malleable Extractors for Entropy Rate <1/2. - Nikolay K. Vereshchagin:
Improving on Gutfreund, Shaltiel, and Ta-Shma's paper "If NP Languages are Hard on the Worst-Case, Then it is Easy to Find Their Hard Instances". - Joshua A. Grochow:
Lie algebra conjugacy. - Leonid Gurvits:
Unleashing the power of Schrijver's permanental inequality with the help of the Bethe Approximation. - Constantinos Daskalakis, S. Matthew Weinberg
On Optimal Multi-Dimensional Mechanism Design. - Piotr Indyk, Reut Levi, Ronitt Rubinfeld:
Approximating and Testing k-Histogram Distributions in Sub-linear time. - Yang Cai, Constantinos Daskalakis, S. Matthew Weinberg
An Algorithmic Characterization of Multi-Dimensional Mechanisms. - Christoph Behle, Andreas Krebs:
Regular Languages in MAJ[>] with three variables. - Pavel Hrubes, Iddo Tzameret:
Short Proofs for the Determinant Identities.
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.
last updated on 2024-11-22 19:43 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by: