Fakultät für Informatik
-
Technische Universität München
Lehrstuhl für Effiziente Algorithmen
Die bibliographische Datenbank LEABib
Suchen
•
Liste der Journale
•
Liste der Serien
•
Liste der Konferenzen
•
Ausgewählte Publikationen
[1]
Hilfe
Suche: Booktitle=Proceedings of the 5th Annual Conference on Structure in Complexity Theory, CSCT'90 (Universitat Politcnica de Catalunya, Barcelona, Spain, July 8-11, 1990)
Als [
bib
] [
pdf
] [
ps
] [
dvi
] [
xml
] herunterladen.
The computational complexity of universal hashing
Y. Mansour
,
N. Nisan
,
P. Tiwari
Proceedings of the 5th Annual Conference on Structure in Complexity Theory, CSCT'90 (Universitat Politcnica de Catalunya, Barcelona, Spain, July 8-11, 1990)
, 1990, pp. 90
On polynomial time bounded truth-table reducibility of
NP
sets to sparse sets
M. Ogiwara
,
O. Watanabe
Proceedings of the 5th Annual Conference on Structure in Complexity Theory, CSCT'90 (Universitat Politcnica de Catalunya, Barcelona, Spain, July 8-11, 1990)
, 1990, pp. 2
Quantifiers and approximation
A. Panconesi
,
D. Ranjan
Proceedings of the 5th Annual Conference on Structure in Complexity Theory, CSCT'90 (Universitat Politcnica de Catalunya, Barcelona, Spain, July 8-11, 1990)
, 1990, pp. 244
Structural properties of nondeterministic complete sets
S. Homer
Proceedings of the 5th Annual Conference on Structure in Complexity Theory, CSCT'90 (Universitat Politcnica de Catalunya, Barcelona, Spain, July 8-11, 1990)
, 1990, pp. 3-10
On sets with efficient implicit membership tests
L.A. Hemachandra
,
A. Hoene
Proceedings of the 5th Annual Conference on Structure in Complexity Theory, CSCT'90 (Universitat Politcnica de Catalunya, Barcelona, Spain, July 8-11, 1990)
, 1990, pp. 11-19
On the instance complexity of
NP
-hard problems
P. Orponen
Proceedings of the 5th Annual Conference on Structure in Complexity Theory, CSCT'90 (Universitat Politcnica de Catalunya, Barcelona, Spain, July 8-11, 1990)
, 1990, pp. 20-27
E-mail and the unexpected power of interaction
L. Babai
Proceedings of the 5th Annual Conference on Structure in Complexity Theory, CSCT'90 (Universitat Politcnica de Catalunya, Barcelona, Spain, July 8-11, 1990)
, 1990, pp. 30-44
On bounded round multi-prover interactive proof systems
J.-Y. Cai
,
A. Condon
,
R.J. Lipton
Proceedings of the 5th Annual Conference on Structure in Complexity Theory, CSCT'90 (Universitat Politcnica de Catalunya, Barcelona, Spain, July 8-11, 1990)
, 1990, pp. 45-54
Privacy, additional information, and communication
R. Bar-Yehuda
,
B. Chor
,
E. Kushilevitz
Proceedings of the 5th Annual Conference on Structure in Complexity Theory, CSCT'90 (Universitat Politcnica de Catalunya, Barcelona, Spain, July 8-11, 1990)
, 1990, pp. 55-65
On the power of randomness in the decision tree model
P. Hajnal
Proceedings of the 5th Annual Conference on Structure in Complexity Theory, CSCT'90 (Universitat Politcnica de Catalunya, Barcelona, Spain, July 8-11, 1990)
, 1990, pp. 66-77
On read-once threshold formulae and their randomized decision tree complexity
R. Heiman
,
I. Newman
,
A. Wigderson
Proceedings of the 5th Annual Conference on Structure in Complexity Theory, CSCT'90 (Universitat Politcnica de Catalunya, Barcelona, Spain, July 8-11, 1990)
, 1990, pp. 78-87
Perfect hashing, graph entropy, and circuit complexity
I. Newman
,
P. Ragde
,
A. Wigderson
Proceedings of the 5th Annual Conference on Structure in Complexity Theory, CSCT'90 (Universitat Politcnica de Catalunya, Barcelona, Spain, July 8-11, 1990)
, 1990, pp. 91-99
Lower bounds on random-self-reducibility
J. Feigenbaum
,
S. Kannan
,
N. Nisan
Proceedings of the 5th Annual Conference on Structure in Complexity Theory, CSCT'90 (Universitat Politcnica de Catalunya, Barcelona, Spain, July 8-11, 1990)
, 1990, pp. 100-109
Non-uniform complexity classes and random languages
M. Mundhenk
,
R. Schuler
Proceedings of the 5th Annual Conference on Structure in Complexity Theory, CSCT'90 (Universitat Politcnica de Catalunya, Barcelona, Spain, July 8-11, 1990)
, 1990, pp. 110-119
Width-bounded reducibility and binary search over complexity classes
E. Allender
,
C. Wilson
Proceedings of the 5th Annual Conference on Structure in Complexity Theory, CSCT'90 (Universitat Politcnica de Catalunya, Barcelona, Spain, July 8-11, 1990)
, 1990, pp. 122-129
Unambiguity of circuits
K.-J. Lange
Proceedings of the 5th Annual Conference on Structure in Complexity Theory, CSCT'90 (Universitat Politcnica de Catalunya, Barcelona, Spain, July 8-11, 1990)
, 1990, pp. 130-137
A survey on counting classes
T. Gundermann
,
N.A. Nasser
,
G. Wechsung
Proceedings of the 5th Annual Conference on Structure in Complexity Theory, CSCT'90 (Universitat Politcnica de Catalunya, Barcelona, Spain, July 8-11, 1990)
, 1990, pp. 140-153
A very hard log space counting class
C. Àlvarez
,
B. Jenner
Proceedings of the 5th Annual Conference on Structure in Complexity Theory, CSCT'90 (Universitat Politcnica de Catalunya, Barcelona, Spain, July 8-11, 1990)
, 1990, pp. 154-168
The Boolean hierarchy and the polynomial hierarchy: a closer connection
R. Chang
,
J. Kadin
Proceedings of the 5th Annual Conference on Structure in Complexity Theory, CSCT'90 (Universitat Politcnica de Catalunya, Barcelona, Spain, July 8-11, 1990)
, 1990, pp. 169-178
On read-once vs.~multiple access to randomness in logspace
N. Nisan
Proceedings of the 5th Annual Conference on Structure in Complexity Theory, CSCT'90 (Universitat Politcnica de Catalunya, Barcelona, Spain, July 8-11, 1990)
, 1990, pp. 179-184
Bounded arithmetic and computational complexity
P. Clote
Proceedings of the 5th Annual Conference on Structure in Complexity Theory, CSCT'90 (Universitat Politcnica de Catalunya, Barcelona, Spain, July 8-11, 1990)
, 1990, pp. 186-199
Extensions to Barrington's
M
-program model
F. Bédard
,
F. Lemieux
,
P. McKenzie
Proceedings of the 5th Annual Conference on Structure in Complexity Theory, CSCT'90 (Universitat Politcnica de Catalunya, Barcelona, Spain, July 8-11, 1990)
, 1990, pp. 200-209
The quantifier structure of sentences that characterize nondeterministic time complexity
J.F. Lynch
Proceedings of the 5th Annual Conference on Structure in Complexity Theory, CSCT'90 (Universitat Politcnica de Catalunya, Barcelona, Spain, July 8-11, 1990)
, 1990, pp. 210-222
Circuits, pebbling and expressibility
V. Vinay
,
H. Venkateswaran
,
C.E.V. Madhavan
Proceedings of the 5th Annual Conference on Structure in Complexity Theory, CSCT'90 (Universitat Politcnica de Catalunya, Barcelona, Spain, July 8-11, 1990)
, 1990, pp. 223-230
Some connections between bounded query classes and non-uniform complexity
A. Amir
,
R. Beigel
,
W.I. Gasarch
Proceedings of the 5th Annual Conference on Structure in Complexity Theory, CSCT'90 (Universitat Politcnica de Catalunya, Barcelona, Spain, July 8-11, 1990)
, 1990, pp. 232-243
Seiten 1
2
>