default search action
9th SCT 1994: Amsterdam, The Netherlands
- Proceedings of the Ninth Annual Structure in Complexity Theory Conference, Amsterdam, The Netherlands, June 28 - July 1, 1994. IEEE Computer Society 1994, ISBN 0-8186-5670-0
Session 1
- Mitsunori Ogihara
:
Polynomial-Time Membership Comparable Sets. 2-11 - Richard Beigel, Martin Kummer, Frank Stephan:
Approximable Sets. 12-23 - Manindra Agrawal, Vikraman Arvind:
Polynomial Time Truth-Table Reductions to P-Selective Sets. 24-30 - Richard Chang:
On the Query Complexity of Clique Size and Maximum Satisfiability. 31-42 - Harry Buhrman, Jim Kadin, Thomas Thierauf:
On Functions Computable with Nonadaptive Queries to NP. 43-52 - Sarah Mocas:
Using Bounded Query Classes to Separate Classes in the Exponential Time Hierarchy from Classes in PH. 53-58 - Avi Wigderson:
NL/poly <= +/poly (Preliminary Version). 59-62
Session 2
- Maciej Liskiewicz, Rüdiger Reischuk:
The Complexity World below Logarithmic Space. 64-78 - Richard J. Lipton:
Some Consequences of Our Failure to Prove Non-Linear Lower Bounds on Explicit Functions. 79-87 - Russell Impagliazzo
A Direct Product Theorem. 88-96 - Shai Ben-David, Mauricio Karchmer, Eyal Kushilevitz:
On Ultrafilters and NP. 97-105 - Klaus-Jörn Lange, Peter Rossmanith:
Unambiguous Polynomial Hierarchies and Exponential Size. 106-115
Session 3
- Harry Buhrman, Leen Torenvliet:
On the Structure of Complete Sets. 118-133 - Richard Beigel, Judy Goldsmith:
Downward separation fails catastrophically for limited nondeterminism classes. 134-138 - Lance Fortnow, Tomoyuki Yamakami:
Generic Separations. 139-145 - Jack H. Lutz:
Weakly Hard Problems. 146-161 - Steven M. Kautz, Peter Bro Miltersen:
Relative to a Random Oracle, NP is Not Small. 162-174
Session 4
- David A. Mix Barrington, Neil Immerman:
Time, Hardware, and Uniformity. 176-185 - Xiangdong Yu, Moti Yung:
Space Lower-Bounds for Pseudorandom-Generators. 186-197 - Bernd Meyer:
Constructive Separation of Classes of Indistinguishable Ensembles. 198-204 - Osamu Watanabe:
Test Instance Generation for Promise NP Search Problems. 205-216 - Harry Buhrman, Pekka Orponen
Random Strings Make Hard Instances. 217-222
Session 5
- Ulrich Hertrampf:
Complexity Classes Defined via k-valued Functions. 224-234 - Bernd Borchert:
Predicate Classes and Promise Classes. 235-241 - Birgit Jenner, Pierre McKenzie, Denis Thérien:
Logspace and Logtime Leaf Languages. 242-254 - Kevin J. Compton, Erich Grädel:
Logical Definability of Counting Functions. 255-266 - Eric Allender, Mitsunori Ogihara
Relationships Among PL, #L, and the Determinant. 267-278
Session 6
- Anne Condon, Joan Feigenbaum, Carsten Lund, Peter W. Shor:
Random Debaters and the Hardness of Approximating Stochastic Functions. 280-293 - Marcos A. Kiwi, Carsten Lund, Alexander Russell
Alternation in Interaction. 294-303 - Oleg Verbitsky:
Towards the Parallel Repetition Conjecture. 304-307 - Gábor Tardos
Multi-Prover Encoding Schemes and Three-Prover Proof Systems. 308-317 - Christos H. Papadimitriou, John N. Tsitsiklis:
The Complexity of Optimal Queueing Network Control. 318-322
Session 7
- Ricard Gavaldà:
The Complexity of Learning with Queries. 324-337 - Manindra Agrawal:
On the Isomorphism Problem for Weak Reducibilities. 338-355 - Harry B. Hunt III, Madhav V. Marathe, Richard Edwin Stearns:
Generalized CNF Satisfiability Problems and Non-Efficient. 356-366 - Deborah Joseph, Randall Pruim, Paul Young:
Collapsing Degrees in Subexponential Time. 367-382 - Pavel Pudlák:
Complexity Theory and Genetics. 383-395
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-12-15 01:30 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: