Electronic Colloquium on Computational Complexity, Volume 7, 2000

Volume 7, 2000

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

Last update Sat May 18 20:22:59 2013 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page