![](https://dblp1.uni-trier.de/img/logo.ua.320x120.png)
![](https://dblp1.uni-trier.de/img/dropdown.dark.16x16.png)
![](https://dblp1.uni-trier.de/img/peace.dark.16x16.png)
Остановите войну!
for scientists:
![search dblp search dblp](https://dblp1.uni-trier.de/img/search.dark.16x16.png)
![search dblp](https://dblp1.uni-trier.de/img/search.dark.16x16.png)
default search action
Electronic Colloquium on Computational Complexity, 1997
Volume TR97, 1997
- Marco Cesati, Luca Trevisan:
On the Efficiency of Polynomial Time Approximation Schemes. - Richard Beigel, Alexis Maciel:
Upper and Lower Bounds for Some Depth-3 Circuit Classes. - Sanjeev Arora, Madhu Sudan:
Improved low-degree testing and its applications. - Marek Karpinski, Alexander Zelikovsky:
Approximating Dense Cases of Covering Problems. - Moni Naor, Omer Reingold:
On the Construction of Pseudo-Random Permutations: Luby-Rackoff Revisited. - Marco Cesati, Miriam Di Ianni:
Parameterized Parallel Complexity. - Stasys Jukna:
Exponential Lower Bounds for Semantic Resolution. - Noam Nisan, Ziv Bar-Yossef:
Pointer Jumping Requires Concurrent Read. - Jonathan F. Buss, Gudmund Skovbjerg Frandsen, Jeffrey O. Shallit:
The Computational Complexity of Some Problems of Linear Algebra. - Marcos A. Kiwi:
Testing and Weight Distributions of Dual Codes. - Alexander E. Andreev, Andrea E. F. Clementi, José D. P. Rolim, Luca Trevisan:
Weak Random Sources, Hitting Sets, and BPP Simulations. - Luca Trevisan:
On Local versus Global Satisfiability. - Bernd Borchert, Dietrich Kuske, Frank Stephan:
On Existentially First-Order Definable Languages and their Relation to NP. - Klaus Reinhardt, Eric Allender:
Making Nondeterminism Unambiguous. - Jan Krajícek:
Interpolation by a Game. - Manindra Agrawal, Eric Allender, Samir Datta:
On TC0, AC0, and Arithmetic Circuits. - Marek Karpinski, Juergen Wirtgen, Alexander Zelikovsky:
An Approximation Algorithm for the Bandwidth Problem on Dense Graphs. - Oded Goldreich, Shafi Goldwasser, Shai Halevi:
Eliminating Decryption Errors in the Ajtai-Dwork Cryptosystem. - Martin Sauerhoff:
A Lower Bound for Randomized Read-k-Times Branching Programs. - Oded Goldreich:
A Sample of Samplers - A Computational Perspective on Sampling (survey). - Farid M. Ablayev:
Randomization and nondeterminsm are incomparable for ordered read-once branching programs. - Gunnar Andersson, Lars Engebretsen:
Better Approximation Algorithms and Tighter Analysis for Set Splitting and Not-All-Equal Sat. - Stasys Jukna, Alexander A. Razborov, Petr Savický, Ingo Wegener:
On P versus NP \cap co-NP for Decision Trees and Read-Once Branching Programs. - Marek Karpinski:
Polynomial Time Approximation Schemes for Some Dense Instances of NP-Hard Optimization Problems. - Harald Hempel, Gerd Wechsung:
The Operators min and max on the Polynomial Hierarchy. - Jochen Meßner, Jacobo Torán:
Optimal proof systems for Propositional Logic and complete sets. - Johannes Merkle, Ralph Werchner:
On the Security of Server aided RSA protocols. - Scott E. Decatur, Oded Goldreich, Dana Ron:
Computational Sample Complexity. - Pavol Duris, Juraj Hromkovic, José D. P. Rolim, Georg Schnitger:
On the Power of Las Vegas for One-way Communication Complexity, Finite Automata, and Polynomial-time Computations. - Martin Sauerhoff:
On Nondeterminism versus Randomness for Read-Once Branching Programs. - Oded Goldreich, Shafi Goldwasser:
On the Limits of Non-Approximability of Lattice Problems. - Jan Johannsen:
Lower Bounds for Monotone Real Circuit Depth and Formula Size and Tree-like Cutting Planes. - Meena Mahajan, Venkatesh Raman:
Parametrizing Above Guaranteed Values: MaxSat and MaxCut. - Jui-Lin Lee:
Counting in Uniform TC0. - Richard Chang:
Bounded Queries, Approximations and the Boolean Hierarchy. - Meena Mahajan, V. Vinay:
Determinant: Combinatorics, Algorithms, and Complexity. - Johan Håstad:
Some optimal inapproximability results. - Johan Håstad:
Clique is hard to approximate within n1-epsilon. - Pierluigi Crescenzi, Luca Trevisan:
MAX NP-Completeness Made Easy. - Dorit Dor, Shay Halperin, Uri Zwick:
All Pairs Almost Shortest Paths. - Marek Karpinski, Juergen Wirtgen:
On Approximation Hardness of the Bandwidth Problem. - Russell Impagliazzo, Pavel Pudlák, Jirí Sgall:
Lower Bounds for the Polynomial Calculus and the Groebner Basis Algorithm. - Bruno Codenotti, Pavel Pudlák, Giovanni Resta:
Some structural properties of low rank matrices related to computational complexity. - David A. Mix Barrington, Chi-Jen Lu, Peter Bro Miltersen, Sven Skyum:
Searching constant width mazes captures the AC0 hierarchy. - Oded Goldreich, David Zuckerman:
Another proof that BPP subseteq PH (and more). - Alexander Barg:
Complexity Issues in Coding Theory. - Miklós Ajtai:
The Shortest Vector Problem in L2 is NP-hard for Randomized Reductions. - Søren Riis, Meera Sitharam:
Non-constant Degree Lower Bounds imply linear Degree Lower Bounds. - Wolfgang Maass, Michael Schmitt:
On the Complexity of Learning for Spiking Neurons with Temporal Coding. - Stanislav Zák:
A subexponential lower bound for branching programs restricted with regard to some semantic aspects. - Wolfgang Maass, Pekka Orponen:
On the Effect of Analog Noise in Discrete-Time Analog Computations. - Wolfgang Maass, Eduardo D. Sontag:
Analog Neural Nets with Gaussian or other Common Noise Distributions cannot Recognize Arbitrary Regular Languages. - Alexander E. Andreev, Juri L. Baskakov, Andrea E. F. Clementi, José D. P. Rolim:
Small Random Sets for Affine Spaces and Better Explicit Lower Bounds for Branching Programs. - Ran Raz, Gábor Tardos, Oleg Verbitsky, Nikolai K. Vereshchagin:
Arthur-Merlin Games in Boolean Decision Trees. - Bruce E. Litow:
A Decision Method for the Rational Sequence Problem. - Oded Goldreich:
Combinatorial Property Testing (a survey). - Petr Savický:
Complexity and Probability of some Boolean Formulas. - Oded Goldreich:
Notes on Levin's Theory of Average-Case Complexity. - Jin-yi Cai, Ajay Nerurkar:
Approximating the SVP to within a factor (1 + 1/dimepsilon) is NP-hard under randomized reductions. - Manindra Agrawal, Thomas Thierauf:
The Satisfiability Problem for Probabilistic Ordered Branching Programs. - Eli Biham, Dan Boneh, Omer Reingold:
Generalized Diffie-Hellman Modulo a Composite is not Weaker than Factoring.
![](https://dblp1.uni-trier.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.