![](https://dblp.dagstuhl.de/img/logo.ua.320x120.png)
![](https://dblp.dagstuhl.de/img/dropdown.dark.16x16.png)
![](https://dblp.dagstuhl.de/img/peace.dark.16x16.png)
Остановите войну!
for scientists:
![search dblp search dblp](https://dblp.dagstuhl.de/img/search.dark.16x16.png)
![search dblp](https://dblp.dagstuhl.de/img/search.dark.16x16.png)
default search action
Electronic Colloquium on Computational Complexity, 2000
Volume TR00, 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 S. 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. - María Isabel González Vasco, Igor E. Shparlinski:
Security of the Most Significant Bits of the Shamir Message Passing Scheme. - Igor E. 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. - María Isabel González Vasco, Igor E. 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.
![](https://dblp.dagstuhl.de/img/cog.dark.24x24.png)
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.