default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDElectronic Colloquium on Computational Complexity, 2010
Volume TR10, 2010
- Iftach Haitner, Mohammad Mahmoody, David Xiao:
A New Sampling Protocol and Applications to Basing Cryptographic Primitives on the Hardness of NP. - Ran Raz:
Tensor-Rank and Lower Bounds for Arithmetic Formulas. - Venkatesan Guruswami, Johan Håstad, Swastik Kopparty:
On the List-Decodability of Random Linear Codes. - Eli Ben-Sasson, Michael Viderman:
Low Rate Is Insufficient for Local Testability. - Haitao Jiang, Binhai Zhu:
Weak Kernels. - Yi Wu, Ryan O'Donnell, David Zuckerman, Parikshit Gopalan:
Fooling functions of halfspaces under product distributions. - Atri Rudra, Steve Uurtamo:
Two Theorems in List Decoding. - Yijia Chen, Jörg Flum:
On optimal proof systems and logics for PTIME. - Aduri Pavan, Raghunath Tewari, N. V. Vinodchandran:
On the Power of Unambiguity in Logspace. - Shachar Lovett:
Equivalence of polynomial conjectures in additive combinatorics. - Amir Shpilka, Ilya Volkovich:
Read-Once Polynomial Identity Testing. - Zeev Dvir, Parikshit Gopalan, Sergey Yekhanin:
Matching Vector Codes. - Nitin Saxena, C. Seshadhri:
From Sylvester-Gallai Configurations to Rank Bounds: Improved Black-box Identity Test for Depth-3 Circuits. - Daniele Micciancio, Panagiotis Voulgaris:
A Deterministic Single Exponential Time Algorithm for Most Lattice Problems based on Voronoi Cell Computations. - Maurice J. Jansen, Youming Qiao, Jayalal Sarma:
Deterministic Black-Box Identity Testing pi-Ordered Algebraic Branching Programs. - Alexander Fanghänel, Sascha Geulen, Martin Hoefer, Berthold Vöcking:
Online Capacity Maximization in Wireless Networks. - Jonathan R. Ullman, Salil P. Vadhan:
PCPs and the Hardness of Generating Synthetic Data. - Vitaly Feldman:
A Complete Characterization of Statistical Query Learning with Applications to Evolvability. - Andrew Drucker:
A PCP Characterization of AM. - Vipul Goyal, Yuval Ishai, Mohammad Mahmoody, Amit Sahai:
Interactive Locking, Zero-Knowledge PCPs, and Unconditional Cryptography. - Pavel Hrubes, Avi Wigderson, Amir Yehudayoff:
Non-commutative circuits and the sum-of-squares problem. - Vitaly Feldman, Homin K. Lee, Rocco A. Servedio:
Lower Bounds and Hardness Amplification for Learning Shallow Monotone Formulas. - Adam R. Klivans, Homin K. Lee, Andrew Wan:
Mansour's Conjecture is True for Random DNF Formulas. - Henning Wunderlich, Stefan Arnold:
On a singular value method in quantum communication complexity. - Alexander A. Sherstov:
Optimal bounds for sign-representing the intersection of two halfspaces by polynomials. - Hao Huang, Benny Sudakov:
A counterexample to the Alon-Saks-Seymour conjecture and related problems. - Arnab Bhattacharyya, Eldar Fischer, Ronitt Rubinfeld, Paul Valiant:
Testing monotonicity of distributions over general partial orders. - Miklós Ajtai:
Oblivious RAMs without Cryptographic Assumptions. - Alexandra Kolla:
Spectral Algorithms for Unique Games. - Airat Khasianov:
Stronger Lower Bounds on Quantum OBDD for the Hidden Subgroup Problem. - Christian Glaßer, Christian Reitwießner, Heinz Schmitz, Maximilian Witek:
Hardness and Approximability in Multi-Objective Optimization. - Jack H. Lutz, Brad Shutters:
Approximate Self-Assembly of the Sierpinski Triangle. - Shachar Lovett, Partha Mukhopadhyay, Amir Shpilka:
Pseudorandom generators for CC0[p] and the Fourier spectrum of low-degree polynomials over finite fields. - Luca Trevisan:
The Program-Enumeration Bottleneck in Average-Case Complexity Theory. - Mark Braverman, Anup Rao, Ran Raz, Amir Yehudayoff:
Pseudorandom Generators for Regular Branching Programs. - Amir Shpilka, Ilya Volkovich:
On the Relation between Polynomial Identity Testing and Finding Variable Disjoint Factors. - Boaz Barak, Guy Kindler, Ronen Shaltiel, Benny Sudakov, Avi Wigderson:
Simulating Independence: New Constructions of Condensers, Ramsey Graphs, Dispersers, and Extractors. - Dieter van Melkebeek, Holger Dell:
Satisfiability Allows No Nontrivial Sparsification Unless The Polynomial-Time Hierarchy Collapses. - Gil Cohen, Amir Shpilka:
On the degree of symmetric functions on the Boolean cube. - Pavel Hrubes, Avi Wigderson, Amir Yehudayoff:
Relationless completeness and separations. - Sanjeev Arora, Russell Impagliazzo, William Matthews, David Steurer:
Improved Algorithms for Unique Games via Divide and Conquer. - Thomas Watson:
Relativized Worlds Without Worst-Case to Average-Case Reductions for NP. - Johannes Köbler, Sebastian Kuhnert, Bastian Laubner, Oleg Verbitsky:
Interval Graphs: Canonical Representation in Logspace. - Eli Ben-Sasson, Swastik Kopparty:
Affine Dispersers from Subspace Polynomials. - Jakob Nordström:
On the Relative Strength of Pebbling and Resolution. - Ján Pich:
Nisan-Wigderson generators in proof systems with forms of interpolation. - Avraham Ben-Aroya, Klim Efremenko, Amnon Ta-Shma:
Local list decoding with a constant number of queries. - David García-Soriano, Arie Matsliah, Sourav Chakraborty, Jop Briët:
Monotonicity Testing and Shortest-Path Routing on the Cube. - Alexey Pospelov:
Bounds for Bilinear Complexity of Noncommutative Group Algebras. - Samir Datta, Prajakta Nimbhorkar, Thomas Thierauf, Fabian Wagner:
Graph Isomorphism for K3,3-free and K5-free graphs is in Log-space. - Madhu Sudan:
Invariance in Property Testing. - Melanie Winkler, Berthold Vöcking, Sascha Geulen:
Regret Minimization for Online Buffering Problems Using the Weighted Majority Algorithm. - Dana Moshkovitz, Subhash Khot:
Hardness of Approximately Solving Linear Equations Over Reals. - Jan Krajícek:
On the proof complexity of the Nisan-Wigderson generator based on a hard NP cap coNP function. - Eric Allender:
Avoiding Simplicity is Complex. - Kord Eickmeyer, Martin Grohe:
Randomisation and Derandomisation in Descriptive Complexity Theory. - Scott Aaronson, Andrew Drucker:
A Full Characterization of Quantum Advice. - Oded Goldreich, Tali Kaufman:
Proximity Oblivious Testing and the Role of Invariances. - Olaf Beyersdorff, Nicola Galesi, Massimo Lauria:
Hardness of Parameterized Resolution. - Dmitry Gavinsky, Alexander A. Sherstov:
A Separation of NP and coNP in Multiparty Communication Complexity. - Oded Goldreich:
On Testing Computability by Small Width OBDDs. - Michael Elberfeld, Andreas Jakoby, Till Tantau:
Logspace Versions of the Theorems of Bodlaender and Courcelle. - Venkatesan Guruswami, Yuan Zhou:
Tight Bounds on the Approximability of Almost-satisfiable Horn SAT and Exact Hitting Set}. - Xin Li:
A New Approach to Affine Extractors and Dispersers. - Tali Kaufman, Shachar Lovett:
Testing of exponentially large codes, by a new extension to Weil bound for character sums. - Sanjeev Arora, Rong Ge:
Learning Parities with Structured Noise. - Sourav Chakraborty, Eldar Fischer, Arie Matsliah:
Query Complexity Lower Bounds for Reconstruction of Codes. - Shir Ben-Israel, Eli Ben-Sasson, David R. Karger:
Breaking local symmetries can dramatically reduce the length of propositional refutations. - Eric Allender, Vikraman Arvind, Fengming Wang:
Uniform Derandomization from Pathetic Lower Bounds. - Eric Allender, Klaus-Jörn Lange:
Symmetry Coincides with Nondeterminism for Time-Bounded Auxiliary Pushdown Automata. - Rahul Jain, Ashwin Nayak:
The space complexity of recognizing well-parenthesized expressions. - Russell Impagliazzo, Valentine Kabanets:
Constructive Proofs of Concentration Bounds. - Neeraj Kayal:
Algorithms for Arithmetic Circuits. - Parikshit Gopalan, Rocco A. Servedio:
Learning and Lower Bounds for AC0 with Threshold Gates. - Ben Reichardt:
Least span program witness size equals the general adversary lower bound on quantum query complexity. - Amit Chakrabarti, Graham Cormode, Ranganath Kondapally, Andrew McGregor:
Information Cost Tradeoffs for Augmented Index and Streaming Language Recognition. - Venkatesan Guruswami, Adam D. Smith:
Codes for Computationally Simple Channels: Explicit Constructions with Optimal Rate. - Holger Dell, Thore Husfeldt, Martin Wahlen:
Exponential Time Complexity of the Permanent and the Tutte Polynomial. - Samir Datta, Raghav Kulkarni, Raghunath Tewari, N. V. Vinodchandran:
Space Complexity of Perfect Matching in Bounded Genus Bipartite Graphs. - Andrew Drucker:
Improved Direct Product Theorems for Randomized Query Complexity. - Olaf Beyersdorff, Nicola Galesi, Massimo Lauria:
A Lower Bound for the Pigeonhole Principle in Tree-like Resolution by Asymmetric Prover-Delayer Games. - Oded Goldreich:
Introduction to Testing Graph Properties. - Mark Braverman, Anup Rao:
Efficient Communication Using Partial Information. - Maurice J. Jansen, Youming Qiao, Jayalal Sarma:
Deterministic Identity Testing of Read-Once Algebraic Branching Programs. - Eli Ben-Sasson, Jan Johannsen:
Lower bounds for width-restricted clause learning on small width formulas. - Henning Wunderlich:
On a Theorem of Razborov. - Shachar Lovett, Ely Porat:
A lower bound for dynamic approximate membership data structures. - Jirí Síma, Stanislav Zák:
A Polynomial Time Construction of a Hitting Set for Read-Once Branching Programs of Width 3. - Iftach Haitner, Omer Reingold, Salil P. Vadhan:
Efficiency Improvements in Constructing Pseudorandom Generators from One-way Functions. - Nikolay K. Vereshchagin:
Algorithmic Minimal Sufficient Statistics: a New Definition. - Nikolay K. Vereshchagin:
An Encoding Invariant Version of Polynomial Time Computable Distributions. - Charanjit S. Jutla, Arnab Roy:
A Completeness Theorem for Pseudo-Linear Functions with Applications to UC Security. - Sourav Chakraborty, David García-Soriano, Arie Matsliah:
Nearly Tight Bounds for Testing Function Isomorphism. - Ajesh Babu, Nutan Limaye, Girish Varma:
Streaming algorithms for some problems in log-space. - Masaki Yamamoto:
A combinatorial analysis for the critical clause tree. - Dana Moshkovitz:
An Alternative Proof of The Schwartz-Zippel Lemma. - Iddo Tzameret:
Algebraic Proofs over Noncommutative Formulas. - Daniel M. Kane, Jelani Nelson:
A Derandomized Sparse Johnson-Lindenstrauss Transform. - T. C. Vijayaraghavan:
A Note on Closure Properties of ModL. - Amit Chakrabarti:
A Note on Randomized Streaming Space Bounds for the Longest Increasing Subsequence Problem. - Samir Datta, Meena Mahajan, B. V. Raghavendra Rao, Michael Thomas, Heribert Vollmer:
Counting Classes and the Fine Structure between NC1 and L. - Per Kristian Lehre, Carsten Witt:
Black-Box Search by Unbiased Variation. - Andreas Krebs, Nutan Limaye, Meena Mahajan:
Counting paths in VPA is complete for #NC1. - Paul Beame, Widad Machmouchi:
Making RAMs Oblivious Requires Superlogarithmic Overhead. - Scott Aaronson, Dieter van Melkebeek:
A note on circuit lower bounds from derandomization. - Yuichi Yoshida:
Optimal Constant-Time Approximation Algorithms and (Unconditional) Inapproximability Results for Every Bounded-Degree CSP. - Irit Dinur, Or Meir:
Derandomized Parallel Repetition via Structured PCPs. - Eli Ben-Sasson, Madhu Sudan:
Limits on the rate of locally testable affine-invariant codes. - Scott Aaronson:
A Counterexample to the Generalized Linial-Nisan Conjecture. - Ben Reichardt:
Span programs and quantum query algorithms. - Venkatesan Guruswami, Ali Kemal Sinop:
The complexity of finding independent sets in bounded degree (hyper)graphs of low chromatic number. - Subhash Khot, Dana Moshkovitz:
NP-Hardness of Approximately Solving Linear Equations Over Reals. - Michal Koucký, Prajakta Nimbhorkar, Pavel Pudlák:
Pseudorandom Generators for Group Products. - Zhixiang Chen, Bin Fu:
The Complexity of Testing Monomials in Multivariate Polynomials. - Shachar Lovett, Emanuele Viola:
Bounded-depth circuits cannot sample good codes. - Arnab Bhattacharyya, Victor Chen, Madhu Sudan, Ning Xie:
Testing linear-invariant non-linear properties: A short report. - Arkadev Chattopadhyay, Jacobo Torán, Fabian Wagner:
Graph Isomorphism is not AC^0 reducible to Group Isomorphism. - Maurice J. Jansen:
Extracting Roots of Arithmetic Circuits by Adapting Numerical Methods. - Michal Moshkovitz:
Distance Estimators with Sublogarithmic Number of Queries. - Noa Eidelstein, Alex Samorodnitsky:
Lower bounds for designs in symmetric spaces. - Ashwin Nayak:
Inverting a permutation is as hard as unordered search. - Zhixiang Chen, Bin Fu, Yang Liu, Robert T. Schweller:
Algorithms for Testing Monomials in Multivariate Polynomials. - Eli Ben-Sasson:
Limitation on the rate of families of locally testable codes. - Zhixiang Chen, Bin Fu:
Approximating Multilinear Monomial Coefficients and Maximum Multilinear Monomials in Multivariate Polynomials. - Eli Ben-Sasson, Jakob Nordström:
Understanding Space in Proof Complexity: Separations and Trade-offs via Substitutions. - Thomas Watson:
Query Complexity in Errorless Hardness Amplification. - Brett Hemenway, Rafail Ostrovsky:
Building Injective Trapdoor Functions From Oblivious Transfer. - Scott Aaronson:
The Equivalence of Sampling and Searching. - Jeff Kinne, Dieter van Melkebeek, Ronen Shaltiel:
Pseudorandom Generators, Typically-Correct Derandomization, and Circuit Lower Bounds. - Tali Kaufman, Michael Viderman:
Locally Testable vs. Locally Decodable Codes. - Nathaniel Bryans, Ehsan Chiniforooshan, David Doty, Lila Kari, Shinnosuke Seki:
The Power of Nondeterminism in Self-Assembly. - Mahdi Cheraghchi, Johan Håstad, Marcus Isaksson, Ola Svensson:
Approximating Linear Threshold Predicates. - Parikshit Gopalan, Adam R. Klivans, Raghu Meka:
Polynomial-Time Approximation Schemes for Knapsack and Related Counting Problems using Branching Programs. - Avraham Ben-Aroya, Klim Efremenko, Amnon Ta-Shma:
A Note on Amplifying the Error-Tolerance of Locally Decodable Codes. - Oded Goldreich:
In a World of P=BPP. - Arnab Bhattacharyya, Elena Grigorescu, Jakob Nordström, Ning Xie:
Separations of Matroid Freeness Properties. - Or Meir:
IP = PSPACE using Error Correcting Codes. - Eric Allender, Luke Friedman, William I. Gasarch:
Exposition of the Muchnik-Positselsky Construction of a Prefix Free Entropy Function that is not Complete under Truth-Table Reductions. - Eric Allender, Luke Friedman, William I. Gasarch:
Limits on the Computational Power of Random Strings. - Amit Chakrabarti, Oded Regev:
An Optimal Lower Bound on the Communication Complexity of Gap-Hamming-Distance. - (Withdrawn) A Strong Parallel Repetition Theorem for Projection Games on Expanders.
- Ran Raz, Ricky Rosen:
A Strong Parallel Repetition Theorem for Projection Games on Expanders. - Bo'az Klartag, Oded Regev:
Quantum One-Way Communication is Exponentially Stronger Than Classical Communication. - Eli Ben-Sasson, Noga Zewi:
From Affine to Two-Source Extractors via Approximate Duality. - Ron Rothblum:
A Taxonomy of Enhanced Trapdoor Permutations. - Ron Rothblum:
Homomorphic Encryption: from Private-Key to Public-Key. - Dieter van Melkebeek, Thomas Watson:
Time-Space Efficient Simulations of Quantum Computations. - Swastik Kopparty, Shubhangi Saraf, Sergey Yekhanin:
High-rate codes with sublinear-time decoding. - Boaz Barak, Zeev Dvir, Avi Wigderson, Amir Yehudayoff:
Rank Bounds for Design Matrices with Applications to Combinatorial Geometry and Locally Correctable Codes. - Bjørn Kjos-Hanssen:
A strong law of computationally weak subsets. - Raghunath Tewari, N. V. Vinodchandran:
Green's Theorem and Isolation in Planar Graphs. - Alexey Pospelov:
Faster Polynomial Multiplication via Discrete Fourier Transforms. - Lorenzo Carlucci, Nicola Galesi, Massimo Lauria:
Paris-Harrington tautologies. - Derrick Stolee, N. V. Vinodchandran:
Space-Efficient Algorithms for Reachability in Surface-Embedded Graphs. - Brendan Juba, Madhu Sudan:
Efficient Semantic Communication via Compatible Beliefs. - Victor Chen, Madhu Sudan, Ning Xie:
Property Testing via Set-Theoretic Operations. - Reut Levi, Dana Ron, Ronitt Rubinfeld:
Testing Properties of Collections of Distributions. - Shiva Kintali:
Realizable Paths and the NL vs L Problem. - Graham Cormode, Justin Thaler, Ke Yi:
Verifying Computations with Streaming Interactive Proofs. - Zeev Dvir, Dan Gutfreund, Guy N. Rothblum, Salil P. Vadhan:
On Approximating the Entropy of Polynomial Mappings. - Arnab Bhattacharyya, Elena Grigorescu, Asaf Shapira:
A Unified Framework for Testing Linear-Invariant Properties. - Zohar Shay Karnin:
Deterministic Construction of a high dimensional lp section in l1n for any p<2. - Harry Buhrman, Leen Torenvliet, Falk Unger, Nikolai K. Vereshchagin:
Sparse Selfreducible Sets and Nonuniform Lower Bounds. - Falk Unger:
Better gates can make fault-tolerant computation impossible. - Dmitry Gavinsky, Tsuyoshi Ito:
Quantum Fingerprints that Keep Secrets. - Mark Braverman, Anup Rao:
Towards Coding for Maximum Errors in Interactive Communication. - Nitin Saxena, C. Seshadhri:
Blackbox identity testing for bounded top fanin depth-3 circuits: the field doesn't matter. - Thomas Watson:
Pseudorandom Generators for Combinatorial Checkerboards. - Siavosh Benabbas, Konstantinos Georgiou, Avner Magen:
The Sherali-Adams System Applied to Vertex Cover: Why Borsuk Graphs Fool Strong LPs and some Tight Integrality Gaps for SDPs. - Scott Aaronson, Alex Arkhipov:
The Computational Complexity of Linear Optics. - Michael Viderman:
A Note on high-rate Locally Testable Codes with sublinear query complexity. - Prasad Raghavendra, David Steurer, Madhur Tulsiani:
Reductions Between Expansion Problems. - Yeow Meng Chee, Tao Feng, San Ling, Huaxiong Wang, Liang Feng Zhang:
Query-Efficient Locally Decodable Codes. - Scott Aaronson, Baris Aydinlioglu, Harry Buhrman, John M. Hitchcock, Dieter van Melkebeek:
A note on exponential circuit lower bounds from derandomizing Arthur-Merlin games. - Emanuele Viola:
Randomness buys depth for approximate counting. - Parikshit Gopalan, Raghu Meka, Omer Reingold, David Zuckerman:
Pseudorandom Generators for Combinatorial Shapes. - Venkatesan Guruswami, Prasad Raghavendra, Rishi Saket, Yi Wu:
Bypassing UGC from some optimal geometric inapproximability results. - Amir Shpilka, Avishay Tal:
On the Minimal Fourier Degree of Symmetric Boolean Functions. - Gregory Valiant, Paul Valiant:
A CLT and tight lower bounds for estimating entropy. - Gregory Valiant, Paul Valiant:
Estimating the unseen: A sublinear-sample canonical estimator of distributions. - Hamed Hatami, Shachar Lovett:
Higher-order Fourier analysis of Fpn and the complexity of systems of linear forms. - Shachar Lovett:
An elementary proof of anti-concentration of polynomials in Gaussian variables. - Daniel Kane, Raghu Meka, Jelani Nelson:
Almost Optimal Explicit Johnson-Lindenstrauss Transformations. - Manish Pal:
Combinatorial Geometry of Graph Partitioning - I. - Vitaly Feldman, Venkatesan Guruswami, Prasad Raghavendra, Yi Wu:
Agnostic Learning of Monomials by Halfspaces is Hard. - Bill Fefferman, Ronen Shaltiel, Christopher Umans, Emanuele Viola:
On beating the hybrid argument. - Gus Gutoski:
Interactive proofs with competing teams of no-signaling provers. - Matthew Anderson, Dieter van Melkebeek, Ilya Volkovich:
Derandomizing Polynomial Identity Testing for Multilinear Constant-Read Formulae. - Neeraj Kayal, Chandan Saha:
On the Sum of Square Roots of Polynomials and related problems. - Xin Li:
Improved Constructions of Three Source Extractors. - Andris Ambainis, Loïck Magnin, Martin Roetteler, Jérémie Roland:
Symmetry-assisted adversaries for quantum state generation. - Frédéric Magniez, Ashwin Nayak, Miklos Santha, David Xiao:
Improved bounds for the randomized decision tree complexity of recursive majority. - Edward A. Hirsch, Dmitry Itsykson, Ivan Monakhov, Alexander Smal:
On optimal heuristic randomized semidecision procedures, with applications to proof complexity and cryptography. - Thanh Minh Hoang:
Isolation of Matchings via Chinese Remaindering. - Ho-Lin Chen, David Doty, Shinnosuke Seki, David Soloveichik:
Parallelism, Program Size, Time, and Temperature in Self-Assembly. - Bin Fu:
NE is not NP Turing Reducible to Nonexpoentially Dense NP Sets. - Albert Atserias, Elitza N. Maneva:
Mean-payoff games and propositional proofs. - Olaf Beyersdorff, Nicola Galesi, Massimo Lauria, Alexander A. Razborov:
Parameterized Bounded-Depth Frege is Not Optimal. - Eli Ben-Sasson, Ghid Maatouk, Amir Shpilka, Madhu Sudan:
Symmetric LDPC codes are not necessarily locally testable. - Eli Ben-Sasson, Michael Viderman:
Towards lower bounds on locally testable codes via density arguments. - Samir Datta, Raghav Kulkarni, Raghunath Tewari:
Perfect Matching in Bipartite Planar Graphs is in UL. - Bin Fu:
Multivariate Polynomial Integration and Derivative Are Polynomial Time Inapproximable unless P=NP.
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 2025-04-21 19:01 CEST 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:
