default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDElectronic 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.
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.
last updated on 2024-11-15 19:21 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
