![](https://dblp.dagstuhl.de/img/logo.ua.320x120.png)
![](https://dblp.dagstuhl.de/img/dropdown.dark.16x16.png)
![](https://dblp.dagstuhl.de/img/peace.dark.16x16.png)
Остановите войну!
for scientists:
![search dblp search dblp](https://dblp.dagstuhl.de/img/search.dark.16x16.png)
![search dblp](https://dblp.dagstuhl.de/img/search.dark.16x16.png)
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.
![](https://dblp.dagstuhl.de/img/cog.dark.24x24.png)
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.