Search results for "ZPP"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
220	Richard Chang 0001, Suresh Purini	Amplifying ZPP^SAT[1] and the Two Queries Problem.	CCC	2008	DBLP DOI BibTeX RDF	ZPP, amplification, bounded queries
128	Vikraman Arvind, Johannes Köbler	Graph Isomorphism Is Low for ZPP(NP) and Other Lowness Results.	STACS	2000	DBLP DOI BibTeX RDF
55	Lance Fortnow, Russell Impagliazzo, Valentine Kabanets, Christopher Umans	On the Complexity of Succinct Zero-Sum Games.	Comput. Complex.	2008	DBLP DOI BibTeX RDF	91A05, 68Q17, Subject classification. 68Q15, 03D15, 68Q32
55	Brian C. Dean, Michel X. Goemans, Jan Vondrák	Adaptivity and approximation for stochastic packing problems.	SODA	2005	DBLP BibTeX RDF
55	Lance Fortnow, Russell Impagliazzo, Valentine Kabanets, Christopher Umans	On the Complexity of Succinct Zero-Sum Games.	CCC	2005	DBLP DOI BibTeX RDF
55	Jin-yi Cai, Venkatesan T. Chakaravarthy, Lane A. Hemaspaandra, Mitsunori Ogihara	Competing Provers Yield Improved Karp-Lipton Collapse Results.	STACS	2003	DBLP DOI BibTeX RDF
55	Holger Spakowski, Mayur Thakur, Rahul Tripathi	Quantum and Classical Complexity Classes: Separations, Collapses, and Closure Properties.	FSTTCS	2003	DBLP DOI BibTeX RDF
55	Valentine Kabanets	Easiness Assumptions and Hardness Tests: Trading Time for Zero Error.	CCC	2000	DBLP DOI BibTeX RDF	probabilistic complexity classes, uniform setting, derandomization
55	Johannes Köbler, Osamu Watanabe 0001	New Collapse Consequences of NP Having Small Circuits.	ICALP	1995	DBLP DOI BibTeX RDF
36	Russell Impagliazzo, Philippe Moser	A zero one law for RP.	CCC	2003	DBLP DOI BibTeX RDF
36	Uriel Feige, Joe Kilian	Zero Knowledge and the Chromatic Number.	CCC	1996	DBLP DOI BibTeX RDF	approximation algorithms, zero knowledge, chromatic number, probabilistically checkable proofs
36	Dipika Deb, John Jose	ZPP: A Dynamic Technique to Eliminate Cache Pollution in NoC based MPSoCs.	ACM Trans. Embed. Comput. Syst.	2023	DBLP DOI BibTeX RDF
36	Thomas Watson 0001	A ZPP^NP[1] Lifting Theorem.	Electron. Colloquium Comput. Complex.	2017	DBLP BibTeX RDF
36	Philippe Moser	RP is Small in SUBEXP else ZPP equals PSPACE and NP equals EXP	Electron. Colloquium Comput. Complex.	2003	DBLP BibTeX RDF
36	Philippe Moser	ZPP is hard unless RP is small	Electron. Colloquium Comput. Complex.	2002	DBLP BibTeX RDF
18	Julia Chuzhoy, Sanjeev Khanna	Polynomial flow-cut gaps and hardness of directed cut problems.	J. ACM	2009	DBLP DOI BibTeX RDF	Directed multicut, hardness of approximation, sparsest cut
18	Khaled M. Elbassioni, Rajiv Raman 0001, Saurabh Ray, René Sitters	On the approximability of the maximum feasible subsystem problem with 0/1-coefficients.	SODA	2009	DBLP DOI BibTeX RDF
18	Pavol Hell, André Raspaud, Juraj Stacho	On Injective Colourings of Chordal Graphs.	LATIN	2008	DBLP DOI BibTeX RDF
18	Julia Chuzhoy, Sanjeev Khanna	Polynomial flow-cut gaps and hardness of directed cut problems.	STOC	2007	DBLP DOI BibTeX RDF	concurrent flow, directed multicut, directed sparsest cut, flow-cut gaps, hardness of approximation, multicommodity flow
18	Moshe Babaioff, Ron Lavi, Elan Pavlov	Single-value combinatorial auctions and implementation in undominated strategies.	SODA	2006	DBLP DOI BibTeX RDF
18	Lance Fortnow, Rahul Santhanam, Luca Trevisan	Hierarchies for semantic classes.	STOC	2005	DBLP DOI BibTeX RDF	hierarchy theorems, semantic classes, advice
18	Ronen Shaltiel, Christopher Umans	Pseudorandomness for Approximate Counting and Sampling.	CCC	2005	DBLP DOI BibTeX RDF
18	Micah Adler, Sanjeev Khanna, Rajmohan Rajaraman, Adi Rosén	Time-Constrained Scheduling of Weighted Packets on Trees and Meshes.	Algorithmica	2003	DBLP DOI BibTeX RDF	Approximation algorithm, Deadline, Packet routing
18	Evripidis Bampis, Massimiliano Caramia, Jirí Fiala 0001, Aleksei V. Fishkin, Antonio Iovanella	Scheduling of Independent Dedicated Multiprocessor Tasks.	ISAAC	2002	DBLP DOI BibTeX RDF
18	Eric Allender, Harry Buhrman, Michal Koucký 0001, Dieter van Melkebeek, Detlef Ronneburger	Power from Random Strings.	FOCS	2002	DBLP DOI BibTeX RDF
18	Aleksei V. Fishkin, Guochuan Zhang	On Maximizing the Throughput of Multiprocessor Tasks.	MFCS	2002	DBLP DOI BibTeX RDF	approximation algorithm, complexity, throughput, Multiprocessor task
18	Martin Sauerhoff	On the size of randomized OBDDs and read-once branching programs for k-stable functions.	Comput. Complex.	2001	DBLP DOI BibTeX RDF	read-once branching program, zero error, lower bounds, randomness, communication complexity, OBDD
18	Russell Impagliazzo, Valentine Kabanets, Avi Wigderson	In Search of an Easy Witness: Exponential Time vs. Probabilistic Polynomial Time.	CCC	2001	DBLP DOI BibTeX RDF
18	Lars Engebretsen, Jonas Holmerin	Clique Is Hard to Approximate within n1-o(1).	ICALP	2000	DBLP DOI BibTeX RDF
18	Michael Krivelevich, Benny Sudakov	Approximate Coloring of Uniform Hypergraphs (Extended Abstract).	ESA	1998	DBLP DOI BibTeX RDF
18	Amotz Bar-Noy, Guy Kortsarz	The Minimum Color Sum of Bipartite Graphs.	ICALP	1997	DBLP DOI BibTeX RDF
18	Christoph Karg, Johannes Köbler, Rainer Schuler	The Complexity of Generating Test Instances.	STACS	1997	DBLP DOI BibTeX RDF
18	Marek Karpinski, Rutger Verbeek	On Randomized Versus Deterministic Computation.	ICALP	1993	DBLP DOI BibTeX RDF
18	Ricard Gavaldà, José L. Balcázar	Strong and Robustly Strong Polynomial Time Reducibilities to Sparse Sets.	MFCS	1988	DBLP DOI BibTeX RDF