Volume 13, 2006
- Ran Raz, Iddo Tzameret:
The Strength of Multilinear Proofs.

- Eyal Kaplan, Moni Naor, Omer Reingold:
Derandomized Constructions of k-Wise (Almost) Independent Permutations.

- Joshua Buresh-Oppenheim, Rahul Santhanam:
Making Hard Problems Harder.

- Jesper Torp Kristensen, Peter Bro Miltersen:
Finding small OBDDs for incompletely specified truth tables is hard.

- Edith Elkind, Leslie Ann Goldberg, Paul W. Goldberg:
Nash Equilibria in Graphical Games on Trees Revisited.

- Alexander Shen:
Multisource algorithmic information theory.

- Mohammad Taghi Hajiaghayi, Guy Kortsarz, Mohammad R. Salavatipour:
Approximating Buy-at-Bulk k-Steiner trees.

- Mohammad Taghi Hajiaghayi, Guy Kortsarz, Mohammad R. Salavatipour:
Polylogarithmic Approximation Algorithm for Non-Uniform Multicommodity Buy-at-Bulk.

- Nutan Limaye, Meena Mahajan, Jayalal M. N. Sarma:
Evaluating Monotone Circuits on Cylinders, Planes and Tori.

- Réka Albert, Bhaskar DasGupta, Riccardo Dondi, Eduardo D. Sontag:
Inferring (Biological) Signal Transduction Networks via Transitive Reductions of Directed Graphs.

- Yijia Chen, Martin Grohe:
An Isomorphism between Subexponential and Parameterized Complexity Theory.

- Bruno Codenotti, Mauro Leoncini, Giovanni Resta:
Efficient Computation of Nash Equilibria for Very Sparse Win-Lose Games .

- Luca Trevisan:
Pseudorandomness and Combinatorial Constructions.

- Argimiro Arratia, Carlos E. Ortiz:
On a syntactic approximation to logics that capture complexity classes.

- Tomás Feder, Carlos S. Subi:
On Barnette's conjecture.

- Tomás Feder, Carlos S. Subi:
Partition into k-vertex subgraphs of k-partite graphs.

- Toshiya Itoh:
Improved Lower Bounds for Families of epsilon-Approximate k-Restricted Min-Wise Independent Permutations.

- Jin-yi Cai, Vinay Choudhary:
On the Theory of Matchgate Computations.

- Janka Chlebíková, Miroslav Chlebík:
Hardness of asymptotic approximation for orthogonal rectangle packing and covering problems.

- Akinori Kawachi, Tomoyuki Yamakami:
Quantum Hardcore Functions by Complexity-Theoretical Quantum List Decoding.

- Tomás Feder:
Constraint satisfaction: a personal perspective.

- Danny Harnik, Moni Naor:
On the Compressibility of NP Instances and Cryptographic Applications.

- Xi Chen, Xiaotie Deng, Shang-Hua Teng:
Computing Nash Equilibria: Approximation and Smoothed Complexity.

- Harry Buhrman, Lance Fortnow, Michal Koucký, John D. Rogers, Nikolai K. Vereshchagin:
Inverting onto functions might not be hard.

- Leonid Gurvits:
Hyperbolic Polynomials Approach to Van der Waerden/Schrijver-Valiant like Conjectures : \\ Sharper Bounds , Simpler Proofs and Algorithmic Applications.

- Ronen Gradwohl, Salil P. Vadhan, David Zuckerman:
Random Selection with an Adversarial Majority.

- Hermann Gruber, Markus Holzer:
Finding Lower Bounds for Nondeterministic State Complexity is Hard.

- Jonathan Katz, Chiu-Yuen Koo:
On Expected Constant-Round Protocols for Byzantine Agreement.

- Deeparnab Chakrabarty, Nikhil R. Devanur, Vijay V. Vazirani:
Eisenberg-Gale Markets: Rationality, Strongly Polynomial Solvability, and Competition Monotonicity.

- Piotr Berman, Jieun K. Jeong, Shiva Prasad Kasiviswanathan, Bhuvan Urgaonkar:
Packing to angles and sectors.

