default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDElectronic Colloquium on Computational Complexity, 2005
Volume TR05, 2005
- Mario Szegedy:
Near optimality of the priority sampling procedure. - Magnus Bordewich, Martin E. Dyer, Marek Karpinski:
Path Coupling Using Stopping Times and Counting Independent Sets and Colourings in Hypergraphs. - Scott Aaronson:
Quantum Computing, Postselection, and Probabilistic Polynomial-Time. - Leslie G. Valiant:
Memorization and Association on a Realistic Neural Model. - Tomás Feder:
Constraint Satisfaction on Finite Groups with Near Subgroups. - Edward A. Hirsch, Sergey I. Nikolenko:
Simulating Cutting Plane proofs with restricted degree of falsity by Resolution. - Vadim Lyubashevsky:
On Random High Density Subset Sums. - Neeraj Kayal:
Recognizing permutation functions in polynomial time. - David P. Woodruff, Sergey Yekhanin:
A Geometric Approach to Information-Theoretic Private Information Retrieval. - Olivier Powell:
Almost Completeness in Small Complexity Classes. - Christian Glaßer, Mitsunori Ogihara, Aduri Pavan, Alan L. Selman, Liyu Zhang:
Autoreducibility, Mitoticity, and Immunity. - Luca Trevisan, Salil P. Vadhan, David Zuckerman:
Compression of Samplable Sources. - Bin Fu:
Theory and Application of Width Bounded Geometric Separator. - Oded Goldreich:
Short Locally Testable Codes and Proofs (Survey). - Andrej Bogdanov, Luca Trevisan:
On Worst-Case to Average-Case Reductions for NP Problems. - Tomás Feder, Daniel K. Ford:
Classification of Bipartite Boolean Constraint Satisfaction through Delta-Matroid Intersection. - Phuong Nguyen:
Two-Sorted Theories for L, SL, NL and P. - Oded Goldreich:
On Promise Problems (a survey in memory of Shimon Even [1935-2004]). - Venkatesan Guruswami, Atri Rudra:
Tolerant Locally Testable Codes. - Sourav Chakraborty:
On the Sensitivity of Cyclically-Invariant Boolean Functions. - Stasys Jukna:
Disproving the single level conjecture. - Omer Reingold, Luca Trevisan, Salil P. Vadhan:
Pseudorandom Walks in Biregular Graphs and the RL vs. L Problem. - Robert H. Sloan, Balázs Szörényi, György Turán:
On k-term DNF with largest number of prime implicants. - Michael Bauland, Elmar Böhler, Nadia Creignou, Steffen Reith, Henning Schnoor, Heribert Vollmer:
Quantified Constraints: The Complexity of Decision and Counting for Bounded Alternation. - Zeev Dvir, Ran Raz:
Analyzing Linear Mergers. - Scott Aaronson:
NP-complete Problems and Physical Reality. - Daniel Rolf:
Derandomization of PPSZ for Unique-k-SAT. - Elmar Böhler:
On the Lattice of Clones Below the Polynomial Time Functions. - Frank Neumann, Marco Laumanns:
Speeding Up Approximation Algorithms for NP-hard Spanning Forest Problems by Multi-objective Optimization. - Evgeny Dantsin, Alexander Wolpert:
An Improved Upper Bound for SAT. - Carme Àlvarez, Joaquim Gabarró, Maria J. Serna:
Pure Nash equilibria in games with a large number of actions. - Gudmund Skovbjerg Frandsen, Peter Bro Miltersen:
Reviewing Bounds on the Circuit Size of the Hardest Functions. - Martin Fürer, Shiva Prasad Kasiviswanathan:
Algorithms for Counting 2-SAT Solutions and Colorings with Applications. - Luca Trevisan:
Approximation Algorithms for Unique Games. - Christian Glaßer, Stephen D. Travers, Klaus W. Wagner:
A Reducibility that Corresponds to Unbalanced Leaf-Language Classes. - Hubie Chen:
Quantified Constraint Satisfaction, Maximal Constraint Languages, and Symmetric Polymorphisms. - Eric Allender, Peter Bürgisser, Johan Kjeldgaard-Pedersen, Peter Bro Miltersen:
On the Complexity of Numerical Analysis. - Ran Raz:
Quantum Information and the PCP Theorem. - Irit Dinur, Elchanan Mossel, Oded Regev:
Conditional Hardness for Approximate Coloring. - Scott Aaronson:
Oracles Are Subtle But Not Malicious. - Shengyu Zhang:
(Almost) tight bounds for randomized and quantum Local Search on hypercubes and grids. - Lance Fortnow, Adam R. Klivans:
Linear Advice for Randomized Logarithmic Space. - Emanuele Viola:
Pseudorandom Bits for Constant-Depth Circuits with Few Arbitrary Symmetric Gates. - Zeev Dvir, Amir Shpilka:
Locally Decodable Codes with 2 queries and Polynomial Identity Testing for depth 3 circuits. - Philippe Moser:
Martingale Families and Dimension in P. - Irit Dinur:
The PCP theorem by gap amplification. - Kooshiar Azimian, Mahmoud Salmasizadeh, Javad Mohajeri:
Weak Composite Diffie-Hellman is not Weaker than Factoring. - Moti Yung, Yunlei Zhao:
Constant-Round Concurrently-Secure rZK in the (Real) Bare Public-Key Model. - Joan Boyar, René Peralta:
The Exact Multiplicative Complexity of the Hamming Weight Function. - Uriel Feige, Eran Ofek:
Finding a Maximum Independent Set in a Sparse Random Graph. - Predrag T. Tosic:
On Complexity of Counting Fixed Points in Certain Classes of Graph Automata. - Grant Schoenebeck, Salil P. Vadhan:
The Computational Complexity of Nash Equilibria in Concisely Represented Games. - Paul Beame, Toniann Pitassi, Nathan Segerlind:
Lower bounds for Lovasz-Schrijver systems and beyond follow from multiparty communication complexity. - Konstantin Pervyshev:
Time Hierarchies for Computations with a Bit of Advice. - Bruno Codenotti, Amin Saberi, Kasturi R. Varadarajan, Yinyu Ye:
Leontief Economies Encode Nonzero Sum Two-Player Games. - Alexis C. Kaporis, Efpraxia I. Politopoulou, Paul G. Spirakis:
The Price of Optimum in Stackelberg Games. - Venkatesan Guruswami, Valentine Kabanets:
Hardness amplification via space-efficient direct products. - Sanjeev Arora, Eli Berger, Elad Hazan, Guy Kindler, Muli Safra
:
On Non-Approximability for Quadratic Programs. - Víctor Dalmau, Ricard Gavaldà, Pascal Tesson, Denis Thérien:
Tractable Clones of Polynomials over Semigroups. - Philippe Moser:
Generic Density and Small Span Theorem. - Ronen Gradwohl, Guy Kindler, Omer Reingold, Amnon Ta-Shma:
On the Error Parameter of Dispersers. - Aduri Pavan, N. V. Vinodchandran:
2-Local Random Reductions to 3-Valued Functions. - Bodo Manthey, Rüdiger Reischuk:
Smoothed Analysis of the Height of Binary Search Trees. - Howard J. Karloff, Subhash Khot, Aranyak Mehta, Yuval Rabani:
On earthmover distance, metric labeling, and 0-extension. - Alexander I. Barvinok, Alex Samorodnitsky:
Random Weighting, Asymptotic Counting, and Inverse Isoperimetry. - Jakob Nordström:
Narrow Proofs May Be Spacious: Separating Space and Width in Resolution. - Zeev Dvir, Amir Shpilka:
An Improved Analysis of Mergers. - Christian Glaßer, Aduri Pavan, Alan L. Selman, Liyu Zhang:
Redundancy in Complete Sets. - Piotr Berman, Marek Karpinski:
8/7-Approximation Algorithm for (1,2)-TSP. - Mahdi Cheraghchi:
On Matrix Rigidity and the Complexity of Linear Forms. - Marius Zimand:
Simple extractors via constructions of cryptographic pseudo-random generators. - Christian Glaßer, Alan L. Selman, Liyu Zhang:
Survey of Disjoint NP-Pairs and Relations to Propositional Proof Systems. - Oded Goldreich, Dana Ron:
Approximating Average Parameters of Graphs. - Li-Sha Huang, Xiaotie Deng:
On Complexity of Market Equilibria with Maximum Social Welfare. - Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum:
Dobrushin conditions and Systematic Scan. - Dima Grigoriev, Edward A. Hirsch, Konstantin Pervyshev:
Time hierarchies for cryptographic function inversion with advice. - Zenon Sadowski:
On a D-N-optimal acceptor for TAUT. - Kooshiar Azimian, Javad Mohajeri, Mahmoud Salmasizadeh, Siamak Fayyaz Shahandashti:
A Verifiable Partial Key Escrow, Based on McCurley Encryption Scheme. - Stasys Jukna:
Expanders and time-restricted branching programs. - Michael R. Fellows, Frances A. Rosamond, Udi Rotics, Stefan Szeider:
Proving NP-hardness for clique-width I: non-approximability of sequential clique-width. - Michael R. Fellows, Frances A. Rosamond, Udi Rotics, Stefan Szeider:
Proving NP-hardness for clique-width II: non-approximability of clique-width. - Jorge Castro:
On the Query Complexity of Quantum Learners. - Olaf Beyersdorff:
Disjoint NP-Pairs from Propositional Proof Systems. - Mickey Brautbar, Alex Samorodnitsky:
Approximating the entropy of large alphabets. - Asaf Shapira, Noga Alon:
Homomorphisms in Graph Property Testing - A Survey. - Dana Moshkovitz, Ran Raz:
Sub-Constant Error Low Degree Test of Almost Linear Size. - Alexander Healy, Emanuele Viola:
Constant-Depth Circuits for Arithmetic in Finite Fields of Characteristic Two. - Jan Arpe:
Learning Juntas in the Presence of Noise. - Xiaoyang Gu, Jack H. Lutz, Philippe Moser:
Dimensions of Copeland-Erdös Sequences. - Paul W. Goldberg, Christos H. Papadimitriou:
Reducibility Among Equilibrium Problems. - Predrag T. Tosic:
Counting Fixed Points and Gardens of Eden of Sequential Dynamical Systems on Planar Bipartite Graphs. - Eyal Rozenman, Salil P. Vadhan:
Derandomized Squaring of Graphs. - Daniele Micciancio, Shien Jin Ong, Amit Sahai, Salil P. Vadhan:
Concurrent Zero Knowledge without Complexity Assumptions. - Michal Parnas, Dana Ron:
On Approximating the Minimum Vertex Cover in Sublinear Time and the Connection to Distributed Algorithms. - Noga Alon, Ilan Newman, Alexander Shen, Gábor Tardos, Nikolai K. Vereshchagin:
Partitioning multi-dimensional sets in a small number of "uniform" parts. - Boaz Barak, Amit Sahai:
How To Play Almost Any Mental Game Over The Net - Concurrent Composition via Super-Polynomial Simulation. - Jens Groth, Rafail Ostrovsky, Amit Sahai:
Perfect Non-Interactive Zero Knowledge for NP. - Oded Goldreich:
Bravely, Moderately: A Common Theme in Four Recent Results. - Leslie G. Valiant:
Holographic Algorithms. - David Zuckerman:
Linear Degree Extractors and the Inapproximability of Max Clique and Chromatic Number. - Guy Kindler, Ryan O'Donnell, Subhash Khot, Elchanan Mossel:
Optimal Inapproximability Results for MAX-CUT and Other 2-Variable CSPs? - Evgeny Dantsin, Edward A. Hirsch, Alexander Wolpert:
Clause Shortening Combined with Pruning Yields a New Upper Bound for Deterministic SAT Algorithms. - Leonid Gurvits:
A proof of hyperbolic van der Waerden conjecture : the right generalization is the ultimate simplification. - Don Coppersmith, Atri Rudra:
On the Robust Testability of Product of Codes. - Lance Fortnow, John M. Hitchcock, Aduri Pavan, N. V. Vinodchandran, Fengming Wang:
Extracting Kolmogorov Complexity with Applications to Dimension Zero-One Laws. - Anup Rao:
Extractors for a Constant Number of Polynomial Min-Entropy Independent Sources. - Avi Wigderson, David Xiao:
A Randomness-Efficient Sampler for Matrix-valued Functions and Applications. - Ariel Gabizon, Ran Raz:
Deterministic Extractors for Affine Sources over Large Fields. - Ariel Gabizon, Ran Raz, Ronen Shaltiel:
Deterministic Extractors for Bit-fixing Sources by Obtaining an Independent Seed. - Saurabh Sanghvi, Salil P. Vadhan:
The Round Complexity of Two-Party Random Selection. - Dieter van Melkebeek, Konstantin Pervyshev:
A Generic Time Hierarchy for Semantic Models With One Bit of Advice. - Eran Ofek:
On the expansion of the giant component in percolated (n,d,lambda) graphs. - Bernhard Fuchs:
On the Hardness of Range Assignment Problems. - Boaz Barak, Shien Jin Ong, Salil P. Vadhan:
Derandomization in Cryptography. - Konstantinos Daskalakis, Paul W. Goldberg, Christos H. Papadimitriou:
The complexity of computing a Nash equilibrium. - Alex Samorodnitsky, Luca Trevisan:
Gowers Uniformity, Influence of Variables, and PCPs. - Piotr Indyk, David P. Woodruff:
Polylogarithmic Private Approximations and Efficient Matching. - Jin-yi Cai, Vinay Choudhary:
Valiant's Holant Theorem and Matchgate Tensors. - Nadia Creignou, Phokion G. Kolaitis, Bruno Zanuttini:
Preferred representations of Boolean relations. - Sashka Davis, Russell Impagliazzo:
Models of Greedy Algorithms for Graph Problems. - Martin E. Dyer, Leslie Ann Goldberg, Mike Paterson:
On counting homomorphisms to directed acyclic graphs. - Pavel Pudlák:
A nonlinear bound on the number of wires in bounded depth circuits. - Olaf Beyersdorff:
Tuples of Disjoint NP-Sets. - Kooshiar Azimian:
Breaking Diffie-Hellman is no Easier than Root Finding. - Sofya Raskhodnikova, Dana Ron, Ronitt Rubinfeld, Amir Shpilka, Adam D. Smith:
Sublinear Algorithms for Approximating String Compressibility and the Distribution Support Size. - Eric Allender, Lisa Hellerstein, Paul McCabe, Toniann Pitassi, Michael E. Saks:
Minimizing DNF Formulas and AC0 Circuits Given a Truth Table. - Vitaly Feldman:
Hardness of Approximate Two-level Logic Minimization and PAC Learning with Membership Queries. - Miroslava Sotáková:
The normal form of reversible circuits consisting of CNOT and NOT gates. - Scott Aaronson:
QMA/qpoly Is Contained In PSPACE/poly: De-Merlinizing Quantum Protocols. - Ahuva Mu'alem:
A Note on Testing Truthfulness. - Don Coppersmith, Lisa Fleischer, Atri Rudra:
Ordering by weighted number of wins gives a good ranking for weighted tournaments. - Venkatesan Guruswami:
Algebraic-geometric generalizations of the Parvaresh-Vardy codes. - Venkatesan Guruswami, Atri Rudra:
Explicit Capacity-Achieving List-Decodable Codes.