default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDElectronic Colloquium on Computational Complexity, 2006
Volume TR06, 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 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 S. 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(n1/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 D. 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 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 S. 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 ℓ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.
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-08 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:
