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