default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCID13th CCC 1998: Buffalo, New York, USA
- Proceedings of the 13th Annual IEEE Conference on Computational Complexity, Buffalo, New York, USA, June 15-18, 1998. IEEE Computer Society 1998, ISBN 0-8186-8395-3
Session 1
- D. Sivakumar:
On Membership Comparable Sets. 2-7 - Harry Buhrman, Lance Fortnow, Thomas Thierauf:
Nonrelativizing Separations. 8-12 - Harry Buhrman, Lance Fortnow:
Two Queries. 13-
Session 2
- Oded Goldreich, Madhu Sudan:
Computational Indistinguishability: A Sample Hierarchy. 24-33 - Giovanni Di Crescenzo, Russell Impagliazzo
:
Proofs of Membership vs. Proofs of Knowledge. 34-45 - Jin-yi Cai, Ajay Nerurkar:
Approximating the SVP to within a Factor is NP-Hard under Randomized Reductions. 46-
Session 3
- Ran Raz, Gábor Tardos, Oleg Verbitsky, Nikolai K. Vereshchagin:
Arthur-Merlin Games in Boolean Decision Trees. 58-67 - Amos Beimel, Anna Gál:
On Arithmetic Branching Programs. 68-80 - Manindra Agrawal, Thomas Thierauf:
The Satisfiability Problem for Probabilistic Ordered Branching Programs. 81-
Session 4
- Eric Allender, Klaus Reinhardt:
Isolation, Matching, and Counting. 92-100 - Birgit Jenner, Pierre McKenzie, Jacobo Torán:
A Note on the Hardness of Tree Isomorphism. 101-105 - Madhav V. Marathe, Harry B. Hunt III, Daniel J. Rosenkrantz, Richard Edwin Stearns:
Theory of Periodically Specified Problems: Complexity and Approximability. 106-
Survey Talk 2
- Daniel A. Spielman:
Models of Computation in Coding Theory. 120-
Session 5
- Helmut Veith:
How to Encode a Logical Structure by an OBDD. 122-131 - Johannes Köbler, Jochen Messner:
Complete Problems for Promise Classes by Optimal Proof Systems for Test Sets. 132-140 - Hartmut Klauck:
Lower Bounds for Computation with Limited Nondeterminism. 141-
Survey Talk 3
- Richard Beigel, Bin Fu:
Solving Intractable Problems with DNA Computing. 154-
Session 6
- Harry Buhrman, Dieter van Melkebeek:
Hard Sets are Hard to Find. 170-181 - Johannes Köbler, Wolfgang Lindner:
On the Resource Bounded Measure of P/poly. 182-185 - Kenneth W. Regan, D. Sivakumar:
Probabilistic Martingales and BPTIME Classes. 186-
Session 7
- Lance Fortnow, John D. Rogers:
Complexity Limitations on Quantum Computation. 202-209 - John Watrous:
Relationships Between Quantum and Classical Space-Bounded Complexity Classes. 210-227 - Rodney G. Downey, Lance Fortnow:
Uniformly Hard Languages. 228-
Session 8
- Jack H. Lutz:
Resource-Bounded Measure. 236-248 - Harry Buhrman, Leen Torenvliet:
Randomness is Hard. 249-260 - Wolfgang Lindner, Rainer Schuler, Osamu Watanabe:
Resource Bounded Measure and Learnability. 261-
Survey Talk 4
- Judy Goldsmith, Martin Mundhenk:
Complexity Issues in Markov Decision Processes. 272-280
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-01-10 18: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:
