default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCID12th CCC 1997: Ulm, Germany
- Proceedings of the Twelfth Annual IEEE Conference on Computational Complexity, Ulm, Germany, June 24-27, 1997. IEEE Computer Society 1997, ISBN 0-8186-7907-7
Session 1
- Harry Buhrman, Lance Fortnow, Leen Torenvliet:
Six Hypotheses in Search of a Theorem. 2-12 - Daniel Hammer, Andrei E. Romashchenko
, Alexander Shen, Nikolai K. Vereshchagin:
Inequalities for Shannon entropies and Kolmogorov complexities. 13-23 - Richard Beigel, Bin Fu:
Circuits Over PP and PL. 24-35 - Bernd Borchert, Riccardo Silvestri:
The General Notion of a Dot-Operator. 36-44 - Klaus-Jörn Lange, Pierre McKenzie, Alain Tapp:
Reversible Space Equals Deterministic Space. 45-50
Session 2
- Lance Fortnow:
Nondeterministic Polynomial Time versus Nondeterministic Logarithmic Space: Time-Space Tradeoffs for Satisfiability. 52-60 - Kenneth W. Regan:
Polynomial Vicinity Circuits and Nonlinear Lower Bounds. 61-68 - Rainer Schuler:
A Note on Universal Distributions for Polynomial-Time Computable Distributions. 69-73 - Christoph Karg:
LR(k) Testing is Average Case Complete. 74-80
Session 3
- Evgeny Dantsin, Thomas Eiter, Georg Gottlob, Andrei Voronkov:
Complexity and Expressive Power of Logic Programming. 82-101 - Stephen A. Fenner, Steven Homer, Randall J. Pruim, Marcus Schaefer:
Hyper-Polynomial Hierarchies and the NP-Jump. 102-110 - Jack H. Lutz, Yong Zhao:
The Density of Weakly Complete Problems under Adaptive Reductions. 111-120 - Klaus Ambos-Spies, Levke Bentzien:
Separating NP-Completeness Notions under Strong Hypotheses. 121-127 - Rodney G. Downey, André Nies:
Undecidability Results for Low Complexity Degree Structures. 128-132
Session 4
- Manindra Agrawal, Eric Allender, Samir Datta:
On TC0, AC0, and Arithmetic Circuits. 134-148 - Richard Beigel, Alexis Maciel:
Upper and Lower Bounds for Some Depth-3 Circuit Classes. 149-157 - Liming Cai, Jianer Chen, Johan Håstad:
Circuit Bottom Fan-in and Computational Power. 158-164 - Christer Berg, Staffan Ulfberg:
A Lower Bound for Perceptrons and an Oracle Separation of the PPPH Hierarchy. 165-172
Session 5
- Heribert Vollmer, Klaus W. Wagner:
On Operators of Higher Types. 174-184 - Maren Hinrichs, Gerd Wechsung:
Time Bounded Frequency Computations. 185-192 - Joshua Berman, Arthur Drisko, François Lemieux, Cristopher Moore, Denis Thérien:
Circuits and Expressions with NOn-Associative Gates. 193-203 - Vikraman Arvind, Jacobo Torán:
A Nonadaptive NC Checker for Permutation Group Intersection. 204-212 - Ulrich Hertrampf:
Acceptance by Transformation Monoids (with an Application to Local Self Reductions). 213-224
Session 6
- Allan Borodin, Ran El-Yaniv:
On Ranomization in Online Computation. 226-238 - László Babai, Peter G. Kimmel:
Randomized Simultaneous Messages: Solution of a Problem of Yao in Communication Complexity. 239-246 - Gábor Tardos, Uri Zwick:
The Communication Complexity of the Universal Relation. 247-259
Session 7
- Pierluigi Crescenzi:
A Short Guide to Approximation Preserving Reductions. 262-273 - Jianer Chen, Donald K. Friesen, Hao Zheng:
Tight Bound on Johnson's Algoritihm for Max-SAT. 274-281 - Sanjeev Khanna, Madhu Sudan, Luca Trevisan:
Constraint Satisfaction: The Approximability of Minimization Problems. 282-296 - Janos Simon, Shi-Chun Tsai:
A Note on the Bottleneck Counting Argument. 297-301 - Stasys Jukna:
Finite Limits and Monotone Computations: The Lower Bounds Criterion. 302-313
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 2025-12-05 22:23 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:
