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