default search action
Electronic Colloquium on Computational Complexity, 2001
Volume TR01, 2001
- Jin-yi Cai:
Essentially every unimodular matrix defines an expander. - Venkatesan Guruswami:
Constructions of Codes from Number Fields. - Lars Engebretsen, Jonas Holmerin:
Towards Optimal Lower Bounds For Clique and Chromatic Number. - Tobias Gärtner, Günter Hotz:
Recursive analytic functions of a complex variable. - Pascal Tesson, Denis Thérien:
The Computing Power of Programs over Finite Monoids. - Rocco A. Servedio:
On Learning Monotone DNF under Product Distributions. - Vered Rosen:
On the Security of Modular Exponentiation. - Eldar Fischer:
On the strength of comparisons in property testing. - Ronen Shaltiel:
Towards proving strong direct product theorems. - Oded Goldreich, Luca Trevisan:
Three Theorems regarding Testing Graph Properties. - Dima Grigoriev, Edward A. Hirsch:
Algebraic proof systems over formulas. - Evgeny Dantsin, Edward A. Hirsch, Sergei Ivanov, Maxim Vsemirnov:
Algorithms for SAT and Upper Bounds on Their Complexity. - Michal Koucký:
Log-space Constructible Universal Traversal Sequences for Cycles of Length O(n4.03). - Marcos A. Kiwi, Frédéric Magniez, Miklos Santha:
Exact and Approximate Testing/Correcting of Algebraic Functions: A Survey. - Amos Beimel, Yuval Ishai:
Information-Theoretic Private Information Retrieval: A Unified Construction. - Ran Canetti:
A unified framework for analyzing security of protocols. - Petr Savický, Detlef Sieling:
A Hierarchy Result for Read-Once Branching Programs with Restricted Parity Nondeterminism. - Omer Reingold, Salil P. Vadhan, Avi Wigderson:
Entropy Waves, the Zig-Zag Graph Product, and New Constant-Degree Expanders and Extractors. - Andris Ambainis, Harry Buhrman, William I. Gasarch, Bala Kalyanasundaram, Leen Torenvliet:
The Communication Complexity of Enumeration, Elimination, and Selection. - N. S. Narayanaswamy, C. E. Veni Madhavan:
Lower Bounds for OBDDs and Nisan's pseudorandom generator. - Ran Raz:
Resolution Lower Bounds for the Weak Pigeonhole Principle. - Rahul Santhanam:
On segregators, separators and time versus space. - Jochen Alber, Henning Fernau, Rolf Niedermeier:
Parameterized Complexity: Exponential Speed-Up for Planar Graph Problems. - Stephen A. Cook, Antonina Kolokolova:
A second-order system for polynomial-time reasoning based on Graedel's theorem. - Piotr Berman, Marek Karpinski:
Approximating Minimum Unsatisfiability of Linear Equations. - Piotr Berman, Marek Karpinski:
Approximation Hardness of Bounded Degree MIN-CSP and MIN-BISECTION. - Marius Zimand:
Probabilistically Checkable Proofs The Easy Way. - Thanh Minh Hoang, Thomas Thierauf:
The Complexity of the Minimal Polynomial. - Denis Xavier Charles:
A Note on Subgroup Membership Problem for PSL(2,p). - Jin-yi Cai:
S_2p \subseteq ZPPNP. - Eli Ben-Sasson, Nicola Galesi:
Space Complexity of Random Formulae in Resolution. - Aduri Pavan, Alan L. Selman:
Separation of NP-completeness Notions. - Eric Allender, David A. Mix Barrington, William Hesse:
Uniform Circuits for Division: Consequences and Problems. - Cristina Bazgan, Wenceslas Fernandez de la Vega, Marek Karpinski:
Polynomial Time Approximation Schemes for Dense Instances of Minimum Constraint Satisfaction. - Amir Shpilka:
Affine Projections of Symmetric Polynomials. - Amnon Ta-Shma, David Zuckerman, Shmuel Safra
:
Extractors from Reed-Muller Codes. - Rustam Mubarakzjanov:
Bounded-Width Probabilistic OBDDs and Read-Once Branching Programs are Incomparable. - Rüdiger Reischuk:
Approximating Schedules for Dynamic Graphs Efficiently. - Stasys Jukna, Stanislav Zák:
On Uncertainty versus Size in Branching Programs. - Pierre Péladeau, Denis Thérien:
On the Languages Recognized by Nilpotent Groups (a translation of "Sur les Langages Reconnus par des Groupes Nilpotents"). - Eric Allender, Michal Koucký, Detlef Ronneburger, Sambuddha Roy, V. Vinay:
Time-Space Tradeoffs in the Counting Hierarchy. - Marek Karpinski:
Approximating Bounded Degree Instances of NP-Hard Problems. - Michael V. Vyugin, Vladimir V. V'yugin:
Predictive complexity and information. - Pavel Pudlák:
On reducibility and symmetry of disjoint NP-pairs. - Michael Schmitt:
Neural Networks with Local Receptive Fields and Superlinear VC Dimension. - Oded Goldreich, Salil P. Vadhan, Avi Wigderson:
On Interactive Proofs with a Laconic Prover. - Piotr Berman, Sridhar Hannenhalli, Marek Karpinski:
1.375-Approximation Algorithm for Sorting by Reversals. - Jui-Lin Lee:
Branching program, commutator, and icosahedron, part I. - Stasys Jukna, Georg Schnitger:
On Multi-Partition Communication Complexity of Triangle-Freeness. - Ran Canetti, Joe Kilian, Erez Petrank, Alon Rosen:
Black-Box Concurrent Zero-Knowledge Requires ~Omega(log n) Rounds. - Sophie Laplante, Richard Lassaigne, Frédéric Magniez, Sylvain Peyronnet, Michel de Rougemont:
Probabilistic abstraction for model checking: An approach based on property testing. - Michael V. Vyugin, Vladimir V. V'yugin:
Non-linear Inequalities between Predictive and Kolmogorov Complexity. - Piotr Berman, Marek Karpinski:
Efficient Amplifiers and Bounded Degree Optimization. - Piotr Berman, Amir Ben-Dor, Itsik Pe'er, Roded Sharan, Ron Shamir:
On the Complexity of Positional Sequencing by Hybridization. - Alexander A. Razborov:
Improved Resolution Lower Bounds for the Weak Pigeonhole Principle. - Michael Alekhnovich, Jan Johannsen, Toniann Pitassi, Alasdair Urquhart:
An Exponential Separation between Regular and General Resolution. - Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil P. Vadhan, Ke Yang:
On the (Im)possibility of Obfuscating Programs. - Stasys Jukna:
A Note on the Minimum Number of Negations Leading to Superpolynomial Savings. - Elvira Mayordomo:
A Kolmogorov complexity characterization of constructive Hausdorff dimension. - Amir Shpilka:
Lower bounds for matrix product. - Mitsunori Ogihara, Seinosuke Toda:
The Complexity of Computing the Number of Self-Avoiding Walks in Two-Dimensional Grid Graphs and in Hypercube Graphs. - Moni Naor, Kobbi Nissim:
Communication Complexity and Secure Function Evaluation. - Michal Parnas, Dana Ron, Alex Samorodnitsky:
Proclaiming Dictators and Juntas or Testing Boolean Formulae. - Moni Naor, Omer Reingold, Alon Rosen:
Pseudo-Random Functions and Factoring. - Chandra Chekuri, Sanjeev Khanna:
Approximation Schemes for Preemptive Weighted Flow Time. - Pavol Duris, Juraj Hromkovic, Stasys Jukna, Martin Sauerhoff, Georg Schnitger:
On Multipartition Communication Complexity. - Hubie Chen:
Polynomial Programs and the Razborov-Smolensky Method. - Philippe Moser:
Relative to P, APP and promise-BPP are the same. - Robert Legenstein, Wolfgang Maass:
Optimizing the Layout of a Balanced Tree. - Robert Legenstein, Wolfgang Maass:
Total Wire Length as a Salient Circuit Complexity Measure for Sensory Processing. - Robert Legenstein, Wolfgang Maass:
Neural Circuits for Pattern Recognition with Small Total Wire Length. - Ronald Cramer, Victor Shoup:
Universal Hash Proofs and and a Paradigm for Adaptive Chosen Ciphertext Secure Public-Key Encryption. - Beate Bollig, Philipp Woelfel, Stephan Waack:
Parity Graph-driven Read-Once Branching Programs and an Exponential Lower Bound for Integer Multiplication. - Josh Buresh-Oppenheim, David G. Mitchell, Toniann Pitassi:
Linear and Negative Resolution are Weaker than Resolution. - Alexander A. Razborov:
Resolution Lower Bounds for the Weak Functional Pigeonhole Principle. - Robert Legenstein:
On the Complexity of Knock-knee Channel-Routing with 3-Terminal Nets. - Andrei A. Krokhin, Peter Jeavons, Peter Jonsson:
The complexity of constraints on intervals and lengths. - Matthias Krause:
BDD-based Cryptanalysis of Keystream Generators. - Michele Zito:
An Upper Bound on the Space Complexity of Random Formulae in Resolution. - Oded Goldreich, Howard J. Karloff, Leonard J. Schulman, Luca Trevisan:
Lower Bounds for Linear Locally Decodable Codes and Private Information Retrieval. - Palash Sarkar:
Pushdown Automaton with the Ability to Flip its Stack. - Tsuyoshi Morioka:
Classification of Search Problems and Their Definability in Bounded Arithmetic. - Nikolai K. Vereshchagin:
An enumerable undecidable set with low prefix complexity: a simplified proof. - Gerhard J. Woeginger:
When does a dynamic programming formulation guarantee the existence of an FPTAS? - Gerhard J. Woeginger:
Resource augmentation for online bounded space bin packing. - Nikolai K. Vereshchagin:
Kolmogorov Complexity Conditional to Large Integers. - Bruno Durand, Alexander Shen, Nikolai K. Vereshchagin:
Descriptive complexity of computable sequences. - Alexander Shen, Nikolai K. Vereshchagin:
Logical operations and Kolmogorov complexity. - Andrei A. Muchnik, Nikolai K. Vereshchagin:
Logical operations and Kolmogorov complexity. II. - Andreas Jakoby, Maciej Liskiewicz, Rüdiger Reischuk:
Dynamic Process Graphs and the Complexity of Scheduling. - Oded Goldreich:
Concurrent Zero-Knowledge With Timing, Revisited. - Till Tantau:
A Note on the Complexity of the Reachability Problem for Tournaments. - Boaz Barak, Oded Goldreich:
Universal Arguments and their Applications. - Jonas Holmerin:
Vertex Cover on 4-regular Hyper-graphs is Hard to Approximate Within 2-epsilon. - Hubie Chen:
Arithmetic Versions of Constant Depth Circuit Complexity Classes. - Jörg Rothe:
Some Facets of Complexity Theory and Cryptography: A Five-Lectures Tutorial. - Piotr Berman, Marek Karpinski:
Improved Approximations for General Minimum Cost Scheduling. - Ke Yang:
On Learning Correlated Boolean Functions Using Statistical Query. - Dimitrios Koukopoulos, Sotiris E. Nikoletseas, Paul G. Spirakis:
The Range of Stability for Heterogeneous and FIFO Queueing Networks. - Noga Alon, Wenceslas Fernandez de la Vega, Ravi Kannan, Marek Karpinski:
Random Sampling and Approximation of MAX-CSP Problems. - Philipp Woelfel:
A Lower Bound Technique for Restricted Branching Programs and Applications. - Oded Goldreich:
Using the FGLSS-reduction to Prove Inapproximability Results for Minimum Vertex Cover in Hypergraphs. - Dima Grigoriev, Edward A. Hirsch, Dmitrii V. Pasechnik:
Complexity of semi-algebraic proofs. - Irit Dinur, Shmuel Safra
The Importance of Being Biased.
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-12 20:59 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: