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