dblp.uni-trier.de www.uni-trier.de

Electronic Colloquium on Computational Complexity, Volume 8, 2001

Volume 8, 2001

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

Home | Conferences | Journals | Series | FAQ — Search: Faceted | Complete | Author
Copyright © Sat May 16 23:57:48 2009 by Michael Ley (ley@uni-trier.de)