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. Article TR05-001 - Magnus Bordewich, Martin E. Dyer, Marek Karpinski:
Path Coupling Using Stopping Times and Counting Independent Sets and Colourings in Hypergraphs. Article TR05-002 - Scott Aaronson:
Quantum Computing, Postselection, and Probabilistic Polynomial-Time. Article TR05-003 - Leslie G. Valiant:
Memorization and Association on a Realistic Neural Model. Article TR05-004 - Tomás Feder:
Constraint Satisfaction on Finite Groups with Near Subgroups. Article TR05-005 - Edward A. Hirsch, Sergey I. Nikolenko:
Simulating Cutting Plane proofs with restricted degree of falsity by Resolution. Article TR05-006 - Vadim Lyubashevsky:
On Random High Density Subset Sums. Article TR05-007 - Neeraj Kayal:
Recognizing permutation functions in polynomial time. Article TR05-008 - David P. Woodruff, Sergey Yekhanin:
A Geometric Approach to Information-Theoretic Private Information Retrieval. Article TR05-009 - Olivier Powell:
Almost Completeness in Small Complexity Classes. Article TR05-010 - Christian Glaßer, Mitsunori Ogihara, Aduri Pavan, Alan L. Selman, Liyu Zhang:
Autoreducibility, Mitoticity, and Immunity. Article TR05-011 - Luca Trevisan, Salil P. Vadhan, David Zuckerman:
Compression of Samplable Sources. Article TR05-012 - Bin Fu:
Theory and Application of Width Bounded Geometric Separator. Article TR05-013 - Oded Goldreich:
Short Locally Testable Codes and Proofs (Survey). Article TR05-014 - Andrej Bogdanov, Luca Trevisan:
On Worst-Case to Average-Case Reductions for NP Problems. Article TR05-015 - Tomás Feder, Daniel K. Ford:
Classification of Bipartite Boolean Constraint Satisfaction through Delta-Matroid Intersection. Article TR05-016 - Phuong Nguyen:
Two-Sorted Theories for L, SL, NL and P. Article TR05-017 - Oded Goldreich:
On Promise Problems (a survey in memory of Shimon Even [1935-2004]). Article TR05-018 - Venkatesan Guruswami, Atri Rudra:
Tolerant Locally Testable Codes. Article TR05-019 - Sourav Chakraborty:
On the Sensitivity of Cyclically-Invariant Boolean Functions. Article TR05-020 - Stasys Jukna:
Disproving the single level conjecture. Article TR05-021 - Omer Reingold, Luca Trevisan, Salil P. Vadhan:
Pseudorandom Walks in Biregular Graphs and the RL vs. L Problem. Article TR05-022 - Robert H. Sloan, Balázs Szörényi, György Turán:
On k-term DNF with largest number of prime implicants. Article TR05-023 - Michael Bauland, Elmar Böhler, Nadia Creignou, Steffen Reith, Henning Schnoor, Heribert Vollmer:
Quantified Constraints: The Complexity of Decision and Counting for Bounded Alternation. Article TR05-024 - Zeev Dvir, Ran Raz:
Analyzing Linear Mergers. Article TR05-025 - Scott Aaronson:
NP-complete Problems and Physical Reality. Article TR05-026 - Daniel Rolf:
Derandomization of PPSZ for Unique-k-SAT. Article TR05-027 - Elmar Böhler:
On the Lattice of Clones Below the Polynomial Time Functions. Article TR05-028 - Frank Neumann, Marco Laumanns:
Speeding Up Approximation Algorithms for NP-hard Spanning Forest Problems by Multi-objective Optimization. Article TR05-029 - Evgeny Dantsin, Alexander Wolpert:
An Improved Upper Bound for SAT. Article TR05-030 - Carme Àlvarez, Joaquim Gabarró, Maria J. Serna:
Pure Nash equilibria in games with a large number of actions. Article TR05-031 - Gudmund Skovbjerg Frandsen, Peter Bro Miltersen:
Reviewing Bounds on the Circuit Size of the Hardest Functions. Article TR05-032 - Martin Fürer, Shiva Prasad Kasiviswanathan:
Algorithms for Counting 2-SAT Solutions and Colorings with Applications. Article TR05-033 - Luca Trevisan:
Approximation Algorithms for Unique Games. Article TR05-034 - Christian Glaßer, Stephen D. Travers, Klaus W. Wagner:
A Reducibility that Corresponds to Unbalanced Leaf-Language Classes. Article TR05-035 - Hubie Chen:
Quantified Constraint Satisfaction, Maximal Constraint Languages, and Symmetric Polymorphisms. Article TR05-036 - Eric Allender, Peter Bürgisser, Johan Kjeldgaard-Pedersen, Peter Bro Miltersen:
On the Complexity of Numerical Analysis. Article TR05-037 - Ran Raz:
Quantum Information and the PCP Theorem. Article TR05-038 - Irit Dinur, Elchanan Mossel, Oded Regev:
Conditional Hardness for Approximate Coloring. Article TR05-039 - Scott Aaronson:
Oracles Are Subtle But Not Malicious. Article TR05-040 - Shengyu Zhang:
(Almost) tight bounds for randomized and quantum Local Search on hypercubes and grids. Article TR05-041 - Lance Fortnow, Adam R. Klivans:
Linear Advice for Randomized Logarithmic Space. Article TR05-042 - Emanuele Viola:
Pseudorandom Bits for Constant-Depth Circuits with Few Arbitrary Symmetric Gates. Article TR05-043 - Zeev Dvir, Amir Shpilka:
Locally Decodable Codes with 2 queries and Polynomial Identity Testing for depth 3 circuits. Article TR05-044 - Philippe Moser:
Martingale Families and Dimension in P. Article TR05-045 - Irit Dinur:
The PCP theorem by gap amplification. Article TR05-046 - Kooshiar Azimian, Mahmoud Salmasizadeh, Javad Mohajeri:
Weak Composite Diffie-Hellman is not Weaker than Factoring. Article TR05-047 - Moti Yung, Yunlei Zhao:
Constant-Round Concurrently-Secure rZK in the (Real) Bare Public-Key Model. Article TR05-048 - Joan Boyar, René Peralta:
The Exact Multiplicative Complexity of the Hamming Weight Function. Article TR05-049 - Uriel Feige, Eran Ofek:
Finding a Maximum Independent Set in a Sparse Random Graph. Article TR05-050 - Predrag T. Tosic:
On Complexity of Counting Fixed Points in Certain Classes of Graph Automata. Article TR05-051 - Grant Schoenebeck, Salil P. Vadhan:
The Computational Complexity of Nash Equilibria in Concisely Represented Games. Article TR05-052 - Paul Beame, Toniann Pitassi, Nathan Segerlind:
Lower bounds for Lovasz-Schrijver systems and beyond follow from multiparty communication complexity. Article TR05-053 - Konstantin Pervyshev:
Time Hierarchies for Computations with a Bit of Advice. Article TR05-054 - Bruno Codenotti, Amin Saberi, Kasturi R. Varadarajan, Yinyu Ye:
Leontief Economies Encode Nonzero Sum Two-Player Games. Article TR05-055 - Alexis C. Kaporis, Efpraxia I. Politopoulou, Paul G. Spirakis:
The Price of Optimum in Stackelberg Games. Article TR05-056 - Venkatesan Guruswami, Valentine Kabanets:
Hardness amplification via space-efficient direct products. Article TR05-057 - Sanjeev Arora, Eli Berger, Elad Hazan, Guy Kindler, Muli Safra
:
On Non-Approximability for Quadratic Programs. Article TR05-058 - Víctor Dalmau, Ricard Gavaldà, Pascal Tesson, Denis Thérien:
Tractable Clones of Polynomials over Semigroups. Article TR05-059 - Philippe Moser:
Generic Density and Small Span Theorem. Article TR05-060 - Ronen Gradwohl, Guy Kindler, Omer Reingold, Amnon Ta-Shma:
On the Error Parameter of Dispersers. Article TR05-061 - Aduri Pavan, N. V. Vinodchandran:
2-Local Random Reductions to 3-Valued Functions. Article TR05-062 - Bodo Manthey, Rüdiger Reischuk:
Smoothed Analysis of the Height of Binary Search Trees. Article TR05-063 - Howard J. Karloff, Subhash Khot, Aranyak Mehta, Yuval Rabani:
On earthmover distance, metric labeling, and 0-extension. Article TR05-064 - Alexander I. Barvinok, Alex Samorodnitsky:
Random Weighting, Asymptotic Counting, and Inverse Isoperimetry. Article TR05-065 - Jakob Nordström:
Narrow Proofs May Be Spacious: Separating Space and Width in Resolution. Article TR05-066 - Zeev Dvir, Amir Shpilka:
An Improved Analysis of Mergers. Article TR05-067 - Christian Glaßer, Aduri Pavan, Alan L. Selman, Liyu Zhang:
Redundancy in Complete Sets. Article TR05-068 - Piotr Berman, Marek Karpinski:
8/7-Approximation Algorithm for (1,2)-TSP. Article TR05-069 - Mahdi Cheraghchi:
On Matrix Rigidity and the Complexity of Linear Forms. Article TR05-070 - Marius Zimand:
Simple extractors via constructions of cryptographic pseudo-random generators. Article TR05-071 - Christian Glaßer, Alan L. Selman, Liyu Zhang:
Survey of Disjoint NP-Pairs and Relations to Propositional Proof Systems. Article TR05-072 - Oded Goldreich, Dana Ron:
Approximating Average Parameters of Graphs. Article TR05-073 - Li-Sha Huang, Xiaotie Deng:
On Complexity of Market Equilibria with Maximum Social Welfare. Article TR05-074 - Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum:
Dobrushin conditions and Systematic Scan. Article TR05-075 - Dima Grigoriev, Edward A. Hirsch, Konstantin Pervyshev:
Time hierarchies for cryptographic function inversion with advice. Article TR05-076 - Zenon Sadowski:
On a D-N-optimal acceptor for TAUT. Article TR05-077 - Kooshiar Azimian, Javad Mohajeri, Mahmoud Salmasizadeh, Siamak Fayyaz Shahandashti:
A Verifiable Partial Key Escrow, Based on McCurley Encryption Scheme. Article TR05-078 - Stasys Jukna:
Expanders and time-restricted branching programs. Article TR05-079 - Michael R. Fellows, Frances A. Rosamond, Udi Rotics, Stefan Szeider:
Proving NP-hardness for clique-width I: non-approximability of sequential clique-width. Article TR05-080 - Michael R. Fellows, Frances A. Rosamond, Udi Rotics, Stefan Szeider:
Proving NP-hardness for clique-width II: non-approximability of clique-width. Article TR05-081 - Jorge Castro:
On the Query Complexity of Quantum Learners. Article TR05-082 - Olaf Beyersdorff:
Disjoint NP-Pairs from Propositional Proof Systems. Article TR05-083 - Mickey Brautbar, Alex Samorodnitsky:
Approximating the entropy of large alphabets. Article TR05-084 - Asaf Shapira, Noga Alon:
Homomorphisms in Graph Property Testing - A Survey. Article TR05-085 - Dana Moshkovitz, Ran Raz:
Sub-Constant Error Low Degree Test of Almost Linear Size. Article TR05-086 - Alexander Healy, Emanuele Viola:
Constant-Depth Circuits for Arithmetic in Finite Fields of Characteristic Two. Article TR05-087 - Jan Arpe:
Learning Juntas in the Presence of Noise. Article TR05-088 - Xiaoyang Gu, Jack H. Lutz, Philippe Moser:
Dimensions of Copeland-Erdös Sequences. Article TR05-089 - Paul W. Goldberg, Christos H. Papadimitriou:
Reducibility Among Equilibrium Problems. Article TR05-090 - Predrag T. Tosic:
Counting Fixed Points and Gardens of Eden of Sequential Dynamical Systems on Planar Bipartite Graphs. Article TR05-091 - Eyal Rozenman, Salil P. Vadhan:
Derandomized Squaring of Graphs. Article TR05-092 - Daniele Micciancio, Shien Jin Ong, Amit Sahai, Salil P. Vadhan:
Concurrent Zero Knowledge without Complexity Assumptions. Article TR05-093 - Michal Parnas, Dana Ron:
On Approximating the Minimum Vertex Cover in Sublinear Time and the Connection to Distributed Algorithms. Article TR05-094 - Noga Alon, Ilan Newman, Alexander Shen, Gábor Tardos, Nikolai K. Vereshchagin:
Partitioning multi-dimensional sets in a small number of "uniform" parts. Article TR05-095 - Boaz Barak, Amit Sahai:
How To Play Almost Any Mental Game Over The Net - Concurrent Composition via Super-Polynomial Simulation. Article TR05-096 - Jens Groth, Rafail Ostrovsky, Amit Sahai:
Perfect Non-Interactive Zero Knowledge for NP. Article TR05-097 - Oded Goldreich:
Bravely, Moderately: A Common Theme in Four Recent Results. Article TR05-098 - Leslie G. Valiant:
Holographic Algorithms. Article TR05-099 - David Zuckerman:
Linear Degree Extractors and the Inapproximability of Max Clique and Chromatic Number. Article TR05-100 - Guy Kindler, Ryan O'Donnell, Subhash Khot, Elchanan Mossel:
Optimal Inapproximability Results for MAX-CUT and Other 2-Variable CSPs? Article TR05-101 - Evgeny Dantsin, Edward A. Hirsch, Alexander Wolpert:
Clause Shortening Combined with Pruning Yields a New Upper Bound for Deterministic SAT Algorithms. Article TR05-102 - Leonid Gurvits:
A proof of hyperbolic van der Waerden conjecture : the right generalization is the ultimate simplification. Article TR05-103 - Don Coppersmith, Atri Rudra:
On the Robust Testability of Product of Codes. Article TR05-104 - Lance Fortnow, John M. Hitchcock, Aduri Pavan, N. V. Vinodchandran, Fengming Wang:
Extracting Kolmogorov Complexity with Applications to Dimension Zero-One Laws. Article TR05-105 - Anup Rao:
Extractors for a Constant Number of Polynomial Min-Entropy Independent Sources. Article TR05-106 - Avi Wigderson, David Xiao:
A Randomness-Efficient Sampler for Matrix-valued Functions and Applications. Article TR05-107 - Ariel Gabizon, Ran Raz:
Deterministic Extractors for Affine Sources over Large Fields. Article TR05-108 - Ariel Gabizon, Ran Raz, Ronen Shaltiel:
Deterministic Extractors for Bit-fixing Sources by Obtaining an Independent Seed. Article TR05-109 - Saurabh Sanghvi, Salil P. Vadhan:
The Round Complexity of Two-Party Random Selection. Article TR05-110 - Dieter van Melkebeek, Konstantin Pervyshev:
A Generic Time Hierarchy for Semantic Models With One Bit of Advice. Article TR05-111 - Eran Ofek:
On the expansion of the giant component in percolated (n,d,lambda) graphs. Article TR05-112 - Bernhard Fuchs:
On the Hardness of Range Assignment Problems. Article TR05-113 - Boaz Barak, Shien Jin Ong, Salil P. Vadhan:
Derandomization in Cryptography. Article TR05-114 - Konstantinos Daskalakis, Paul W. Goldberg, Christos H. Papadimitriou:
The complexity of computing a Nash equilibrium. Article TR05-115 - Alex Samorodnitsky, Luca Trevisan:
Gowers Uniformity, Influence of Variables, and PCPs. Article TR05-116 - Piotr Indyk, David P. Woodruff:
Polylogarithmic Private Approximations and Efficient Matching. Article TR05-117 - Jin-yi Cai, Vinay Choudhary:
Valiant's Holant Theorem and Matchgate Tensors. Article TR05-118 - Nadia Creignou, Phokion G. Kolaitis, Bruno Zanuttini:
Preferred representations of Boolean relations. Article TR05-119 - Sashka Davis, Russell Impagliazzo:
Models of Greedy Algorithms for Graph Problems. Article TR05-120 - Martin E. Dyer, Leslie Ann Goldberg, Mike Paterson:
On counting homomorphisms to directed acyclic graphs. Article TR05-121 - Pavel Pudlák:
A nonlinear bound on the number of wires in bounded depth circuits. Article TR05-122 - Olaf Beyersdorff:
Tuples of Disjoint NP-Sets. Article TR05-123 - Kooshiar Azimian:
Breaking Diffie-Hellman is no Easier than Root Finding. Article TR05-124 - Sofya Raskhodnikova, Dana Ron, Ronitt Rubinfeld, Amir Shpilka, Adam D. Smith:
Sublinear Algorithms for Approximating String Compressibility and the Distribution Support Size. Article TR05-125 - Eric Allender, Lisa Hellerstein, Paul McCabe, Toniann Pitassi, Michael E. Saks:
Minimizing DNF Formulas and AC0 Circuits Given a Truth Table. Article TR05-126 - Vitaly Feldman:
Hardness of Approximate Two-level Logic Minimization and PAC Learning with Membership Queries. Article TR05-127 - Miroslava Sotáková:
The normal form of reversible circuits consisting of CNOT and NOT gates. Article TR05-128 - Scott Aaronson:
QMA/qpoly Is Contained In PSPACE/poly: De-Merlinizing Quantum Protocols. Article TR05-129 - Ahuva Mu'alem:
A Note on Testing Truthfulness. Article TR05-130 - Don Coppersmith, Lisa Fleischer, Atri Rudra:
Ordering by weighted number of wins gives a good ranking for weighted tournaments. Article TR05-131 - Venkatesan Guruswami:
Algebraic-geometric generalizations of the Parvaresh-Vardy codes. Article TR05-132 - Venkatesan Guruswami, Atri Rudra:
Explicit Capacity-Achieving List-Decodable Codes. Article TR05-133 - Xi Chen, Xiaotie Deng:
3-NASH is PPAD-Complete. Article TR05-134 - Iftach Haitner, Danny Harnik, Omer Reingold:
On the Power of the Randomized Iterate. Article TR05-135 - Anna Gál, Michal Koucký, Pierre McKenzie:
Incremental branching programs. Article TR05-136 - Emanuele Viola:
On Probabilistic Time versus Alternating Time. Article TR05-137 - Peter Bürgisser, Felipe Cucker:
Exotic quantifiers, complexity classes, and complete problems. Article TR05-138 - Konstantinos Daskalakis, Christos H. Papadimitriou:
Three-Player Games Are Hard. Article TR05-139 - Xi Chen, Xiaotie Deng:
Settling the Complexity of 2-Player Nash-Equilibrium. Article TR05-140 - Amos Beimel, Paz Carmi, Kobbi Nissim, Enav Weinreb:
Private Approximation of Search Problems. Article TR05-141 - Vadim Lyubashevsky, Daniele Micciancio:
Generalized Compact Knapsacks are Collision Resistant. Article TR05-142 - Parikshit Gopalan:
Constructing Ramsey Graphs from Boolean Function Representations. Article TR05-143 - Lance Fortnow, Luis Antunes:
Time-Bounded Universal Distributions. Article TR05-144 - Ronen Shaltiel:
How to get more mileage from randomness extractors. Article TR05-145 - Gábor Erdélyi, Tobias Riege, Jörg Rothe:
Quantum Cryptography: A Survey. Article TR05-146 - Christian Glaßer, Stephen D. Travers:
Machines that can Output Empty Words. Article TR05-147 - Eric Allender, Samir Datta, Sambuddha Roy:
The Directed Planar Reachability Problem. Article TR05-148 - Eric Allender, David A. Mix Barrington, Tanmoy Chakraborty, Samir Datta, Sambuddha Roy:
Grid Graph Reachability Problems. Article TR05-149 - Neeraj Kayal, Nitin Saxena:
Polynomial Identity Testing for Depth 3 Circuits. Article TR05-150 - Magnus Bordewich, Martin E. Dyer, Marek Karpinski:
Metric Construction, Stopping Times and Path Coupling. Article TR05-151 - Oded Lachish, Ilan Newman:
Languages that are Recognized by Simple Counter Automata are not necessarily Testable. Article TR05-152 - Shirley Halevy, Oded Lachish, Ilan Newman, Dekel Tsur:
Testing Orientation Properties. Article TR05-153 - Albert Atserias:
Non-Uniform Hardness for NP via Black-Box Adversaries. Article TR05-154 - Amir Shpilka:
Constructions of low-degree and error-correcting epsilon-biased sets. Article TR05-155 - Jonathan A. Kelner, Daniel A. Spielman:
A Randomized Polynomial-Time Simplex Algorithm for Linear Programming (Preliminary Version). Article TR05-156 - Xiaoyang Gu, Jack H. Lutz, Elvira Mayordomo:
Points on Computable Curves. Article TR05-157 - Chris Peikert, Alon Rosen:
Efficient Collision-Resistant Hashing from Worst-Case Assumptions on Cyclic Lattices. Article TR05-158 - Daniel Rolf:
Improved Bound for the PPSZ/Schöning-Algorithm for 3-SAT. Article TR05-159 - Xiaoyang Gu, Jack H. Lutz:
Dimension Characterizations of Complexity Classes. Article TR05-160 - John M. Hitchcock:
Online Learning and Resource-Bounded Dimension: Winnow Yields New Lower Bounds for Hard Sets. Article TR05-161 - Yunlei Zhao, Jesper Buus Nielsen, Robert H. Deng, Dengguo Feng:
Generic yet Practical ZK Arguments from any Public-Coin HVZK. Article TR05-162 - Dvir Falik, Alex Samorodnitsky:
Edge-isoperimetric inequalities and influences. Article TR05-163
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 2026-03-22 22:38 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:
