Search results for "lowness"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
242	Steffen Reith, Klaus W. Wagner	On Boolean Lowness and Boolean Highness.	COCOON	1998	DBLP DOI BibTeX RDF	lowness, highness, boolean lowness, boolean highness, boolean hierarchy, hard/easy, Computational complexity, advice, polynomial-time hierarchy, collapse
73	Hong-Zhou Li, Guan-Ying Li	Nonuniform Lowness and Strong Nonuniform Lowness.	ISAAC	1994	DBLP DOI BibTeX RDF
69	Vikraman Arvind, Johannes Köbler	Graph Isomorphism Is Low for ZPP(NP) and Other Lowness Results.	STACS	2000	DBLP DOI BibTeX RDF
52	Hongzhou Li, Guanying Li	Nonuniform lowness and strong nonuniform lowness.	J. Comput. Sci. Technol.	1995	DBLP DOI BibTeX RDF
47	Liang Yu	Lowness for genericity.	Arch. Math. Log.	2006	DBLP DOI BibTeX RDF	Mathematics Subject Classification (2000) 03D80
47	Stephen A. Fenner	PP-Lowness and a Simple Definition of AWPP.	Theory Comput. Syst.	2003	DBLP DOI BibTeX RDF
47	N. V. Vinodchandran	Improved Lowness Results for Solvable Black-box Group Problems.	FSTTCS	1997	DBLP DOI BibTeX RDF
47	Vikraman Arvind, Johannes Köbler, Martin Mundhenk	Lowness and the Complexity of Sparse and Tally Descriptions.	ISAAC	1992	DBLP DOI BibTeX RDF
43	Ming-Jye Sheu, Timothy J. Long	UP and the Low and High Hierarchies: A Relativized Separation.	ICALP	1992	DBLP DOI BibTeX RDF
26	Klaus Ambos-Spies, Rod Downey, Martin Monath	Lowness properties for strong reducibilities and the computational power of maximal sets.	Comput.	2024	DBLP DOI BibTeX RDF
26	Artem Chernikov, Byunghan Kim, Nicholas Ramsey	Transitivity, Lowness, and ranks in Nsop Theories.	J. Symb. Log.	2023	DBLP DOI BibTeX RDF
26	Johanna N. Y. Franklin, Reed Solomon	Lowness for isomorphism, countable ideals, and computable traceability.	Math. Log. Q.	2020	DBLP DOI BibTeX RDF
26	Johanna N. Y. Franklin, Timothy H. McNicholl	Degrees of and lowness for isometric isomorphism.	J. Log. Anal.	2020	DBLP BibTeX RDF
26	Philippe Moser	Polylog depth, highness and lowness for E.	Inf. Comput.	2020	DBLP DOI BibTeX RDF
26	Noam Greenberg, Rutger Kuyper, Dan Turetsky	Cardinal invariants, non-lowness classes, and Weihrauch reducibility.	Comput.	2019	DBLP DOI BibTeX RDF
26	Johanna N. Y. Franklin, Dan Turetsky	Lowness for isomorphism and degrees of genericity.	Comput.	2018	DBLP DOI BibTeX RDF
26	Rod Downey, Michael McInerney, Keng Meng Ng	Lowness and logical depth.	Theor. Comput. Sci.	2017	DBLP DOI BibTeX RDF
26	André Nies	Lowness, Randomness, and Computable Analysis.	Computability and Complexity	2017	DBLP DOI BibTeX RDF
26	Philippe Moser	Polynomial Depth, Highness and Lowness for E.	CoRR	2016	DBLP BibTeX RDF
26	Ian Herbert	Lowness for integer-valued randomness.	Comput.	2016	DBLP DOI BibTeX RDF
26	Johannes Köbler, Jacobo Torán	Lowness results: the next generation.	Bull. EATCS	2015	DBLP BibTeX RDF
26	Takayuki Kihara, Kenshi Miyabe	Unified characterizations of lowness properties via Kolmogorov complexity.	Arch. Math. Log.	2015	DBLP DOI BibTeX RDF
26	Laurent Bienvenu, Rod Downey, Noam Greenberg, André Nies, Daniel Turetsky	Characterizing Lowness for Demuth Randomness.	J. Symb. Log.	2014	DBLP DOI BibTeX RDF
26	David Diamondstone, Johanna N. Y. Franklin	Lowness for Difference Tests.	Notre Dame J. Formal Log.	2014	DBLP DOI BibTeX RDF
26	Steffen Lempp, Joseph S. Miller, Keng Meng Ng, Daniel D. Turetsky, Rebecca Weber	Lowness for effective Hausdorff dimension.	J. Math. Log.	2014	DBLP DOI BibTeX RDF
26	Rod Downey, Keng Meng Ng	Lowness for bounded randomness.	Theor. Comput. Sci.	2012	DBLP DOI BibTeX RDF
26	Laurent Bienvenu, Joseph S. Miller	Randomness and lowness notions via open covers.	Ann. Pure Appl. Log.	2012	DBLP DOI BibTeX RDF
26	Bjørn Kjos-Hanssen, Joseph S. Miller, Reed Solomon	Lowness notions, measure and domination.	J. Lond. Math. Soc.	2012	DBLP DOI BibTeX RDF
26	Noam Greenberg, André Nies	Benign cost functions and lowness properties.	J. Symb. Log.	2011	DBLP DOI BibTeX RDF
26	Noam Greenberg, Joseph S. Miller	Lowness for Kurtz randomness.	J. Symb. Log.	2009	DBLP DOI BibTeX RDF
26	Rod Downey, Keng Meng Ng	Lowness for Demuth Randomness.	CiE	2009	DBLP DOI BibTeX RDF
26	George Barmpalias, Andrew E. M. Lewis, Mariya Ivanova Soskova	Randomness, lowness and degrees.	J. Symb. Log.	2008	DBLP DOI BibTeX RDF
26	Santiago Figueira, André Nies, Frank Stephan 0001	Lowness properties and approximations of the jump.	Ann. Pure Appl. Log.	2008	DBLP DOI BibTeX RDF
26	Rod Downey, André Nies, Rebecca Weber, Liang Yu	Lowness and Π20 nullsets.	J. Symb. Log.	2006	DBLP DOI BibTeX RDF
26	Frank Stephan 0001, Liang Yu	Lowness for Weakly 1-generic and Kurtz-Random.	TAMC	2006	DBLP DOI BibTeX RDF
26	Santiago Figueira, André Nies, Frank Stephan 0001	Lowness Properties and Approximations of the Jump.	WoLLIC	2005	DBLP DOI BibTeX RDF
26	Bjørn Kjos-Hanssen, André Nies, Frank Stephan 0001	Lowness for the Class of Schnorr Random Reals.	SIAM J. Comput.	2005	DBLP DOI BibTeX RDF
26	Benjamín René Callejas Bedregal, André Nies	Lowness Properties of Reals and Hyper-Immunity.	WoLLIC	2003	DBLP DOI BibTeX RDF
26	Vikraman Arvind, Johannes Köbler	New Lowness Results for ZPPNP and Other Complexity Classes.	J. Comput. Syst. Sci.	2002	DBLP DOI BibTeX RDF
26	Stephen A. Fenner	PP-lowness and a simple definition of AWPP	Electron. Colloquium Comput. Complex.	2002	DBLP BibTeX RDF
26	Sebastiaan Terwijn, Domenico Zambella	Computational Randomness and Lowness.	J. Symb. Log.	2001	DBLP DOI BibTeX RDF
26	Steffen Reith, Klaus W. Wagner	On boolean lowness and boolean highness.	Theor. Comput. Sci.	2001	DBLP DOI BibTeX RDF
26	Antonín Kucera 0002, Sebastiaan Terwijn	Lowness for The Class of Random Sets.	J. Symb. Log.	1999	DBLP DOI BibTeX RDF
26	Vikraman Arvind, Johannes Köbler	Graph Isomorphism is Low for ZPPNP and other Lowness results.	Electron. Colloquium Comput. Complex.	1999	DBLP BibTeX RDF
26	Jack H. Lutz	Observations on Measure and Lowness for \Delta^p_2.	Theory Comput. Syst.	1997	DBLP DOI BibTeX RDF
26	Jack H. Lutz	Observations on Measure and Lowness for Delta^P_2.	STACS	1996	DBLP DOI BibTeX RDF
26	Lane A. Hemaspaandra	Lowness: a yardstick for NP-P.	SIGACT News	1993	DBLP DOI BibTeX RDF
26	Uwe Schöning	Probabilistic Complexity Classes and Lowness.	J. Comput. Syst. Sci.	1989	DBLP DOI BibTeX RDF
26	Andrew Klapper	Generalized Lowness and Highness and Probabilistic Complexity Classes.	Math. Syst. Theory	1989	DBLP DOI BibTeX RDF
26	Ronald V. Book, Pekka Orponen, David A. Russo, Osamu Watanabe 0001	Lowness Properties of Sets in the Exponential-Time Hierarchy.	SIAM J. Comput.	1988	DBLP DOI BibTeX RDF
26	Uwe Schöning	Probabilistic complexity classes and lowness.	SCT	1987	DBLP BibTeX RDF
26	José L. Balcázar, Ronald V. Book, Uwe Schöning	Sparse Sets, Lowness and Highness.	SIAM J. Comput.	1986	DBLP DOI BibTeX RDF
26	Ronald V. Book, Pekka Orponen, David A. Russo, Osamu Watanabe 0001	On Exponential Lowness.	ICALP	1986	DBLP DOI BibTeX RDF
26	José L. Balcázar, Ronald V. Book, Uwe Schöning	Sparse Oracles, Lowness, and Highness.	MFCS	1984	DBLP DOI BibTeX RDF
26	Victor L. Bennison, Robert I. Soare	Some Lowness Properties and Computational Complexity Sequences.	Theor. Comput. Sci.	1978	DBLP DOI BibTeX RDF
21	Laurent Bienvenu, Wolfgang Merkle	Reconciling Data Compression and Kolmogorov Complexity.	ICALP	2007	DBLP DOI BibTeX RDF
21	Stephen A. Fenner, Steven Homer, Mitsunori Ogiwara, Alan L. Selman	On Using Oracles That Compute Values.	STACS	1993	DBLP DOI BibTeX RDF
21	Eric Allender, Lane A. Hemachandra	Lower Bounds for the Low Hierarchy (Extended Abstract).	ICALP	1989	DBLP DOI BibTeX RDF
21	Uwe Schöning	Robust Orale Machines.	MFCS	1988	DBLP DOI BibTeX RDF
21	Jürgen Kämper	Non-Uniform Proof System: A New Framework to Describe Non-Uniform and Probabalistic Complexity Classes.	FSTTCS	1988	DBLP DOI BibTeX RDF