Electronic Colloquium on Computational Complexity, Volume 8, 2001
Volume 8, 2001
Jin-yi Cai: Essentially every unimodular matrix defines an expander.- Venkatesan Guruswami: Constructions of Codes from Number Fields.
- 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.
- 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.
- Marius Zimand: Probabilistically Checkable Proofs The Easy Way.
- Denis Xavier Charles: A Note on Subgroup Membership Problem for PSL(2,p).
- Jin-yi Cai: S_2p \subseteq ZPPNP.
- 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.
- Rustam Mubarakzjanov: Bounded-Width Probabilistic OBDDs and Read-Once Branching Programs are Incomparable.
- Rüdiger Reischuk: Approximating Schedules for Dynamic Graphs Efficiently.
- 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.
- Pavel Pudlák: On reducibility and symmetry of disjoint NP-pairs.
- Michael Schmitt: Neural Networks with Local Receptive Fields and Superlinear VC Dimension.
- Piotr Berman, Sridhar Hannenhalli, Marek Karpinski: 1.375-Approximation Algorithm for Sorting by Reversals.
- Jui-Lin Lee: Branching program, commutator, and icosahedron, part I.
- 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, 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.
- Michal Parnas, Dana Ron, Alex Samorodnitsky: Proclaiming Dictators and Juntas or Testing Boolean Formulae.
- 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 A. Legenstein, Wolfgang Maass: Total Wire Length as a Salient Circuit Complexity Measure for Sensory Processing.
- Robert A. 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 A. 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.
- 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.
- 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.
- 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.
data released under the ODC-BY 1.0 license. See also our legal information page
last updated on 2013-06-18T211851 by the dblp team