default search action
Electronic 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. - Xi Chen, Xiaotie Deng:
3-NASH is PPAD-Complete. - Iftach Haitner, Danny Harnik, Omer Reingold:
On the Power of the Randomized Iterate. - Anna Gál, Michal Koucký, Pierre McKenzie:
Incremental branching programs. - Emanuele Viola:
On Probabilistic Time versus Alternating Time. - Peter Bürgisser, Felipe Cucker:
Exotic quantifiers, complexity classes, and complete problems. - Konstantinos Daskalakis, Christos H. Papadimitriou:
Three-Player Games Are Hard. - Xi Chen, Xiaotie Deng:
Settling the Complexity of 2-Player Nash-Equilibrium. - Amos Beimel, Paz Carmi, Kobbi Nissim, Enav Weinreb:
Private Approximation of Search Problems. - Vadim Lyubashevsky, Daniele Micciancio:
Generalized Compact Knapsacks are Collision Resistant. - Parikshit Gopalan:
Constructing Ramsey Graphs from Boolean Function Representations. - Lance Fortnow, Luis Antunes:
Time-Bounded Universal Distributions. - Ronen Shaltiel:
How to get more mileage from randomness extractors. - Gábor Erdélyi, Tobias Riege, Jörg Rothe:
Quantum Cryptography: A Survey. - Christian Glaßer, Stephen D. Travers:
Machines that can Output Empty Words. - Eric Allender, Samir Datta, Sambuddha Roy:
The Directed Planar Reachability Problem. - Eric Allender, David A. Mix Barrington, Tanmoy Chakraborty, Samir Datta, Sambuddha Roy:
Grid Graph Reachability Problems. - Neeraj Kayal, Nitin Saxena:
Polynomial Identity Testing for Depth 3 Circuits. - Magnus Bordewich, Martin E. Dyer, Marek Karpinski:
Metric Construction, Stopping Times and Path Coupling. - Oded Lachish, Ilan Newman:
Languages that are Recognized by Simple Counter Automata are not necessarily Testable. - Shirley Halevy, Oded Lachish, Ilan Newman, Dekel Tsur:
Testing Orientation Properties. - Albert Atserias:
Non-Uniform Hardness for NP via Black-Box Adversaries. - Amir Shpilka:
Constructions of low-degree and error-correcting epsilon-biased sets. - Jonathan A. Kelner, Daniel A. Spielman:
A Randomized Polynomial-Time Simplex Algorithm for Linear Programming (Preliminary Version). - Xiaoyang Gu, Jack H. Lutz, Elvira Mayordomo:
Points on Computable Curves. - Chris Peikert, Alon Rosen:
Efficient Collision-Resistant Hashing from Worst-Case Assumptions on Cyclic Lattices. - Daniel Rolf:
Improved Bound for the PPSZ/Schöning-Algorithm for 3-SAT. - Xiaoyang Gu, Jack H. Lutz:
Dimension Characterizations of Complexity Classes. - John M. Hitchcock:
Online Learning and Resource-Bounded Dimension: Winnow Yields New Lower Bounds for Hard Sets. - Yunlei Zhao, Jesper Buus Nielsen, Robert H. Deng, Dengguo Feng:
Generic yet Practical ZK Arguments from any Public-Coin HVZK. - Dvir Falik, Alex Samorodnitsky:
Edge-isoperimetric inequalities and influences.
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-21 20:19 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: