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 |