Searching...
Advanced Search
Table of Contents
Login to access your subscribed content
13th Annual IEEE Conference on Computational Complexity (CoCo'98)
ISBN: 0-8186-8395-3
Buffalo, New York June 15-June 18
Subscribe to this Publication
RSS feed for this Publication
This Publication
Digital Library
Advanced Search
Committees and Acknowledgements
pp. viii
PURCHASE ARTICLE: $0
ABSTRACT
PDF
HTML
IEEE
Xplore
Subscribers
Best Student Paper Award
pp. ix
PURCHASE ARTICLE: $0
ABSTRACT
PDF
HTML
IEEE
Xplore
Subscribers
Session 1
On Membership Comparable Sets
D. Sivakumar
pp. 2
PURCHASE ARTICLE: $19
ABSTRACT
PDF
HTML
IEEE
Xplore
Subscribers
Nonrelativizing Separations
H. Buhrman
L. Fortnow
T. Thierauf
pp. 8
PURCHASE ARTICLE: $19
ABSTRACT
PDF
HTML
IEEE
Xplore
Subscribers
Two Queries
H. Buhrman
L. Fortnow
pp. 13
PURCHASE ARTICLE: $19
ABSTRACT
PDF
HTML
IEEE
Xplore
Subscribers
Session 2
Computational Indistinguishability: A Sample Hierarchy
O. Goldreich
M. Sudan
pp. 24
PURCHASE ARTICLE: $19
ABSTRACT
PDF
HTML
IEEE
Xplore
Subscribers
Proofs of Membership vs. Proofs of Knowledge
G. Di Crescenzo
R. Impagliazzo
pp. 34
PURCHASE ARTICLE: $19
ABSTRACT
PDF
HTML
IEEE
Xplore
Subscribers
Approximating the SVP to within a Factor is NP-Hard under Randomized Reductions
J.-Y. Cai
A. Nerurkar
pp. 46
PURCHASE ARTICLE: $19
ABSTRACT
PDF
HTML
IEEE
Xplore
Subscribers
Session 3
Arthur-Merlin Games in Boolean Decision Trees
R. Raz
G. Tardos
O. Verbitsky
N. Vereshagin
pp. 58
PURCHASE ARTICLE: $19
ABSTRACT
PDF
HTML
IEEE
Xplore
Subscribers
On Arithmetic Branching Programs
A. Beimel
A. Gál
pp. 68
PURCHASE ARTICLE: $19
ABSTRACT
PDF
HTML
IEEE
Xplore
Subscribers
The Satisfiability Problem for Probabilistic Ordered Branching Programs
M. Agrawal
T. Thierauf
pp. 81
PURCHASE ARTICLE: $19
ABSTRACT
PDF
HTML
IEEE
Xplore
Subscribers
Session 4
Isolation, Matching, and Counting
E. Allender
K. Reinhardt
pp. 92
PURCHASE ARTICLE: $19
ABSTRACT
PDF
HTML
IEEE
Xplore
Subscribers
A Note on the Hardness of Tree Isomorphism
P. McKenzie B. Jenne
J. Torán
pp. 101
PURCHASE ARTICLE: $19
ABSTRACT
PDF
HTML
IEEE
Xplore
Subscribers
Theory of Periodically Specified Problems: Complexity and Approximability
M.V. Marathe
H.B. Hunt Iii
D.J. Rosenkrantz
R.E. Stearns
pp. 106
PURCHASE ARTICLE: $19
ABSTRACT
PDF
HTML
IEEE
Xplore
Subscribers
Survey Talk 2
Models of Computation in Coding Theory
D.A. Spielman
pp. 120
PURCHASE ARTICLE: $19
ABSTRACT
PDF
HTML
IEEE
Xplore
Subscribers
Session 5
How to Encode a Logical Structure by an OBDD
H. Veith
pp. 122
PURCHASE ARTICLE: $19
ABSTRACT
PDF
HTML
IEEE
Xplore
Subscribers
Complete Problems for Promise Classes by Optimal Proof Systems for Test Sets
J. Köbler
J. Messner
pp. 132
PURCHASE ARTICLE: $19
ABSTRACT
PDF
HTML
IEEE
Xplore
Subscribers
Lower Bounds for Computation with Limited Nondeterminism
H. Klauck
pp. 141
PURCHASE ARTICLE: $19
ABSTRACT
PDF
HTML
IEEE
Xplore
Subscribers
Survey Talk 3
Solving Intractable Problems with DNA Computing
R. Beigel
B. Fu
pp. 154
PURCHASE ARTICLE: $19
ABSTRACT
PDF
HTML
IEEE
Xplore
Subscribers
Session 6
Hard Sets are Hard to Find
H. Buhrman
D. Van Melkebeek
pp. 170
PURCHASE ARTICLE: $19
ABSTRACT
PDF
HTML
IEEE
Xplore
Subscribers
On the Resource Bounded Measure of P/poly
J. Köbler
W. Lindner
pp. 182
PURCHASE ARTICLE: $19
ABSTRACT
PDF
HTML
IEEE
Xplore
Subscribers
Probabilistic Martingales and BPTIME Classes
K.W. Regan
D. Sivakumar
pp. 186
PURCHASE ARTICLE: $19
ABSTRACT
PDF
HTML
IEEE
Xplore
Subscribers
Session 7
Complexity Limitations on Quantum Computation
L. Fortnow
J. Rogers
pp. 202
PURCHASE ARTICLE: $19
ABSTRACT
PDF
HTML
IEEE
Xplore
Subscribers
Relationships Between Quantum and Classical Space-Bounded Complexity Classes
J. Watrous
pp. 210
PURCHASE ARTICLE: $19
ABSTRACT
PDF
HTML
IEEE
Xplore
Subscribers
Uniformly Hard Languages
R. Downey
L. Fortnow
pp. 228
PURCHASE ARTICLE: $19
ABSTRACT
PDF
HTML
IEEE
Xplore
Subscribers
Session 8
Resource-Bounded Measure
J.H. Lutz
pp. 236
PURCHASE ARTICLE: $19
ABSTRACT
PDF
HTML
IEEE
Xplore
Subscribers
Randomness is Hard
H. Buhrman
L. Torenvliet
pp. 249
PURCHASE ARTICLE: $19
ABSTRACT
PDF
HTML
IEEE
Xplore
Subscribers
Resource Bounded Measure and Learnability
W. Lindner
R. Schuler
O. Watanabe
pp. 261
PURCHASE ARTICLE: $19
ABSTRACT
PDF
HTML
IEEE
Xplore
Subscribers
Survey Talk 4
Complexity Issues in Markov Decision Processes
J. Goldsmith
M. Mundhenk
pp. 272
PURCHASE ARTICLE: $19
ABSTRACT
PDF
HTML
IEEE
Xplore
Subscribers
Author Index
pp. 281
PURCHASE ARTICLE: $0
ABSTRACT
PDF
HTML
IEEE
Xplore
Subscribers
Peer Review Notice
|
Give Us Feedback
Usage of this product signifies your acceptance of the
Terms of Use
.
Open
Download
Sponsored Whitepaper
11 Best Practices
for Peer Code Review