- Li-Sha Huang, Shang-Hua Teng:
On the Approximation and Smoothed Complexity of Leontief Market Equilibria.

- Vitaly Feldman:
Optimal Hardness Results for Maximizing Agreements with Monomials.

- Amit Agarwal, Elad Hazan:
Efficient Algorithms for Online Game Playing and Universal Portfolio Management.

- Moni Naor, Guy N. Rothblum:
The Complexity of Online Memory Checking.

- Till Tantau:
The Descriptive Complexity of the Reachability Problem As a Function of Different Graph Parameters.

- Tobias Riege, Jörg Rothe:
Completeness in the Boolean Hierarchy: Exact-Four-Colorability, Minimal Graph Uncolorability, and Exact Domatic Number Problems.

- Xi Chen, Xiaotie Deng:
On the Complexity of 2D Discrete Fixed Point Problem.

- David Doty, Jack H. Lutz, Satyadev Nandakumar:
Finite-State Dimension and Real Arithmetic.

- John M. Hitchcock, Aduri Pavan:
Comparing Reductions to NP-Complete Sets.

- Tomás Feder, Gagan Aggarwal, Rajeev Motwani, An Zhu:
Channel assignment in wireless networks and classification of minimum graph homomorphism.

- Tomás Feder, Rajeev Motwani, An Zhu:
k-connected spanning subgraphs of low degree.

- Amit Deshpande, Santosh Vempala:
Adaptive Sampling and Fast Low-Rank Matrix Approximation.

- Eran Ofek, Uriel Feige:
Random 3CNF formulas elude the Lovasz theta function.

- Andreas Björklund, Thore Husfeldt:
Inclusion-Exclusion Based Algorithms for Graph Colouring.

- Jan Arpe, Bodo Manthey:
Approximability of Minimum AND-Circuits.

- Dima Grigoriev, Edward A. Hirsch, Konstantin Pervyshev:
A Complete Public-Key Cryptosystem.

- María López-Valdés:
Scaled Dimension of Individual Strings.

- Jin-yi Cai, Vinay Choudhary:
Some Results on Matchgates and Holographic Algorithms.

- Guy Wolfovitz:
The Complexity of Depth-3 Circuits Computing Symmetric Boolean Functions.

- Alexander A. Razborov, Sergey Yekhanin:
An Omega(n^{1/3}) Lower Bound for Bilinear Group Based Private Information Retrieval.

- Alan Nash, Russell Impagliazzo, Jeffrey B. Remmel:
Infinitely-Often Universal Languages and Diagonalization.

- Wenbin Chen, Jiangtao Meng:
Inapproximability Results for the Closest Vector Problem with Preprocessing over infty Norm.

- Eldar Fischer, Orly Yahalom:
Testing Convexity Properties of Tree Colorings.

- Alex Samorodnitsky:
Low-degree tests at large distances.

- Scott Aaronson, Greg Kuperberg:
Quantum Versus Classical Proofs and Advice.

- Salil P. Vadhan:
An Unconditional Study of Computational Zero Knowledge.

- Adam R. Klivans, Alexander A. Sherstov:
Cryptographic Hardness Results for Learning Intersections of Halfspaces.

- Alexander Healy:
Randomness-Efficient Sampling within NC^1.

- Vitaly Feldman, Parikshit Gopalan, Subhash Khot, Ashok Kumar Ponnuswami:
New Results for Learning Noisy Parities and Halfspaces.

- Ran Raz, Amir Shpilka, Amir Yehudayoff:
A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits.

- Venkatesan Guruswami, Prasad Raghavendra:
Hardness of Learning Halfspaces with Noise.

- Subhas Kumar Ghosh:
Unique k-SAT is as Hard as k-SAT.

- Moses Charikar, Konstantin Makarychev, Yury Makarychev:
Approximation Algorithm for the Max k-CSP Problem.

- Moses Charikar, Konstantin Makarychev, Yury Makarychev:
Note on MAX 2SAT.

- Jan Arpe, Rüdiger Reischuk:
When Does Greedy Learning of Relevant Features Succeed? --- A Fourier-based Characterization ---.

- Vitaly Feldman:
On Attribute Efficient and Non-adaptive Learning of Parities and DNF Expressions.

- Heiner Ackermann, Heiko Röglin, Berthold Vöcking:
On the Impact of Combinatorial Structure on Congestion Games.

- Patrick Briest, Piotr Krysta:
Buying Cheap is Expensive: Hardness of Non-Parametric Multi-Product Pricing.

- Christian Glaßer, Alan L. Selman, Stephen D. Travers, Klaus W. Wagner:
The Complexity of Unions of Disjoint Sets.

- Ludwig Staiger:
The Kolmogorov complexity of infinite words.

- John M. Hitchcock, Aduri Pavan:
Hardness Hypotheses, Derandomization, and Circuit Complexity.

- Henning Fernau:
Parameterized Algorithms for Hitting Set: the Weighted Case.

- Andrej Bogdanov, Luca Trevisan:
Average-Case Complexity.

- Shahar Dobzinski, Noam Nisan:
Approximations by Computationally-Efficient VCG-Based Mechanisms.

- Minh-Huyen Nguyen, Shien Jin Ong, Salil P. Vadhan:
Statistical Zero-Knowledge Arguments for NP from Any One-Way Function.

- Noam Nisan:
A Note on the computational hardness of evolutionary stable strategies.

- María López-Valdés:
Lempel-Ziv Dimension for Lempel-Ziv Compression.

- Tobias Riege, Jörg Rothe:
Improving Deterministic and Randomized Exponential-Time Algorithms for the Satisfiability, the Colorability, and the Domatic Number Problem.

- Kristoffer Arnsfelt Hansen:
Lower Bounds for Circuits with Few Modular Gates using Exponential Sums.

- David Doty:
Dimension Extractors.

- Spyros C. Kontogiannis, Panagiota N. Panagopoulou, Paul G. Spirakis:
Polynomial Algorithms for Approximating Nash Equilibria of Bimatrix Games.

- Prabhu Manyem:
Polynomial-Time Maximisation Classes: Syntactic Hierarchy.

- Nils Hebbinghaus, Benjamin Doerr, Frank Neumann:
Speeding up Evolutionary Algorithms by Restricted Mutation Operators.

- Frank Neumann, Carsten Witt:
Runtime Analysis of a Simple Ant Colony Optimization Algorithm.

- Andreas Jakoby, Maciej Liskiewicz, Aleksander Madry:
Using Quantum Oblivious Transfer to Cheat Sensitive Quantum Bit Commitment.

- Dmitry Gavinsky, Julia Kempe, Ronald de Wolf:
Exponential Separation of Quantum and Classical One-Way Communication Complexity for a Boolean Function.

- Iordanis Kerenidis, Ran Raz:
The one-way communication complexity of the Boolean Hidden Matching Problem.

- Per Austrin:
Balanced Max 2-Sat might not be the hardest.

- Sofya Raskhodnikova, Adam Smith:
A Note on Adaptivity in Testing Properties of Bounded Degree Graphs.

- Christian Glaßer, Alan L. Selman, Stephen D. Travers, Liyu Zhang:
Non-Mitotic Sets.

- Felix Brandt, Felix A. Fischer, Markus Holzer:
Symmetries and the Complexity of Pure Nash Equilibrium.

- Matthias Englert, Heiko Röglin, Berthold Vöcking:
Worst Case and Probabilistic Analysis of the 2-Opt Algorithm for the TSP.

- Takeshi Koshiba, Yoshiharu Seri:
Round-Efficient One-Way Permutation Based Perfectly Concealing Bit Commitment Scheme.

- Parikshit Gopalan, Phokion G. Kolaitis, Elitza N. Maneva, Christos H. Papadimitriou:
The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies.

- Rafail Ostrovsky, Giuseppe Persiano, Ivan Visconti:
Concurrent Non-Malleable Witness Indistinguishability and its Applications.

- Iftach Haitner, Omer Reingold:
A New Interactive Hashing Theorem.

- Emanuele Viola:
New correlation bounds for GF(2) polynomials using Gowers uniformity.

- Grant Schoenebeck, Luca Trevisan, Madhur Tulsiani:
A Linear Round Lower Bound for Lovasz-Schrijver SDP Relaxations of Vertex Cover.

- Oded Goldreich:
On Expected Probabilistic Polynomial-Time Adversaries -- A suggestion for restricted definitions and their benefits.

- Meena Mahajan, Jayalal M. N. Sarma:
On the Complexity of Rank and Rigidity.

- Wenceslas Fernandez de la Vega, Marek Karpinski:
Approximation Complexity of Nondense Instances of MAX-CUT.

- Luis Rademacher, Santosh Vempala:
Dispersion of Mass and the Complexity of Randomized Geometric Algorithms.

- Oded Lachish, Ilan Newman, Asaf Shapira:
Space Complexity vs. Query Complexity.

- Wenceslas Fernandez de la Vega, Marek Karpinski:
On the Sample Complexity of MAX-CUT.

- Avi Wigderson, David Xiao:
Derandomizing the AW matrix-valued Chernoff bound using pessimistic estimators and applications.

- Scott Aaronson:
The Learnability of Quantum States.

- Arkadev Chattopadhyay:
An improved bound on correlation between polynomials over Z_m and MOD_q.

- Dan Gutfreund, Amnon Ta-Shma:
New connections between derandomization, worst-case complexity and average-case complexity.

- Julia Chuzhoy, Sanjeev Khanna:
Hardness of Directed Routing with Congestion.

- Nishanth Chandran, Ryan Moriarty, Rafail Ostrovsky, Omkant Pandey, Amit Sahai:
Improved Algorithms for Optimal Embeddings.

- Artur Czumaj, Miroslaw Kowaluk, Andrzej Lingas:
Faster algorithms for finding lowest common ancestors in directed acyclic graphs.

- Xin Han, Kazuo Iwama, Deshi Ye, Guochuan Zhang:
Strip Packing vs. Bin Packing.

- Peter Bürgisser:
On defining integers in the counting hierarchy and proving lower bounds in algebraic complexity.

- Carl Bosley, Yevgeniy Dodis:
Does Privacy Require True Randomness?.

- Artur Czumaj, Andrzej Lingas:
Finding a Heaviest Triangle is not Harder than Matrix Multiplication.

- Amin Coja-Oghlan:
Graph partitioning via adaptive spectral techniques.

- Arkadev Chattopadhyay, Michal Koucký, Andreas Krebs, Mario Szegedy, Pascal Tesson, Denis Thérien:
Languages with Bounded Multiparty Communication Complexity.

- Irit Dinur, Madhu Sudan, Avi Wigderson:
Robust Local Testability of Tensor Products of LDPC Codes.

- Noga Alon, Oded Schwartz, Asaf Shapira:
An Elementary Construction of Constant-Degree Expanders.

- Leslie G. Valiant:
Evolvability.

- Charanjit S. Jutla:
A Simple Biased Distribution for Dinur's Construction.

- Noam Livne:
All Natural NPC Problems Have Average-Case Complete Versions.

- Venkatesan Guruswami:
Iterative Decoding of Low-Density Parity Check Codes (A Survey).

- Wenceslas Fernandez de la Vega, Ravi Kannan, Marek Karpinski:
Approximation of Global MAX-CSP Problems.

- Luis Antunes, Lance Fortnow, Alexandre Pinto, Andre Souto:
Low-Depth Witnesses are Easy to Find.

- Piotr Indyk:
Uncertainty Principles, Extractors, and Explicit Embeddings of L2 into L1.

- Sergey Yekhanin:
New Locally Decodable Codes and Private Information Retrieval Schemes.

- Shankar Kalyanaraman, Christopher Umans:
On obtaining pseudorandomness from error-correcting codes..

- Manindra Agrawal, Thanh Minh Hoang, Thomas Thierauf:
The polynomially bounded perfect matching problem is in NC^2.

