Electronic Colloquium on Computational Complexity, Volume 7, 2000
Volume 7, 2000
- 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.
- Russell Impagliazzo, Ronen Shaltiel, Avi Wigderson: Extractors and pseudo-random generators with optimal seed length.
- 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.
- 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.
- 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.
- 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: 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.
- 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.
- Philipp Woelfel: New Bounds on the OBDD-Size of Integer Multiplication via Universal Hashing.
- 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.
- 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.
- Martin Sauerhoff: An Improved Hierarchy Result for Partitioned BDDs.
- Martin Sauerhoff: Approximation of Boolean Functions by Combinatorial Rectangles.
- Uri Zwick: All Pairs Shortest Paths using Bridging Sets and Rectangular Matrix Multiplication.
- 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.
- Peter Auer: On Learning from Ambiguous Information.
- 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, Philip M. Long, Aravind Srinivasan: Approximating Hyper-Rectangles: Learning and Pseudo-random Sets.
- 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.
- Eldar Fischer: Testing graphs for colorability properties.
- 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.
- 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.
data released under the ODC-BY 1.0 license. See also our legal information page
last updated on 2013-06-19T201401 by the dblp team