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

Copyright © Mon Nov 2 21:34:17 2009 by Michael Ley (ley@uni-trier.de)