- Tanmoy Chakraborty, Samir Datta:
One-input-face MPCVP is Hard for L, but in LogDCFL.

- Konstantin Pervyshev:
On Heuristic Time Hierarchies.

- Grant Schoenebeck, Luca Trevisan, Madhur Tulsiani:
Tight Integrality Gaps for Lovasz-Schrijver LP Relaxations of Vertex Cover and Max Cut.

- Alexander Hertel, Alasdair Urquhart:
The Resolution Width Problem is EXPTIME-Complete.

- Venkatesan Guruswami, Christopher Umans, Salil P. Vadhan:
Extractors and condensers from univariate polynomials.

- Jin-yi Cai, Pinyan Lu:
On Symmetric Signatures in Holographic Algorithms.

- Mihir Bellare, Oded Goldreich:
On Probabilistic versus Deterministic Provers in the Definition of Proofs Of Knowledge.

- Wolfgang Maass, Prashant Joshi, Eduardo D. Sontag:
Computational aspects of feedback in neural circuits.

- Wolfgang Maass, Kei Uchizawa, Rodney J. Douglas:
Energy Complexity and Entropy of Threshold Circuits.

- Shien Jin Ong, Salil P. Vadhan:
Zero Knowledge and Soundness are Symmetric.

- Paul Beame, Russell Impagliazzo, Toniann Pitassi, Nathan Segerlind:
Formula Caching in DPLL.

- Venkatesan Guruswami, Kunal Talwar:
Hardness of Low Congestion Routing in Directed Graphs.

- Olaf Beyersdorff:
On the Deduction Theorem and Complete Disjoint NP-Pairs.

- Frank Neumann, Carsten Witt:
Ant Colony Optimization and the Minimum Spanning Tree Problem.

- Claire Kenyon-Mathieu, Warren Schudy:
How to rank with few errors: A PTAS for Weighted Feedback Arc Set on Tournaments.

- Jin-yi Cai, Pinyan Lu:
Holographic Algorithms: From Art to Science.

- Christoph Buchheim, Peter J. Cameron, Taoyang Wu:
On the Subgroup Distance Problem.

- Chris Peikert, Alon Rosen:
Lattices that Admit Logarithmic Worst-Case to Average-Case Connection Factors.

- Chris Peikert:
Limits on the Hardness of Lattice Problems in $\ell_p$ Norms.

- Lance Fortnow, Rakesh Vohra:
The Complexity of Forecast Testing.

- Patrick Briest:
Towards Hardness of Envy-Free Pricing.

- Prahladh Harsha, Rahul Jain, David A. McAllester, Jaikumar Radhakrishnan:
The communication complexity of correlation.

- Konstantinos Georgiou, Avner Magen, Toniann Pitassi, Iannis Tourlakis:
Tight integrality gaps for Vertex Cover SDPs in the Lovasz-Schrijver hierarchy.

- Michael Bauland, Thomas Schneider, Henning Schnoor, Ilka Schnoor, Heribert Vollmer:
The Complexity of Generalized Satisfiability for Linear Temporal Logic.

- Joshua Buresh-Oppenheim, Valentine Kabanets, Rahul Santhanam:
Uniform Hardness Amplification in NP via Monotone Codes.

- Wenceslas Fernandez de la Vega, Marek Karpinski:
Trading Tensors for Cloning: Constant Time Approximation Schemes for Metric MAX-CSP.

- Tomás Feder, Rajeev Motwani:
Finding large cycles in Hamiltonian graphs.

- Lance Fortnow, Rahul Santhanam:
Fixed-Polynomial Size Circuit Bounds.

- Gyula Györ:
Representing Boolean OR function by quadratic polynomials modulo 6.

- Predrag T. Tosic:
Computational Complexity of Some Enumeration Problems About Uniformly Sparse Boolean Network Automata.

- Tomás Feder, Phokion G. Kolaitis:
Closures and dichotomies for quantified constraints.

Last update Fri May 24 16:37:03 2013
CET by the DBLP Team —
Data released under the ODC-BY 1.0 license — See also our legal information page