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

Electronic Colloquium on Computational Complexity, Volume 7, 2000

Volume 7, 2000

  1. Piotr Berman, Moses Charikar, Marek Karpinski:
    On-Line Load Balancing for Related Machines.
    Electronic Edition (link) BibTeX
  2. Michael Schmitt:
    Lower Bounds on the Complexity of Approximating Continuous Functions by Sigmoidal Neural Networks.
    Electronic Edition (link) BibTeX
  3. Matthias Krause, Hans-Ulrich Simon:
    Determining the Optimal Contrast for Secret Sharing Schemes in Visual Cryptography.
    Electronic Edition (link) BibTeX
  4. Oded Goldreich, Salil P. Vadhan, Avi Wigderson:
    Simplified derandomization of BPP using a hitting set generator.
    Electronic Edition (link) BibTeX
  5. Eli Ben-Sasson, Russell Impagliazzo, Avi Wigderson:
    Near-Optimal Separation of Treelike and General Resolution.
    Electronic Edition (link) BibTeX
  6. Elizaveta A. Okol'nishnikova:
    On Operations of Geometrical Projection and Monotone Extension.
    Electronic Edition (link) BibTeX
  7. Pavlos Efraimidis, Paul G. Spirakis:
    Randomized Approximation Schemes for Scheduling Unrelated Parallel Machines.
    Electronic Edition (link) BibTeX
  8. Albert Atserias, Nicola Galesi, Ricard Gavaldà:
    Monotone Proofs of the Pigeon Hole Principle.
    Electronic Edition (link) BibTeX
  9. Russell Impagliazzo, Ronen Shaltiel, Avi Wigderson:
    Extractors and pseudo-random generators with optimal seed length.
    Electronic Edition (link) BibTeX
  10. Amitabha Roy, Christopher Wilson:
    Supermodels and Closed Sets.
    Electronic Edition (link) BibTeX
  11. Sotiris E. Nikoletseas, Paul G. Spirakis:
    Efficient Communication Establishment in Extremely Unreliable Large Networks.
    Electronic Edition (link) BibTeX
  12. Ke Yang:
    Integer Circuit Evaluation is PSPACE-complete.
    Electronic Edition (link) BibTeX
  13. Daniel Král:
    Algebraic and Uniqueness Properties of Parity Ordered Binary Decision Diagrams and their Generalization.
    Electronic Edition (link) BibTeX
  14. Matthias Krause, Stefan Lucks:
    On Learning versus Distinguishing and the Minimal Hardware Complexity of Pseudorandom Function Generators.
    Electronic Edition (link) BibTeX
  15. Andrei A. Muchnik, Alexei L. Semenov:
    Multi-conditional Descriptions and Codes in Kolmogorov Complexity.
    Electronic Edition (link) BibTeX
  16. Michael V. Vyugin:
    Information Distance and Conditional Complexities.
    Electronic Edition (link) BibTeX
  17. Valentin E. Brimkov, Stefan S. Dantchev:
    On the Algebraic Complexity of Integer Programming.
    Electronic Edition (link) BibTeX
  18. Oliver Kullmann:
    An application of matroid theory to the SAT problem.
    Electronic Edition (link) BibTeX
  19. Edward A. Hirsch:
    Worst-case time bounds for MAX-k-SAT w.r.t. the number of variables using local search.
    Electronic Edition (link) BibTeX
  20. Oded Goldreich, Dana Ron:
    On Testing Expansion in Bounded-Degree Graphs.
    Electronic Edition (link) BibTeX
  21. Uriel Feige, Marek Karpinski, Michael Langberg:
    Improved Approximation of MAX-CUT on Graphs of Bounded Degree.
    Electronic Edition (link) BibTeX
  22. Rosario Gennaro, Luca Trevisan:
    Lower Bounds on the Efficiency of Generic Cryptographic Constructions.
    Electronic Edition (link) BibTeX
  23. Michael Alekhnovich, Eli Ben-Sasson, Alexander A. Razborov, Avi Wigderson:
    Pseudorandom Generators in Propositional Proof Complexity.
    Electronic Edition (link) BibTeX
  24. Amihood Amir, Richard Beigel, William I. Gasarch:
    Some Connections between Bounded Query Classes and Non-Uniform Complexity.
    Electronic Edition (link) BibTeX
  25. Paul Beame, Michael E. Saks, Xiaodong Sun, Erik Vee:
    Super-Linear Time-Space Tradeoff Lower Bounds for Randomized Computation.
    Electronic Edition (link) BibTeX
  26. Andrei E. Romashchenko, Alexander Shen, Nikolai K. Vereshchagin:
    Combinatorial Interpretation of Kolmogorov Complexity.
    Electronic Edition (link) BibTeX
  27. Pavol Duris, Juraj Hromkovic, Katsushi Inoue:
    A Separation of Determinism, Las Vegas and Nondeterminism for Picture Recognition.
    Electronic Edition (link) BibTeX
  28. Lance Fortnow, Dieter van Melkebeek:
    Time-Space Tradeoffs for Nondeterministic Computation.
    Electronic Edition (link) BibTeX
  29. Ran Raz, Amir Shpilka:
    Lower Bounds for Matrix Product, in Bounded Depth Circuits with Arbitrary Gates.
    Electronic Edition (link) BibTeX
  30. Wolfgang Maass:
    A Simple Model for Neural Computation with Firing Rates and Firing Correlations .
    Electronic Edition (link) BibTeX
  31. Wolfgang Maass, Eduardo D. Sontag:
    Neural Systems as Nonlinear Filters.
    Electronic Edition (link) BibTeX
  32. Wolfgang Maass:
    On the Computational Power of Winner-Take-All.
    Electronic Edition (link) BibTeX
  33. Jan Krajícek:
    Tautologies from pseudo-random generators.
    Electronic Edition (link) BibTeX
  34. Valentine Kabanets, Charles Rackoff, Stephen Cook:
    Efficiently Approximable Real-Valued Functions.
    Electronic Edition (link) BibTeX
  35. Nikolai K. Vereshchagin, Michael V. Vyugin:
    Independent minimum length programs to translate between given strings.
    Electronic Edition (link) BibTeX
  36. Carsten Damm, Markus Holzer, Pierre McKenzie:
    The Complexity of Tensor Calculus.
    Electronic Edition (link) BibTeX
  37. Jens Gramm, Edward A. Hirsch, Rolf Niedermeier, Peter Rossmanith:
    New Worst-Case Upper Bounds for MAX-2-SAT with Application to MAX-CUT.
    Electronic Edition (link) BibTeX
  38. Wolfgang Maass:
    On Computation with Pulses.
    Electronic Edition (link) BibTeX
  39. Yevgeniy Dodis:
    Impossibility of Black-Box Reduction from Non-Adaptively to Adaptively Secure Coin-Flipping.
    Electronic Edition (link) BibTeX
  40. Maria Isabel Gonzalez Vasco, Igor Shparlinski:
    Security of the Most Significant Bits of the Shamir Message Passing Scheme.
    Electronic Edition (link) BibTeX
  41. Igor Shparlinski:
    Security of Polynomial Transformations of the Diffie--Hellma.
    Electronic Edition (link) BibTeX
  42. Lars Engebretsen:
    Lower Bounds for non-Boolean Constraint Satisfaction.
    Electronic Edition (link) BibTeX
  43. Uriel Feige, Marek Karpinski, Michael Langberg:
    A Note on Approximating MAX-BISECTION on Regular Graphs.
    Electronic Edition (link) BibTeX
  44. Tzvika Hartman, Ran Raz:
    On the Distribution of the Number of Roots of Polynomials and Explicit Logspace Extractors.
    Electronic Edition (link) BibTeX
  45. Maria Isabel Gonzalez Vasco, Igor Shparlinski:
    On the Security of Diffie-Hellman Bits.
    Electronic Edition (link) BibTeX
  46. Philipp Woelfel:
    New Bounds on the OBDD-Size of Integer Multiplication via Universal Hashing.
    Electronic Edition (link) BibTeX
  47. Tobias Polzin, Siavash Vahdati Daneshmand:
    Primal-Dual Approaches to the Steiner Problem.
    Electronic Edition (link) BibTeX
  48. Beate Bollig:
    Restricted Nondeterministic Read-Once Branching Programs and an Exponential Lower Bound for Integer Multiplication.
    Electronic Edition (link) BibTeX
  49. Herbert Fleischner, Stefan Szeider:
    Polynomial-Time Recognition of Minimal Unsatisfiable Formulas with Fixed Clause-Variable Difference.
    Electronic Edition (link) BibTeX
  50. Peter Auer, Philip M. Long, Wolfgang Maass, Gerhard J. Woeginger:
    On the Complexity of Function Learning.
    Electronic Edition (link) BibTeX
  51. Marek Karpinski, Miroslaw Kowaluk, Andrzej Lingas:
    Approximation Algorithms for MAX-BISECTION on Low Degree Reg ular Graphs and Planar Graphs.
    Electronic Edition (link) BibTeX
  52. Beate Bollig, Ingo Wegener:
    Approximability and Nonapproximability by Binary Decision Diagrams.
    Electronic Edition (link) BibTeX
  53. Alexander E. Andreev, Andrea E. F. Clementi, Paolo Penna, José D. P. Rolim:
    Parallel Read Operations Without Memory Contention.
    Electronic Edition (link) BibTeX
  54. Andrea E. F. Clementi, Paolo Penna, Riccardo Silvestri:
    On the power assignment problem in radio networks.
    Electronic Edition (link) BibTeX
  55. Peter Auer, Stephen Kwek, Wolfgang Maass, Manfred K. Warmuth:
    Learning of Depth Two Neural Networks with Constant Fan-in at the Hidden Nodes.
    Electronic Edition (link) BibTeX
  56. Oded Goldreich, Avi Wigderson:
    On Pseudorandomness with respect to Deterministic Observers.
    Electronic Edition (link) BibTeX
  57. Martin Sauerhoff:
    An Improved Hierarchy Result for Partitioned BDDs.
    Electronic Edition (link) BibTeX
  58. Martin Sauerhoff:
    Approximation of Boolean Functions by Combinatorial Rectangles.
    Electronic Edition (link) BibTeX
  59. Omer Reingold, Ronen Shaltiel, Avi Wigderson:
    Extracting Randomness via Repeated Condensing.
    Electronic Edition (link) BibTeX
  60. Uri Zwick:
    All Pairs Shortest Paths using Bridging Sets and Rectangular Matrix Multiplication.
    Electronic Edition (link) BibTeX
  61. Prahladh Harsha, Madhu Sudan:
    Small PCPs with low query complexity.
    Electronic Edition (link) BibTeX
  62. Venkatesan Guruswami, Johan Håstad, Madhu Sudan:
    Hardness of approximate hypergraph coloring.
    Electronic Edition (link) BibTeX
  63. Peter Auer:
    On-line Learning of Rectangles in Noisy Environments.
    Electronic Edition (link) BibTeX
  64. Klaus Jansen, Marek Karpinski, Andrzej Lingas:
    A Polynomial Time Approximation Scheme for MAX-BISECTION on Planar Graphs.
    Electronic Edition (link) BibTeX
  65. Eric Allender, David A. Mix Barrington:
    Uniform Circuits for Division: Consequences and Problems.
    Electronic Edition (link) BibTeX
  66. Peter Auer:
    On Learning from Ambiguous Information.
    Electronic Edition (link) BibTeX
  67. Peter Auer, Philip M. Long:
    Simulating Access to Hidden Information while Learning.
    Electronic Edition (link) BibTeX
  68. Peter Auer, Nicolò Cesa-Bianchi, Yoav Freund, Robert E. Schapire:
    Gambling in a rigged casino: The adversarial multi-armed bandit problem.
    Electronic Edition (link) BibTeX
  69. Peter Auer:
    Learning Nested Differences in the Presence of Malicious Noise.
    Electronic Edition (link) BibTeX
  70. Peter Auer, Manfred K. Warmuth:
    Tracking the best disjunction.
    Electronic Edition (link) BibTeX
  71. Peter Auer, Nicolò Cesa-Bianchi:
    On-line Learning with Malicious Noise and the Closure Algorithm.
    Electronic Edition (link) BibTeX
  72. Peter Auer, Philip M. Long, Aravind Srinivasan:
    Approximating Hyper-Rectangles: Learning and Pseudo-random Sets.
    Electronic Edition (link) BibTeX
  73. Venkatesan Guruswami, Sanjeev Khanna:
    On the Hardness of 4-coloring a 3-colorable Graph.
    Electronic Edition (link) BibTeX
  74. Daniele Micciancio, Bogdan Warinschi:
    A Linear Space Algorithm for Computing the Hermite Normal Form.
    Electronic Edition (link) BibTeX
  75. Andreas Klein, Martin Kutrib:
    Deterministic Turing Machines in the Range between Real-Time and Linear-Time.
    Electronic Edition (link) BibTeX
  76. Juraj Hromkovic, Juhani Karhumäki, Hartmut Klauck, Georg Schnitger, Sebastian Seibert:
    Measures of Nondeterminism in Finite Automata.
    Electronic Edition (link) BibTeX
  77. Till Tantau:
    On the Power of Extra Queries to Selective Languages.
    Electronic Edition (link) BibTeX
  78. Jean-Pierre Seifert:
    Using fewer Qubits in Shor's Factorization Algorithm via Simultaneous Diophantine Approximation.
    Electronic Edition (link) BibTeX
  79. Mark Jerrum, Eric Vigoda:
    A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries.
    Electronic Edition (link) BibTeX
  80. Marco Cesati:
    Perfect Code is W[1]-complete.
    Electronic Edition (link) BibTeX
  81. Shin Aida, Rainer Schuler, Tatsuie Tsukiji, Osamu Watanabe:
    On the difference between polynomial-time many-one and truth-table reducibilities on distributional problems.
    Electronic Edition (link) BibTeX
  82. Lefteris M. Kirousis, Phokion G. Kolaitis:
    The Complexity of Minimal Satisfiability Problems.
    Electronic Edition (link) BibTeX
  83. Eldar Fischer:
    Testing graphs for colorability properties.
    Electronic Edition (link) BibTeX
  84. Amit Sahai, Salil P. Vadhan:
    A Complete Problem for Statistical Zero Knowledge.
    Electronic Edition (link) BibTeX
  85. Rustam Mubarakzjanov:
    Probabilistic OBDDs: on Bound of Width versus Bound of Error .
    Electronic Edition (link) BibTeX
  86. Michael Schmitt:
    On the Complexity of Computing and Learning with Multiplicative Neural Networks.
    Electronic Edition (link) BibTeX
  87. Albert Atserias, Nicola Galesi, Pavel Pudlák:
    Monotone simulations of nonmonotone propositional proofs.
    Electronic Edition (link) BibTeX
  88. Meena Mahajan, V. Vinay:
    A note on the hardness of the characteristic polynomial.
    Electronic Edition (link) BibTeX
  89. Lars Engebretsen, Marek Karpinski:
    Approximation Hardness of TSP with Bounded Metrics.
    Electronic Edition (link) BibTeX
  90. Oded Goldreich:
    Candidate One-Way Functions Based on Expander Graphs.
    Electronic Edition (link) BibTeX
  91. Cristina Bazgan, Wenceslas Fernandez de la Vega, Marek Karpinski:
    Approximability of Dense Instances of NEAREST CODEWORD Problem.
    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)