| Hits ?▲ |
Authors |
Title |
Venue |
Year |
Link |
Author keywords |
| 1 | Yosi Ben-Asher, Ilan Newman |
Decision Trees with AND, OR Queries.  |
SCT  |
1995 |
DBLP DOI BibTeX RDF |
|
| 1 | Martin Kummer |
The Instance Complexity Conjecture. |
SCT |
1995 |
DBLP DOI BibTeX RDF |
|
| 1 | James S. Royer |
Semantics versus Syntax versus Computations. |
SCT |
1995 |
DBLP DOI BibTeX RDF |
|
| 1 | Stephen A. Fenner |
Resource-Bounded Baire Category: A Stronger Approach. |
SCT |
1995 |
DBLP DOI BibTeX RDF |
|
| 1 | Jack H. Lutz |
A Small Span Theorem for P/Poly-Turing Reductions. |
SCT |
1995 |
DBLP DOI BibTeX RDF |
|
| 1 | John D. Rogers |
The Isomorphism Conjecture Holds and One-Way Functions Exist Relative to an Oracle. |
SCT |
1995 |
DBLP DOI BibTeX RDF |
|
| 1 | Stephen A. Fenner |
Inverting the Turing Jump in Complexity Theory. |
SCT |
1995 |
DBLP DOI BibTeX RDF |
|
| 1 | Kousha Etessami |
Counting Quantifiers, Successor Relations, and Logarithmic Space. |
SCT |
1995 |
DBLP DOI BibTeX RDF |
|
| 1 | Russell Impagliazzo |
A Personal View of Average-Case Complexity. |
SCT |
1995 |
DBLP DOI BibTeX RDF |
|
| 1 | |
Proceedings of the Tenth Annual Structure in Complexity Theory Conference, Minneapolis, Minnesota, USA, June 19-22, 1995 |
SCT |
1995 |
DBLP BibTeX RDF |
|
| 1 | Richard Chang 0001, William I. Gasarch, Jacobo Torán |
On Finding the Number of Graph Automorphisms. |
SCT |
1995 |
DBLP DOI BibTeX RDF |
|
| 1 | Anna Gál, Mario Szegedy |
Fault Tolerant Circuits and Probabilistically Checkable Proofs. |
SCT |
1995 |
DBLP DOI BibTeX RDF |
|
| 1 | Marius Zimand |
Weighted NP Optimization Problems: Logical Definability and Approximation Properties. |
SCT |
1995 |
DBLP DOI BibTeX RDF |
|
| 1 | Johannes Köbler |
On the Structure of Low Sets. |
SCT |
1995 |
DBLP DOI BibTeX RDF |
|
| 1 | Harry Buhrman, Elvira Mayordomo |
An Excursion to the Kolmogorov Random Strings. |
SCT |
1995 |
DBLP DOI BibTeX RDF |
|
| 1 | Sameet Agarwal, Anne Condon |
On Approximation Algorithms for Hierarchical MAX-SAT. |
SCT |
1995 |
DBLP DOI BibTeX RDF |
|
| 1 | José L. Balcázar, Elvira Mayordomo |
A Note on Genericity and Bi-Immunity. |
SCT |
1995 |
DBLP DOI BibTeX RDF |
|
| 1 | Richard Beigel, William I. Gasarch, Efim B. Kinber |
Frequency Computation and Bounded Queries. |
SCT |
1995 |
DBLP DOI BibTeX RDF |
|
| 1 | Richard Beigel, Howard Straubing |
The Power of Local Self-Reductions. |
SCT |
1995 |
DBLP DOI BibTeX RDF |
|
| 1 | Kazuo Iwama, Eiji Miyano |
Intractability of Read-Once Resolution. |
SCT |
1995 |
DBLP DOI BibTeX RDF |
|
| 1 | Yenjo Han, Thomas Thierauf |
Restricted Information from Nonadaptive Queries to NP. |
SCT |
1995 |
DBLP DOI BibTeX RDF |
|
| 1 | Chih-Long Lin |
Optimizing TRIEs for Ordered Pattern Matching is PiP2-Complete. |
SCT |
1995 |
DBLP DOI BibTeX RDF |
|
| 1 | Ulrich Hertrampf, Heribert Vollmer, Klaus W. Wagner |
On the Power of Number-Theoretic Operations with Respect to Counting. |
SCT |
1995 |
DBLP DOI BibTeX RDF |
|
| 1 | Joan Feigenbaum, Daphne Koller, Peter W. Shor |
A Game-Theoretic Classification of Interactive Complexity Classes. |
SCT |
1995 |
DBLP DOI BibTeX RDF |
|
| 1 | Nicholas Q. Trân |
On P-Immunity of Nondeterministic Complete Sets. |
SCT |
1995 |
DBLP DOI BibTeX RDF |
|
| 1 | Rainer Schuler, Osamu Watanabe 0001 |
Towards Average-Case Complexity Analysis of NP Optimization Problems. |
SCT |
1995 |
DBLP DOI BibTeX RDF |
|
| 1 | Anna Gál |
Semi-Unbounded Fan-In Circuits: Boolean vs. Arithmetic. |
SCT |
1995 |
DBLP DOI BibTeX RDF |
|
| 1 | Klaus Ambos-Spies |
Resource-Bounded Genericity. |
SCT |
1995 |
DBLP DOI BibTeX RDF |
|
| 1 | Manindra Agrawal |
DSPACE(n)=?NSPACE(n): A Degree Theoretic Characterization. |
SCT |
1995 |
DBLP DOI BibTeX RDF |
|
| 1 | Kenneth W. Regan |
On Superlinear Lower Bounds in Complexity Theory. |
SCT |
1995 |
DBLP DOI BibTeX RDF |
|
| 1 | Manindra Agrawal, Vikraman Arvind |
Reductions of Self-Reducible Sets to Depth-1 Weighted Threshold Circuit Classes, and Sparse Sets. |
SCT |
1995 |
DBLP DOI BibTeX RDF |
|
| 1 | Harry B. Hunt III, Madhav V. Marathe, Richard Edwin Stearns |
Generalized CNF Satisfiability Problems and Non-Efficient. |
SCT |
1994 |
DBLP DOI BibTeX RDF |
|
| 1 | Avi Wigderson |
NL/poly <= +/poly (Preliminary Version). |
SCT |
1994 |
DBLP DOI BibTeX RDF |
|
| 1 | Richard J. Lipton |
Some Consequences of Our Failure to Prove Non-Linear Lower Bounds on Explicit Functions. |
SCT |
1994 |
DBLP DOI BibTeX RDF |
|
| 1 | Manindra Agrawal |
On the Isomorphism Problem for Weak Reducibilities. |
SCT |
1994 |
DBLP DOI BibTeX RDF |
|
| 1 | Harry Buhrman, Leen Torenvliet |
On the Structure of Complete Sets. |
SCT |
1994 |
DBLP DOI BibTeX RDF |
|
| 1 | Lance Fortnow, Tomoyuki Yamakami |
Generic Separations. |
SCT |
1994 |
DBLP DOI BibTeX RDF |
|
| 1 | Mitsunori Ogihara |
Polynomial-Time Membership Comparable Sets. |
SCT |
1994 |
DBLP DOI BibTeX RDF |
|
| 1 | Osamu Watanabe 0001 |
Test Instance Generation for Promise NP Search Problems. |
SCT |
1994 |
DBLP DOI BibTeX RDF |
|
| 1 | Kevin J. Compton, Erich Grädel |
Logical Definability of Counting Functions. |
SCT |
1994 |
DBLP DOI BibTeX RDF |
|
| 1 | Maciej Liskiewicz, Rüdiger Reischuk |
The Complexity World below Logarithmic Space. |
SCT |
1994 |
DBLP DOI BibTeX RDF |
|
| 1 | Harry Buhrman, Jim Kadin, Thomas Thierauf |
On Functions Computable with Nonadaptive Queries to NP. |
SCT |
1994 |
DBLP DOI BibTeX RDF |
|
| 1 | Manindra Agrawal, Vikraman Arvind |
Polynomial Time Truth-Table Reductions to P-Selective Sets. |
SCT |
1994 |
DBLP DOI BibTeX RDF |
|
| 1 | Klaus-Jörn Lange, Peter Rossmanith |
Unambiguous Polynomial Hierarchies and Exponential Size. |
SCT |
1994 |
DBLP DOI BibTeX RDF |
|
| 1 | Anne Condon, Joan Feigenbaum, Carsten Lund, Peter W. Shor |
Random Debaters and the Hardness of Approximating Stochastic Functions. |
SCT |
1994 |
DBLP DOI BibTeX RDF |
|
| 1 | Deborah Joseph, Randall Pruim, Paul Young |
Collapsing Degrees in Subexponential Time. |
SCT |
1994 |
DBLP DOI BibTeX RDF |
|
| 1 | Shai Ben-David, Mauricio Karchmer, Eyal Kushilevitz |
On Ultrafilters and NP. |
SCT |
1994 |
DBLP DOI BibTeX RDF |
|
| 1 | Jack H. Lutz |
Weakly Hard Problems. |
SCT |
1994 |
DBLP DOI BibTeX RDF |
|
| 1 | Steven M. Kautz, Peter Bro Miltersen |
Relative to a Random Oracle, NP is Not Small. |
SCT |
1994 |
DBLP DOI BibTeX RDF |
|
| 1 | David A. Mix Barrington, Neil Immerman |
Time, Hardware, and Uniformity. |
SCT |
1994 |
DBLP DOI BibTeX RDF |
|
| 1 | Gábor Tardos |
Multi-Prover Encoding Schemes and Three-Prover Proof Systems. |
SCT |
1994 |
DBLP DOI BibTeX RDF |
|
| 1 | Richard Beigel, Martin Kummer, Frank Stephan 0001 |
Approximable Sets. |
SCT |
1994 |
DBLP DOI BibTeX RDF |
|
| 1 | Russell Impagliazzo, Ran Raz, Avi Wigderson |
A Direct Product Theorem. |
SCT |
1994 |
DBLP DOI BibTeX RDF |
|
| 1 | Marcos A. Kiwi, Carsten Lund, Alexander Russell, Daniel A. Spielman, Ravi Sundaram |
Alternation in Interaction. |
SCT |
1994 |
DBLP DOI BibTeX RDF |
|
| 1 | Oleg Verbitsky 0001 |
Towards the Parallel Repetition Conjecture. |
SCT |
1994 |
DBLP DOI BibTeX RDF |
|
| 1 | Sarah Mocas |
Using Bounded Query Classes to Separate Classes in the Exponential Time Hierarchy from Classes in PH. |
SCT |
1994 |
DBLP DOI BibTeX RDF |
|
| 1 | Eric Allender, Mitsunori Ogihara |
Relationships Among PL, #L, and the Determinant. |
SCT |
1994 |
DBLP DOI BibTeX RDF |
|
| 1 | Christos H. Papadimitriou, John N. Tsitsiklis |
The Complexity of Optimal Queueing Network Control. |
SCT |
1994 |
DBLP DOI BibTeX RDF |
|
| 1 | Bernd Borchert |
Predicate Classes and Promise Classes. |
SCT |
1994 |
DBLP DOI BibTeX RDF |
|
| 1 | Richard Chang 0001 |
On the Query Complexity of Clique Size and Maximum Satisfiability. |
SCT |
1994 |
DBLP DOI BibTeX RDF |
|
| 1 | Bernd Meyer 0002 |
Constructive Separation of Classes of Indistinguishable Ensembles. |
SCT |
1994 |
DBLP DOI BibTeX RDF |
|
| 1 | Birgit Jenner, Pierre McKenzie, Denis Thérien |
Logspace and Logtime Leaf Languages. |
SCT |
1994 |
DBLP DOI BibTeX RDF |
|
| 1 | Richard Beigel, Judy Goldsmith |
Downward separation fails catastrophically for limited nondeterminism classes. |
SCT |
1994 |
DBLP DOI BibTeX RDF |
|
| 1 | Harry Buhrman, Pekka Orponen |
Random Strings Make Hard Instances. |
SCT |
1994 |
DBLP DOI BibTeX RDF |
|
| 1 | Ulrich Hertrampf |
Complexity Classes Defined via k-valued Functions. |
SCT |
1994 |
DBLP DOI BibTeX RDF |
|
| 1 | |
Proceedings of the Ninth Annual Structure in Complexity Theory Conference, Amsterdam, The Netherlands, June 28 - July 1, 1994 |
SCT |
1994 |
DBLP BibTeX RDF |
|
| 1 | Pavel Pudlák |
Complexity Theory and Genetics. |
SCT |
1994 |
DBLP DOI BibTeX RDF |
|
| 1 | Ricard Gavaldà |
The Complexity of Learning with Queries. |
SCT |
1994 |
DBLP DOI BibTeX RDF |
|
| 1 | Xiangdong Yu, Moti Yung |
Space Lower-Bounds for Pseudorandom-Generators. |
SCT |
1994 |
DBLP DOI BibTeX RDF |
|
| 1 | Birgit Jenner, Jacobo Torán |
Computing Functions with Parallel Queries to NP. |
SCT |
1993 |
DBLP DOI BibTeX RDF |
|
| 1 | Phokion G. Kolaitis, Madhukar N. Thakur |
Polynomial-time Optimization, Parallel Approximation, and Fixpoint Logic (Extended Abstract). |
SCT |
1993 |
DBLP DOI BibTeX RDF |
|
| 1 | Sanjay Gupta |
Alternating Time Versus Deterministic Time: A Separation. |
SCT |
1993 |
DBLP DOI BibTeX RDF |
|
| 1 | Manindra Agrawal, Somenath Biswas |
Polynomial Isomorphism of 1-L-Complete Sets. |
SCT |
1993 |
DBLP DOI BibTeX RDF |
|
| 1 | Pierluigi Crescenzi, Riccardo Silvestri |
Sperner's Lemma and Robust Machines. |
SCT |
1993 |
DBLP DOI BibTeX RDF |
|
| 1 | José L. Balcázar, Ricard Gavaldà, Hava T. Siegelmann, Eduardo D. Sontag |
Some Structural Complexity Aspects of Neural Computation. |
SCT |
1993 |
DBLP DOI BibTeX RDF |
|
| 1 | Jay Belanger, Jie Wang 0002 |
Isomorphisms of NP Complete Problems on Random Instances. |
SCT |
1993 |
DBLP DOI BibTeX RDF |
|
| 1 | Richard Beigel |
The Polynomial Method in Circuit Complexity. |
SCT |
1993 |
DBLP DOI BibTeX RDF |
|
| 1 | Mitsunori Ogiwara, Thomas Thierauf, Seinosuke Toda, Osamu Watanabe 0001 |
On Closure Properties of #P in the Context of PF°#P. |
SCT |
1993 |
DBLP DOI BibTeX RDF |
|
| 1 | |
Proceedings of the Eigth Annual Structure in Complexity Theory Conference, San Diego, CA, USA, May 18-21, 1993 |
SCT |
1993 |
DBLP BibTeX RDF |
|
| 1 | Zhi-Zhong Chen, Seinosuke Toda |
The Complexity of Selecting Maximal Solutions. |
SCT |
1993 |
DBLP DOI BibTeX RDF |
|
| 1 | Ulrich Hertrampf, Clemens Lautemann, Thomas Schwentick, Heribert Vollmer, Klaus W. Wagner |
On the Power of Polynomial Time Bit-Reductions (Extended Abstract). |
SCT |
1993 |
DBLP DOI BibTeX RDF |
|
| 1 | Stephen A. Fenner, Lance Fortnow, Stuart A. Kurtz, Lide Li |
An Oarcle Builder's Toolkit. |
SCT |
1993 |
DBLP DOI BibTeX RDF |
|
| 1 | Nikolai K. Vereshchagin |
Relationships between NP-sets, Co-NP-sets, and P-sets relative to random oracles. |
SCT |
1993 |
DBLP DOI BibTeX RDF |
|
| 1 | Jack H. Lutz |
The Quantitative Structure of Exponential Time. |
SCT |
1993 |
DBLP DOI BibTeX RDF |
|
| 1 | Patrick W. Dymond, Faith E. Fich, Naomi Nishimura, Prabhakar Ragde, Walter L. Ruzzo |
Pointers versus Arithmetic in PRAMs. |
SCT |
1993 |
DBLP DOI BibTeX RDF |
|
| 1 | Suresh Chari, Pankaj Rohatgi |
On Completeness under Random Reductions. |
SCT |
1993 |
DBLP DOI BibTeX RDF |
|
| 1 | Johannes Köbler, Seinosuke Toda |
On the Power of Generalized MOD-Classes. |
SCT |
1993 |
DBLP DOI BibTeX RDF |
|
| 1 | Sanjeev Saluja |
Relativized limitations of left set technique and closure classes of sparse sets (Extended Abstract). |
SCT |
1993 |
DBLP DOI BibTeX RDF |
|
| 1 | Mauricio Karchmer |
On Proving Lower Bounds for Circuit Size. |
SCT |
1993 |
DBLP DOI BibTeX RDF |
|
| 1 | Jin-yi Cai, Richard J. Lipton, Robert Sedgewick, Andrew Chi-Chih Yao |
Towards Uncheatable benchmarks. |
SCT |
1993 |
DBLP DOI BibTeX RDF |
|
| 1 | Shi-Chun Tsai |
Lower Bounds on Representing Boolean Functions as Polynomials in Zm. |
SCT |
1993 |
DBLP DOI BibTeX RDF |
|
| 1 | Bin Fu |
With Quasi-linear Queries, EXP is not Polynomial Time Turing Reducible to ?Sparse Sets. |
SCT |
1993 |
DBLP DOI BibTeX RDF |
|
| 1 | Ronald Fagin, Larry J. Stockmeyer, Moshe Y. Vardi |
On Monadic NP vs. Monadic co-NP (Extended Abstract). |
SCT |
1993 |
DBLP DOI BibTeX RDF |
|
| 1 | Klaus-Jörn Lange |
Complexity and Structure in Formal Language Theory. |
SCT |
1993 |
DBLP DOI BibTeX RDF |
|
| 1 | Christos H. Papadimitriou, Mihalis Yannakakis |
On Limited Nondeterminism and the Complexity of the V.C Dimension (Extended Abstract). |
SCT |
1993 |
DBLP DOI BibTeX RDF |
|
| 1 | Harry Buhrman, Peter van Helden, Leen Torenvliet |
P-Selective Self-reducibles Sets: A New Characterization of P. |
SCT |
1993 |
DBLP DOI BibTeX RDF |
|
| 1 | David Zuckerman |
NP-Complete Problems Have a Version That's Hard to Approximate. |
SCT |
1993 |
DBLP DOI BibTeX RDF |
|
| 1 | Mauricio Karchmer, Avi Wigderson |
On Span Programs. |
SCT |
1993 |
DBLP DOI BibTeX RDF |
|
| 1 | Harry Buhrman, Luc Longpré, Edith Spaan |
SPARSE reduces conjunctively to TALLY. |
SCT |
1993 |
DBLP DOI BibTeX RDF |
|
| 1 | Tirza Hirst, David Harel |
Taking it to the Limit: On Infinite Variants of NP-Complete Problems. |
SCT |
1993 |
DBLP DOI BibTeX RDF |
|
![[Valid RSS]](Pics/valid-rss.png "Validate my RSS feed")
data released under the ODC-BY 1.0 license