Search results for "68Q17"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
50	Petr Hlinený	On Matroid Representability and Minor Problems.	MFCS	2006	DBLP DOI BibTeX RDF	Matroid representability, spike, swirl. 2000 Math subject classification: 05B35, finite field, 68Q17, 68R05, minor
17	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
17	Troy Lee, Adi Shraibman	Disjointness is Hard in the Multiparty Number-on-the-Forehead Model.	Comput. Complex.	2009	DBLP DOI BibTeX RDF	68Q17, Subject classification
17	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
17	Amir Hashemi	Nullstellensätze for Zero-Dimensional Gröbner Bases.	Comput. Complex.	2009	DBLP DOI BibTeX RDF	Primary 13P10, Secondary 68Q17, Subject classification
17	Alexander A. Sherstov	Approximate Inclusion-Exclusion for Arbitrary Symmetric Functions.	Comput. Complex.	2009	DBLP DOI BibTeX RDF	Subject classification. 03D15, 68Q17
17	Peter Bürgisser	On Defining Integers And Proving Arithmetic Circuit Lower Bounds.	Comput. Complex.	2009	DBLP DOI BibTeX RDF	Primary 68Q17, Secondary 11D45, Subject classification
17	Per Austrin, Elchanan Mossel	Approximation Resistant Predicates from Pairwise Independence.	Comput. Complex.	2009	DBLP DOI BibTeX RDF	MSC Primary 68Q17, Secondary 41A52, Subject classification
17	Ran Raz, Amir Yehudayoff	Lower Bounds and Separations for Constant Depth Multilinear Circuits.	Comput. Complex.	2009	DBLP DOI BibTeX RDF	68Q17, Subject classification
17	Jean François Maurras	A family of easy polyhedra.	4OR	2009	DBLP DOI BibTeX RDF	MSC classification (2000) 52B12, 68Q17, 68Q25
17	Venkatesan Guruswami, Valentine Kabanets	Hardness Amplification via Space-Efficient Direct Products.	Comput. Complex.	2008	DBLP DOI BibTeX RDF	94B35, 68Q25, 94B05, 68P30, Subject classification. 68Q17
17	Chris Peikert	Limits on the Hardness of Lattice Problems in lp Norms.	Comput. Complex.	2008	DBLP DOI BibTeX RDF	11H06, 94B75, 68Q25, Subject classification. 68Q17
17	Aduri Pavan, N. V. Vinodchandran	2-Local Random Reductions to 3-Valued Functions.	Comput. Complex.	2008	DBLP DOI BibTeX RDF	68Q17, Subject classification. 68Q15
17	Saugata Basu, Nayantara Bhatnagar, Parikshit Gopalan, Richard J. Lipton	Polynomials that Sign Represent Parity and Descartes' Rule of Signs.	Comput. Complex.	2008	DBLP DOI BibTeX RDF	68Q17, Subject classification
17	Hubie Chen	Inverse NP Problems.	Comput. Complex.	2008	DBLP DOI BibTeX RDF	68Q17, Subject classification
17	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
17	John M. Hitchcock, Aduri Pavan	Hardness Hypotheses, Derandomization, and Circuit Complexity.	Comput. Complex.	2008	DBLP DOI BibTeX RDF	68Q30, 68Q17, Subject classification. 68Q15
17	Alexander A. Sherstov	Halfspace Matrices.	Comput. Complex.	2008	DBLP DOI BibTeX RDF	Subject classification. 03D15, 68Q17, 68Q15
17	R. Ryan Williams	Time-Space Tradeoffs for Counting NP Solutions Modulo Integers.	Comput. Complex.	2008	DBLP DOI BibTeX RDF	68Q17, Subject classification. 68Q15
17	Ran Raz, Iddo Tzameret	The Strength of Multilinear Proofs.	Comput. Complex.	2008	DBLP DOI BibTeX RDF	Subject classification. 03F20, 68Q17, 13P10
17	Jin-yi Cai, Pinyan Lu	Basis Collapse in Holographic Algorithms.	Comput. Complex.	2008	DBLP DOI BibTeX RDF	68Q25, Subject classification. 68Q17
17	Miroslaw Truszczynski, Stefan Woltran	Hyperequivalence of logic programs with respect to supported models.	Ann. Math. Artif. Intell.	2008	DBLP DOI BibTeX RDF	Mathematics Subject Classifications (2000) 68N17, 68Q17, 68T30
17	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
17	Cédric Bentz	Exact and approximate resolution of integral multiflow and multicut problems: algorithms and complexity.	4OR	2008	DBLP DOI BibTeX RDF	MSC Classification 05C85, 90C27, 68Q17
17	Uwe Naumann	Optimal Jacobian accumulation is NP-complete.	Math. Program.	2008	DBLP DOI BibTeX RDF	Mathematics Subject Classification (2000) 26B10, 68Q17
17	Willem L. Fouché	Subrecursive Complexity of Identifying the Ramsey Structure of Posets.	CiE	2008	DBLP DOI BibTeX RDF	Mathematics Subject Classification (2000) 03D20, 68Q17, 06A07, 05D10
17	Daniele Micciancio	Generalized Compact Knapsacks, Cyclic Lattices, and Efficient One-Way Functions.	Comput. Complex.	2007	DBLP DOI BibTeX RDF	11H06, Subject classification. 68Q17, 94B15
17	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
17	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
17	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
17	Ingo Wegener, Philipp Woelfel	New Results on the Complexity of the Middle Bit of Multiplication.	Comput. Complex.	2007	DBLP DOI BibTeX RDF	68Q17, Subject classification
17	Paul Beame, Russell Impagliazzo, Ashish Sabharwal	The Resolution Complexity of Independent Sets and Vertex Covers in Random Graphs.	Comput. Complex.	2007	DBLP DOI BibTeX RDF	Subject classification. 03F20, 68Q17
17	K. Subramani 0001	On a decision procedure for quantified linear programs.	Ann. Math. Artif. Intell.	2007	DBLP DOI BibTeX RDF	Mathematics Subject Classifications (2000) 68W05, 68Q17, 90C05, 68W40
17	Thomas Eiter, Wolfgang Faber 0001, Michael Fink 0001, Stefan Woltran	Complexity results for answer set programming with bounded predicate arities and implications.	Ann. Math. Artif. Intell.	2007	DBLP DOI BibTeX RDF	Mathematics Subject Classifications (2000) 68N17, 68Q17
17	Bruno Escoffier	Polynomial approximation: a structural and operational study.	4OR	2007	DBLP DOI BibTeX RDF	MSC classification 68Q17, 68Q25, 05C15, 68W25
17	Irène Charon, Olivier Hudry	A survey on the linear ordering problem for weighted or unweighted tournaments.	4OR	2007	DBLP DOI BibTeX RDF	Mathematical Subject Classification (2000) 05C20, 05C90, 06A05, 91F10, 90C27, 68Q17, 68Q25, 90C57, 68R10, 90C10, 90C59, 90C35, 05C38, 06A07
17	Pascal Michel	Computational complexity of logical theories of one successor and another unary function.	Arch. Math. Log.	2007	DBLP DOI BibTeX RDF	Mathematics Subject Classification (2000) 03D15, 03B25, 68Q17
17	Shuchi Chawla 0001, Robert Krauthgamer, Ravi Kumar 0001, Yuval Rabani, D. Sivakumar 0001	On the Hardness of Approximating Multicut and Sparsest-Cut.	Comput. Complex.	2006	DBLP DOI BibTeX RDF	68Q17, Subject classification
17	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
17	Ryan Williams 0001	Inductive Time-Space Lower Bounds for Sat and Related Problems.	Comput. Complex.	2006	DBLP DOI BibTeX RDF	68Q17, Subject classification
17	Richard Beigel, Lance Fortnow, William I. Gasarch	A tight lower bound for restricted pir protocols.	Comput. Complex.	2006	DBLP DOI BibTeX RDF	68Q17, Subject classification
17	Sophie Laplante, Troy Lee, Mario Szegedy	The Quantum Adversary Method and Classical Formula Size Lower Bounds.	Comput. Complex.	2006	DBLP DOI BibTeX RDF	68Q30, Subject classification. 68Q17
17	Elad Hazan, Shmuel Safra, Oded Schwartz	On the complexity of approximating k-set packing.	Comput. Complex.	2006	DBLP DOI BibTeX RDF	68Q17, Subject classification
17	Shmuel Safra, Oded Schwartz	On the complexity of approximating tsp with neighborhoods and related problems.	Comput. Complex.	2006	DBLP DOI BibTeX RDF	68Q25, Subject classification. 68Q17
17	Dániel Marx	The complexity of chromatic strength and chromatic edge strength.	Comput. Complex.	2006	DBLP DOI BibTeX RDF	68Q17, Subject classification
17	Michael R. Fellows, Jens Gramm, Rolf Niedermeier	On The Parameterized Intractability Of Motif Search Problems.	Comb.	2006	DBLP DOI BibTeX RDF	Mathematics Subject Classification (2000): 03D15, 68Q17, 68Q25
17	Mark Jerrum	Two Remarks Concerning Balanced Matroids.	Comb.	2006	DBLP DOI BibTeX RDF	Mathematics Subject Classification (2000): 05B35, 05A99, 51E10, 68Q17
17	Christos H. Papadimitriou, Santosh S. Vempala	On The Approximability Of The Traveling Salesman Problem.	Comb.	2006	DBLP DOI BibTeX RDF	Mathematics Subject Classification (2000): 68Q17, 05D40
17	Corinne Feremans, Alexander Grigoriev, René Sitters	The geometric generalized minimum spanning tree problem with grid clustering.	4OR	2006	DBLP DOI BibTeX RDF	MSC classification 68Q17, 68W25
17	Dirk Müller 0003	On the complexity of the planar directed edge-disjoint paths problem.	Math. Program.	2006	DBLP DOI BibTeX RDF	Mathematics Subject Classification (2000) 05C38, 68Q17, 68R10, 90C35
17	Peter Bro Miltersen, N. V. Vinodchandran	Derandomizing Arthur-Merlin Games using Hitting Sets.	Comput. Complex.	2005	DBLP DOI BibTeX RDF	68Q17, Subject classification. 68Q15
17	Venkatesan Guruswami, Daniele Micciancio, Oded Regev 0001	The complexity of the covering radius problem.	Comput. Complex.	2005	DBLP DOI BibTeX RDF	11H06, 11H31, 68Q25, 94B05, Subject classification. 68Q17
17	Pascal Koiran	Valiant's model and the cost of computing integers.	Comput. Complex.	2005	DBLP DOI BibTeX RDF	68Q17, Subject classification. 68Q15, 03D15
17	Dániel Marx	Parameterized complexity of constraint satisfaction problems.	Comput. Complex.	2005	DBLP DOI BibTeX RDF	Subject classification. 68Q25, 68Q17
17	Joe Kilian, Charles Rackoff, Erez Petrank	Lower Bounds For Concurrent Zero Knowledge*.	Comb.	2005	DBLP DOI BibTeX RDF	Mathematics Subject Classification (2000): 68Q17, 68Q10, 68Q85
17	Irit Dinur, Oded Regev 0001, Clifford D. Smyth	The Hardness of 3-Uniform Hypergraph Coloring.	Comb.	2005	DBLP DOI BibTeX RDF	Mathematics Subject Classification (2000): 68Q17
17	Maria Luisa Bonet, Carlos Domingo, Ricard Gavaldà, Alexis Maciel, Toniann Pitassi	Non-Automatizability of Bounded-Depth Frege Proofs.	Comput. Complex.	2004	DBLP DOI BibTeX RDF	Subject classification. 03F20, 68Q17, 68T15
17	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
17	Michelangelo Grigni, Leonard J. Schulman, Monica Vazirani, Umesh V. Vazirani	Quantum Mechanical Algorithms for the Nonabelian Hidden Subgroup Problem.	Comb.	2004	DBLP DOI BibTeX RDF	Mathematics Subject Classification (2000): 81P68, 68Q17
17	Eli Ben-Sasson, Russell Impagliazzo, Avi Wigderson	Near Optimal Separation Of Tree-Like And General Resolution.	Comb.	2004	DBLP DOI BibTeX RDF	Mathematics Subject Classification (2000): 03F20, 68Q17
17	Toniann Pitassi, Ran Raz	Regular Resolution Lower Bounds For The Weak Pigeonhole Principle.	Comb.	2004	DBLP DOI BibTeX RDF	Mathematics Subject Classification (2000): 03F20, 68Q17
17	Qi Cheng 0001	Straight-line programs and torsion points on elliptic curves.	Comput. Complex.	2003	DBLP DOI BibTeX RDF	Mathematics Subject Classification (2000). 14H52, 68Q17
17	Ronen Shaltiel	Towards proving strong direct product theorems.	Comput. Complex.	2003	DBLP DOI BibTeX RDF	Mathematics Subject Classification (2000). 68Q17, 68Q15
17	Sanjeev Arora, Madhu Sudan 0001	Improved Low-Degree Testing and its Applications.	Comb.	2003	DBLP DOI BibTeX RDF	AMS Subject Classification (2000): 68Q10, 68Q17
17	Irit Dinur, Guy Kindler, Ran Raz, Shmuel Safra	Approximating CVP to Within Almost-Polynomial Factors is NP-Hard.	Comb.	2003	DBLP DOI BibTeX RDF	AMS Subject Classification (2000): 68Q17
17	Friedrich Eisenbrand, Andreas S. Schulz	Bounds on the Chvátal Rank of Polytopes in the 0/1-Cube.	Comb.	2003	DBLP DOI BibTeX RDF	AMS Subject Classification (2000): 52B05, 90C27, 68Q17, 90C57, 90C10, 90C60
17	Vangelis Th. Paschos	Polynomial Approximation and Graph-Coloring.	Computing	2003	DBLP DOI BibTeX RDF	AMS Subject Classification: 05C15, 68Q17, 68Q25, 90C59, 68W25
17	Josh Buresh-Oppenheim, Matthew Clegg, Russell Impagliazzo, Toniann Pitassi	Homogenization and the polynomial calculus.	Comput. Complex.	2002	DBLP DOI BibTeX RDF	Mathematics Subject Classification (2000). 68Q17
17	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
17	Bruno Codenotti, Igor E. Shparlinski, Arne Winterhof	On the hardness of approximating the permanent of structured matrices.	Comput. Complex.	2002	DBLP DOI BibTeX RDF	Mathematics Subject Classification (2000). 11T23, 15A15, 68Q17
17	Alexander A. Razborov, Avi Wigderson, Andrew Chi-Chih Yao	Read-Once Branching Programs, Rectangular Proofs of the Pigeonhole Principle and the Transversal Calculus.	Comb.	2002	DBLP DOI BibTeX RDF	AMS Subject Classification (2000): 03F20, 68Q17
17	Erez Petrank, Gábor Tardos	On the Knowledge Complexity of NP.	Comb.	2002	DBLP DOI BibTeX RDF	AMS Subject Classification (2000) Classes: 68Q15, 68Q17
17	Bojan Mohar	Existence of Polyhedral Embeddings of Graphs.	Comb.	2001	DBLP DOI BibTeX RDF	AMS Subject Classification (2000) Classes: 05C10, 68Q17
17	Sanjeev Khanna, Nathan Linial, Shmuel Safra	On the Hardness of Approximating the Chromatic Number.	Comb.	2000	DBLP DOI BibTeX RDF	AMS Subject Classification (1991) Classes: 68Q17, 68Q25, 68R10