default search action
Electronic Colloquium on Computational Complexity, 2003
Volume TR03, 2003
- Vince Grolmusz:
Near Quadratic Matrix Multiplication Modulo Composites. - Stefan Szeider:
Minimal unsatisfiable formulas with bounded clause-variable difference are fixed-parameter tractable. - Fahiem Bacchus, Shannon Dalmao, Toniann Pitassi:
DPLL with Caching: A new algorithm for #SAT and Bayesian Inference. - Eli Ben-Sasson, Prahladh Harsha:
Lower Bounds for Bounded-Depth Frege Proofs via Buss-Pudlack Games. - Scott Aaronson:
Quantum Certificate Complexity. - Eli Ben-Sasson, Prahladh Harsha, Sofya Raskhodnikova:
3CNF Properties are Hard to Test. - Olivier Dubois, Yacine Boufkhad, Jacques Mandler:
Typical random 3-SAT formulae and the satisfiability threshold. - Piotr Berman, Marek Karpinski:
Improved Approximation Lower Bounds on Small Occurrence Optimization. - Markus Bläser, Andreas Jakoby, Maciej Liskiewicz, Bodo Manthey:
Private Computation - k-connected versus 1-connected Networks. - Sven Baumer, Rainer Schuler:
Improving a probabilistic 3-SAT Algorithm by Dynamic Search and Independent Clause Pairs. - Christian Glaßer, Alan L. Selman, Samik Sengupta, Liyu Zhang:
Disjoint NP-Pairs. - Edward A. Hirsch, Arist Kojevnikov:
Several notes on the power of Gomory-Chvatal cuts. - Luca Trevisan:
An epsilon-Biased Generator in NC0. - Avrim Blum, Ke Yang:
On Statistical Query Sampling and NMR Quantum Computing. - Shafi Goldwasser, Yael Tauman:
On the (In)security of the Fiat-Shamir Paradigm. - Dimitrios Koukopoulos, Marios Mavronicolas, Paul G. Spirakis:
FIFO is Unstable at Arbitrarily Low Rates. - Peter Bro Miltersen, Jaikumar Radhakrishnan, Ingo Wegener:
On Converting CNF to DNF. - Matthias Galota, Heribert Vollmer:
Functions Computable in Polynomial Space. - Eli Ben-Sasson, Oded Goldreich, Madhu Sudan:
Bounds on 2-Query Codeword Testing. - Elad Hazan, Shmuel Safra
, Oded Schwartz:
On the Hardness of Approximating k-Dimensional Matching. - Mikhail N. Vyalyi:
QMA=PP implies that PP contains PH. - Piotr Berman, Marek Karpinski, Alex D. Scott:
Approximation Hardness and Satisfiability of Bounded Occurrence Instances of SAT. - Anna Palbom:
On Spanning Cacti and Asymmetric TSP. - Till Tantau:
Weak Cardinality Theorems for First-Order Logic. - Kristoffer Arnsfelt Hansen:
Constant width planar computation characterizes ACC0. - Janka Chlebíková, Miroslav Chlebík:
Inapproximability results for bounded variants of optimization problems. - Christian Glaßer, Alan L. Selman, Samik Sengupta:
Reductions between Disjoint NP-Pairs. - Olivier Powell:
PSPACE contains almost complete problems. - Philippe Moser:
BPP has effective dimension at most 1/2 unless BPP=EXP. - Amin Coja-Oghlan, Andreas Goerdt, André Lanka, Frank Schädlich:
Certifying Unsatisfiability of Random 2k-SAT Formulas using Approximation Techniques. - Birgit Schelm:
Average-Case Complexity Theory of Approximation Problems. - Andreas Björklund, Thore Husfeldt, Sanjeev Khanna:
Approximating Longest Directed Path. - Meir Feder, Dana Ron, Ami Tavory:
Bounds on Linear Codes for Network Multicast. - Arnold Beckmann:
Height restricted constant depth LK. - Eran Halperin, Guy Kortsarz, Robert Krauthgamer:
Tight lower bounds for the asymmetric k-center problem. - Bruce E. Litow:
Polynomial equation elimination via Tarski Algebra. - Ziv Bar-Yossef:
Sampling Lower Bounds via Information Theory. - Julia Chuzhoy, Sudipto Guha, Sanjeev Khanna, Joseph Naor:
Asymmetric k-center is log*n-hard to Approximate. - Judy Goldsmith, Robert H. Sloan, Balázs Szörényi, György Turán:
Theory Revision with Queries: Horn, Read-once, and Parity Formulas. - Philippe Moser:
RP is Small in SUBEXP else ZPP equals PSPACE and NP equals EXP. - Albert Atserias, Maria Luisa Bonet, Jordi Levy:
On Chvatal Rank and Cutting Planes Proofs. - Luca Trevisan:
List Decoding Using the XOR Lemma. - Elchanan Mossel, Amir Shpilka, Luca Trevisan:
On epsilon-Biased Generators in NC0. - Juan Luis Esteban, Jacobo Torán:
A Combinatorial Characterization of Treelike Resolution Space. - Oded Goldreich, Shafi Goldwasser, Asaf Nussboim:
On the Implementation of Huge Random Objects. - Philippe Moser:
Locally Computed Baire's Categories on Small Complexity Classes. - Nayantara Bhatnagar, Parikshit Gopalan, Richard J. Lipton:
Symmetric Polynomials over Zm and Simultaneous Communication Protocols. - Stefan Droste, Thomas Jansen, Ingo Wegener:
Upper and Lower Bounds for Randomized Search Heuristics in Black-Box Optimization. - Piotr Berman, Marek Karpinski, Alex D. Scott:
Approximation Hardness of Short Symmetric Instances of MAX-3SAT. - Daniel Král:
Locally satisfiable formulas. - Tsuyoshi Morioka:
The Relative Complexity of Local Search Heuristics and the Iteration Principle. - Stanislav Busygin, Dmitrii V. Pasechnik:
On ~chi(G)-alpha(G)>0 gap recognition and alpha(G)-upper bounds. - Kazuo Iwama, Suguru Tamaki:
Improved Upper Bounds for 3-SAT. - Daniel Rolf:
3-SAT in RTIME(O(1.32793n)) - Improving Randomized Local Search by Initializing Strings of 3-Clauses. - Jan Krajícek:
Implicit proofs. - Piotr Berman, Marek Karpinski:
Approximability of Hypergraph Minimum Bisection. - Scott Aaronson:
Lower Bounds for Local Search by Quantum Arguments. - Vince Grolmusz:
Defying Dimensions Modulo 6. - Harumichi Nishimura, Tomoyuki Yamakami:
Polynomial time quantum computation with advice. - Danny Harnik, Moni Naor, Omer Reingold, Alon Rosen:
Completeness in Two-Party Secure Computation - A Computational View. - Jan Kára, Daniel Král:
Free Binary Decision Diagrams for Computation of EARn. - Andrei A. Krokhin, Peter Jonsson:
Recognizing Frozen Variables in Constraint Satisfaction Problems. - John M. Hitchcock:
The Size of SPP. - Vikraman Arvind, Piyush P. Kurur:
Upper Bounds on the Complexity of some Galois Theory Problems. - Hoeteck Wee:
Compressibility Lower Bounds in Oracle Settings. - Daniele Micciancio:
Almost perfect lattices, the covering radius problem, and applications to Ajtai's connection factor. - Ran Raz:
Multi-Linear Formulas for Permanent and Determinant are of Super-Polynomial Size. - Matthias Homeister:
Lower Bounds for the Sum of Graph--driven Read--Once Parity Branching Programs. - Elmar Böhler, Christian Glaßer, Daniel Meister:
Small Bounded-Error Computations and Completeness. - Amit Chakrabarti, Oded Regev:
An Optimal Randomised Cell Probe Lower Bound for Approximate Nearest Neighbour Searching. - Markus Bläser, Andreas Jakoby, Maciej Liskiewicz, Bodo Manthey:
Privacy in Non-Private Environments. - Evgeny Dantsin, Edward A. Hirsch, Alexander Wolpert:
Algorithms for SAT based on search in Hamming balls. - Amin Coja-Oghlan:
The Lovasz number of random graph. - Vince Grolmusz:
Sixtors and Mod 6 Computations. - Agostino Capponi:
A tutorial on the Deterministic two-party Communication Complexity. - Michael Langberg:
Testing the independence number of hypergraphs. - Till Tantau:
Logspace Optimisation Problems and their Approximation Properties. - Fan R. K. Chung, Ronald L. Graham, Jia Mao, Andrew Chi-Chih Yao:
Finding Favorites. - Scott Aaronson:
Multilinear Formulas and Skepticism of Quantum Computing. - Venkatesan Guruswami:
Better Extractors for Better Codes? - Valentin E. Brimkov, Bruno Codenotti, Valentino Crespi, Reneta P. Barneva, Mauro Leoncini:
Computation of the Lovász Theta Function for Circulant Graphs. - Andris Ambainis, Ke Yang:
Towards the Classical Communication Complexity of Entanglement Distillation Protocols with Incomplete Information. - Jan Arpe, Andreas Jakoby, Maciej Liskiewicz:
One-Way Communication Complexity of Symmetric Boolean Functions. - Josh Buresh-Oppenheim, Tsuyoshi Morioka:
Relativized NP Search Problems and Propositional Proof Systems. - Ke Yang:
On the (Im)possibility of Non-interactive Correlation Distillation. - Amos Beimel, Tal Malkin:
A Quantitative Approach to Reductions in Secure Computation. - Richard Beigel, Lance Fortnow, William I. Gasarch:
A Nearly Tight Bound for Private Information Retrieval Protocols.
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-12-26 00:54 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: