scientific article; zbMATH DE number 5485586

zbMath1231.68154MaRDI QIDQ5302097

Benjamin Rossman

Publication date: 5 January 2009

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (25)

Tensor clustering with planted structures: statistical optimality and computational limits ⋮ Parameterized Parallel Computing and First-Order Logic ⋮ Disordered systems insights on computational hardness ⋮ Formulas versus Circuits for Small Distance Connectivity ⋮ Some lower bounds in parameterized \(\mathrm{AC}^{0}\) ⋮ Combinatorics, probability and computing. Abstracts from the workshop held April 24--30, 2022 ⋮ Unnamed Item ⋮ Hardness of Random Optimization Problems for Boolean Circuits, Low-Degree Polynomials, and Langevin Dynamics ⋮ Cliques enumeration and tree-like resolution proofs ⋮ The Average-Case Complexity of Counting Cliques in Erdös--Rényi Hypergraphs ⋮ Unnamed Item ⋮ On the $AC^0$ Complexity of Subgraph Isomorphism ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A Fixed-Depth Size-Hierarchy Theorem for $\mathrm{AC}^0[\oplus$ via the Coin Problem] ⋮ Beating treewidth for average-case subgraph isomorphism ⋮ Parameterized Complexity of DPLL Search Procedures ⋮ The descriptive complexity of subgraph isomorphism without numerics ⋮ Ehrenfeucht-Fraïssé Games on Random Structures ⋮ Expressiveness of Hybrid Temporal Logic on Data Words ⋮ A Simple Gap-Producing Reduction for the Parameterized Set Cover Problem ⋮ Unnamed Item ⋮ Graph Pattern Detection: Hardness for all Induced Patterns and Faster Noninduced Cycles ⋮ Unnamed Item ⋮ Large clique is hard on average for resolution

This page was built for publication: