Which Problems Have Strongly Exponential Complexity?

2001/12/01 by Russell Impagliazzo, Ramamohan Paturi, Francis Zane · 45 citations
Computer Science · #Complexity and Algorithms in Graphs #Advanced Graph Theory Research #Machine Learning and Algorithms

paper · doi:10.1006/jcss.2001.1774

Cited by

• Revenue maximization in Stackelberg Pricing Games: beyond the combinatorial setting
• PCP Theorems, SETH and More: Towards Proving Sub-linear Time Inapproximability
• The Complexity of Adversarially Robust Proper Learning of Halfspaces with Agnostic Noise
• Towards Tight Approximation Bounds for Graph Diameter and Eccentricities
• On the Complexity Landscape of Connected f -Factor Problems
• Knapsack Problems: A Parameterized Point of View
• On the Fine-grained Complexity of One-Dimensional Dynamic Programming
• Polynomial Kernels for Weighted Problems
• Lossy Kernelization
• CSPs with Global Modular Constraints: Algorithms and Hardness via\n Polynomial Representations
• Why walking the dog takes time: Frechet distance has no strongly subquadratic algorithms unless SETH fails
• Inapproximability of Maximum Biclique Problems, Minimum k-Cut and\n Densest At-Least-k-Subgraph from the Small Set Expansion Hypothesis
• Hardness of Approximate Nearest Neighbor Search under L-infinity
• A Proof Checking View of Parameterized Complexity
• On Fine-Grained Exact Computation in Regular Graphs
• Detecting communities is hard, and counting them is even harder
• On the Computational Complexity of MapReduce
• On Structural Parameterizations of Hitting Set: Hitting Paths in Graphs\n Using 2-SAT
• Subexponential-time Algorithms for Maximum Independent Set in P_t-free and Broom-free Graphs
• Into the Square - On the Complexity of Quadratic-Time Solvable Problems
• Parameterized Complexity of Bandwidth on Trees
• On the Parameterized Complexity and Kernelization of the Workflow Satisfiability Problem
• Popular conjectures imply strong lower bounds for dynamic problems
• Dynamic Programming for Graphs on Surfaces
• Lower Bounds for QBFs of Bounded Treewidth
• A New Direction for Counting Perfect Matchings
• The Relative Exponential Time Complexity of Approximate Counting\n Satisfying Assignments
• A randomized polynomial kernelization for Vertex Cover with a smaller parameter
• Subexponential and FPT-time Inapproximability of Independent Set and Related Problems
• Multivariate Complexity Analysis of Geometric \sc Red Blue Set Cover
• Quadratic-Time Hardness of LCS and other Sequence Similarity Measures
• Kernels for (connected) Dominating Set on graphs with Excluded Topological subgraphs
• On the complexity of detecting hazards
• Circuit Depth Reductions
• Half-integrality, LP-branching and FPT Algorithms
• Simultaneous Feedback Vertex Set: A Parameterized Perspective
• Improved Lower Bounds for Graph Embedding Problems
• Exact Algorithms for 0-1 Integer Programs with Linear Equality Constraints
• Treewidth-Aware Complexity in ASP: Not all Positive Cycles are Equally\n Hard
• Exploiting Treewidth for Projected Model Counting and its Limits
• Enumerating Minimal Connected Dominating Sets
• Inapproximability of VC Dimension and Littlestone's Dimension
• Parameterized complexity dichotomy for (r,ℓ)-Vertex Deletion
• On the dynamic width of the 3-colorability problem
• On the (adjacency) metric dimension of corona and strong product graphs\n and their local variants: combinatorial and computational results