Search results for "68Q15"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
48	Arnold Beckmann	Resolution Refutations and Propositional Proofs with Height-Restrictions.	CSL	2002	DBLP DOI BibTeX RDF	Height of proofs, Length of proofs, Resolution refutation, Frege systems, Order induction principle, Cut introduction, MSC: Primary 03F20, Secondary 03F07, 68R99, Cut elimination, 68Q15, Bounded arithmetic, Propositional calculus
48	Martin Hofmann 0001	The Strength of Non-size-increasing Computation (Introduction and Summary).	MFCS	2001	DBLP DOI BibTeX RDF	semantics AMS Classification: 03D15, 03C13, computational complexity, 68Q15, higher-order functions, finite model, 68Q55
18	Peter Bürgisser, Felipe Cucker	Exotic Quantifiers, Complexity Classes, and Complete Problems.	Found. Comput. Math.	2009	DBLP DOI BibTeX RDF	Mathematics Subject Classification (2000) 68Q15, 68Q17
18	Ali Juma, Valentine Kabanets, Charles Rackoff, Amir Shpilka	The Black-Box Query Complexity of Polynomial Summation.	Comput. Complex.	2009	DBLP DOI BibTeX RDF	Subject classification. 68Q05, 68Q17, 68Q25, 68Q15
18	Julia Kempe, Hirotada Kobayashi, Keiji Matsumoto, Thomas Vidick	Using Entanglement in Quantum Multi-Prover Interactive Proofs.	Comput. Complex.	2009	DBLP DOI BibTeX RDF	Subject classification. 03D15, 81P68, 68Q15, 68Q10
18	Aduri Pavan, N. V. Vinodchandran	2-Local Random Reductions to 3-Valued Functions.	Comput. Complex.	2008	DBLP DOI BibTeX RDF	68Q17, Subject classification. 68Q15
18	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
18	Oded Lachish, Ilan Newman, Asaf Shapira	Space Complexity Vs. Query Complexity.	Comput. Complex.	2008	DBLP DOI BibTeX RDF	Subject classification. 68Q15, 68Q10
18	John M. Hitchcock, Aduri Pavan	Hardness Hypotheses, Derandomization, and Circuit Complexity.	Comput. Complex.	2008	DBLP DOI BibTeX RDF	68Q30, 68Q17, Subject classification. 68Q15
18	Alexander Healy	Randomness-Efficient Sampling within NC1.	Comput. Complex.	2008	DBLP DOI BibTeX RDF	68Q15, 68R10, Subject classification. 68Q10
18	Alexander A. Sherstov	Halfspace Matrices.	Comput. Complex.	2008	DBLP DOI BibTeX RDF	Subject classification. 03D15, 68Q17, 68Q15
18	R. Ryan Williams	Time-Space Tradeoffs for Counting NP Solutions Modulo Integers.	Comput. Complex.	2008	DBLP DOI BibTeX RDF	68Q17, Subject classification. 68Q15
18	Xiaoyang Gu, Jack H. Lutz	Dimension Characterizations of Complexity Classes.	Comput. Complex.	2008	DBLP DOI BibTeX RDF	Subject classification, 68Q15
18	Marius Zimand	Exposure-Resilient Extractors and the Derandomization of Probabilistic Sublinear Time.	Comput. Complex.	2008	DBLP DOI BibTeX RDF	Subject classification, 68Q15
18	Shahar Sarid, Amir Shapiro	Classifying the multi robot path finding problem into a quadratic competitive complexity class.	Ann. Math. Artif. Intell.	2008	DBLP DOI BibTeX RDF	Mathematics Subject Classifications (2000) 68Q25, 68T40, 11Y16, 93C85, 68Q17, 68Q15, 68W40, 68W15
18	Masahiro Kumabe, Toshio Suzuki, Takeshi Yamazaki	Does truth-table of linear norm reduce the one-query tautologies to a random oracle?	Arch. Math. Log.	2008	DBLP DOI BibTeX RDF	Mathematics Subject Classification (2000) 68Q15, 03D15
18	Manuel Lameiras Campagnolo, Kerry Ojakian	The elementary computable functions over the real numbers: applying two new techniques.	Arch. Math. Log.	2008	DBLP DOI BibTeX RDF	Mathematics Subject Classification (2000) 68Q15
18	Martin Beaudry, Markus Holzer 0001	The Complexity of Tensor Circuit Evaluation.	Comput. Complex.	2007	DBLP DOI BibTeX RDF	Subject classification. 15A69, 68Q70, 68Q17, 68Q15, 68Q05
18	Dan Gutfreund, Ronen Shaltiel, Amnon Ta-Shma	If NP Languages are Hard on the Worst-Case, Then it is Easy to Find Their Hard Instances.	Comput. Complex.	2007	DBLP DOI BibTeX RDF	68Q17, 68Q15, 94A60, Subject classification. 68Q10
18	Prahladh Harsha, Yuval Ishai, Joe Kilian, Kobbi Nissim, Srinivasan Venkatesh 0001	Communication vs. Computation.	Comput. Complex.	2007	DBLP DOI BibTeX RDF	68Q17, Subject classification. 68Q15
18	Dieter van Melkebeek, Konstantin Pervyshev	A Generic Time Hierarchy with One Bit of Advice.	Comput. Complex.	2007	DBLP DOI BibTeX RDF	Subject classification. 68Q15, 68Q10
18	Rocco A. Servedio	Every Linear Threshold Function has a Low-Weight Approximator.	Comput. Complex.	2007	DBLP DOI BibTeX RDF	Subject classification. 06E30, 52C07, 52C35, 68Q15, 68Q32
18	Neeraj Kayal, Nitin Saxena 0001	Polynomial Identity Testing for Depth 3 Circuits.	Comput. Complex.	2007	DBLP DOI BibTeX RDF	13P99, Subject classification. 68Q15
18	Pierre McKenzie, Klaus W. Wagner	The Complexity of Membership Problems for Circuits Over Sets of Natural Numbers.	Comput. Complex.	2007	DBLP DOI BibTeX RDF	Subject classification. 68Q25, 68Q15, 03D15
18	Satoru Kuroda	Generalized quantifier and a bounded arithmetic theory for LOGCFL.	Arch. Math. Log.	2007	DBLP DOI BibTeX RDF	Mathematics Subject Classification (2000) 03F30, 68Q15
18	Benny Applebaum, Yuval Ishai, Eyal Kushilevitz	Computationally Private Randomizing Polynomials and Their Applications.	Comput. Complex.	2006	DBLP DOI BibTeX RDF	Subject classification. 94A60, 68P25, 68Q15
18	Chris Pollett	Languages to diagonalize against advice classes.	Comput. Complex.	2006	DBLP DOI BibTeX RDF	Subject classification. 68Q15, 03D15
18	Paul Beame, Toniann Pitassi, Nathan Segerlind, Avi Wigderson	A Strong Direct Product Theorem for Corruption and the Multiparty Communication Complexity of Disjointness.	Comput. Complex.	2006	DBLP DOI BibTeX RDF	06D15, 68Q17, 68Q15, 06E30, Subject classification. 68Q10
18	Peter Bürgisser, Felipe Cucker, Paulin Jacobé de Naurois	The complexity of semilinear problems in succinct representation.	Comput. Complex.	2006	DBLP DOI BibTeX RDF	Subject classification, 68Q15
18	Matthias Krause 0001	On the computational power of Boolean decision lists.	Comput. Complex.	2006	DBLP DOI BibTeX RDF	94C05, Subject classification. 68Q15, 06E30, 94C10
18	Neeraj Kayal, Nitin Saxena 0001	Complexity of Ring Morphism Problems.	Comput. Complex.	2006	DBLP DOI BibTeX RDF	13P99, Subject classification. 68Q15
18	Ronen Shaltiel, Christopher Umans	Pseudorandomness for Approximate Counting and Sampling.	Comput. Complex.	2006	DBLP DOI BibTeX RDF	Subject classification, 68Q15
18	Russell Impagliazzo, Ronen Shaltiel, Avi Wigderson	Reducing The Seed Length In The Nisan-Wigderson Generator.	Comb.	2006	DBLP DOI BibTeX RDF	Mathematics Subject Classification (2000): 68Q15
18	Peter Bro Miltersen, N. V. Vinodchandran	Derandomizing Arthur-Merlin Games using Hitting Sets.	Comput. Complex.	2005	DBLP DOI BibTeX RDF	68Q17, Subject classification. 68Q15
18	Pascal Koiran	Valiant's model and the cost of computing integers.	Comput. Complex.	2005	DBLP DOI BibTeX RDF	68Q17, Subject classification. 68Q15, 03D15
18	Chris Marriott, John Watrous	Quantum Arthur-Merlin games.	Comput. Complex.	2005	DBLP DOI BibTeX RDF	68Q15, Subject classification. 68Q10
18	Lars Kristiansen	Neat function algebraic characterizations of logspace and linspace.	Comput. Complex.	2005	DBLP DOI BibTeX RDF	03D10, Subject classification. 68Q15, 68Q05, 03D20
18	Leonard J. Schulman, Vijay V. Vazirani	A Computationally Motivated Definition Of Parametric Estimation And Its Applications To The Gaussian Distribution.	Comb.	2005	DBLP DOI BibTeX RDF	Mathematics Subject Classification (2000): 68Q15, 68W20, 62F25, 68Q25, 68W25
18	Toshio Suzuki	Bounded truth table does not reduce the one-query tautologies to a random oracle.	Arch. Math. Log.	2005	DBLP DOI BibTeX RDF	Mathematics Subject Classification (2000) 68Q15, 03D15
18	Satoru Kuroda	Recursion Schemata for Slowly Growing Depth Circuit Classes.	Comput. Complex.	2004	DBLP DOI BibTeX RDF	Subject classification. 03D20, 94C99, 68Q15
18	Valentine Kabanets, Russell Impagliazzo	Derandomizing Polynomial Identity Tests Means Proving Circuit Lower Bounds.	Comput. Complex.	2004	DBLP DOI BibTeX RDF	68Q17, 68Q15, Subject classification. 68Q10
18	John Watrous	On the complexity of simulating space-bounded quantum computations.	Comput. Complex.	2003	DBLP DOI BibTeX RDF	Mathematics Subject Classification (2000). 03D15, 68Q15
18	Dan Gutfreund, Ronen Shaltiel, Amnon Ta-Shma	Uniform hardness versus randomness tradeoffs for Arthur-Merlin games.	Comput. Complex.	2003	DBLP DOI BibTeX RDF	Mathematics Subject Classification (2000). 68Q15
18	Ronen Shaltiel	Towards proving strong direct product theorems.	Comput. Complex.	2003	DBLP DOI BibTeX RDF	Mathematics Subject Classification (2000). 68Q17, 68Q15
18	Carsten Damm, Markus Holzer 0001, Pierre McKenzie	The complexity of tensor calculus.	Comput. Complex.	2002	DBLP DOI BibTeX RDF	Mathematics Subject Classification (2000). 15A69, 68Q70, 68Q17, 68Q15, 68Q05
18	Lance Fortnow, John D. Rogers	Separability and one-way functions.	Comput. Complex.	2002	DBLP DOI BibTeX RDF	Mathematics Subject Classification (2000). 68Q15
18	Oded Goldreich 0001, Salil P. Vadhan, Avi Wigderson	On interactive proofs with a laconic prover.	Comput. Complex.	2002	DBLP DOI BibTeX RDF	Mathematics Subject Classification (2000). 68Q05, 91A05, 68Q15, 68Q10
18	Erez Petrank, Gábor Tardos	On the Knowledge Complexity of NP.	Comb.	2002	DBLP DOI BibTeX RDF	AMS Subject Classification (2000) Classes: 68Q15, 68Q17
18	Anna Gál	A characterization of span program size and improved lower bounds for monotone span programs.	Comput. Complex.	2001	DBLP DOI BibTeX RDF	Span programs, Boolean formula size, secret sharing..¶ Subject classification. 68Q15, lower bounds, 94C10
18	Karl-Heinz Niggl	The m\mu-measure as a tool for classifying computational complexity.	Arch. Math. Log.	2000	DBLP DOI BibTeX RDF	Mathematics Subject Classification (2000): 03D15, 68Q15, 68Q42, 03D20
18	Ran Raz, Pierre McKenzie	Separation of the Monotone NC Hierarchy.	Comb.	1999	DBLP DOI BibTeX RDF	AMS Subject Classification (1991) Classes: 68Q15, 68R99, 68Q25
18	Martin Grohe	Equivalence in Finite-Variable Logics is Complete for Polynomial Time.	Comb.	1999	DBLP DOI BibTeX RDF	AMS Subject Classification (1991) Classes: 03C13, 05C60, 68Q15
18	Karl-Heinz Niggl	A restricted computation model on Scott domains and its partial primitive recursive functionals.	Arch. Math. Log.	1998	DBLP DOI BibTeX RDF	Mathematics Subject Classification (1991):03D15, 03D65, 03D99, 68Q99, 68Q15, 68Q10, 68Q55, 68Q05, 03D20