The computational complexity of factored graphs

DOI10.4230/LIPICS.ITCS.2025.58MaRDI QIDQ7296702zbMATH OpenFDO

Authors Shreya Gupta, Boyang Huang, Russell Impagliazzo, Stanley Woo, Christopher Ye

Publication date 14 July 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.ITCS.2025.58

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• A measure for the lexicographically first maximal independent set problem and its limits
• A taxonomy of problems with fast parallel algorithms
• Advice classes of parametrized tractability
• Algorithms – ESA 2005
• Approximation schemes for PSPACE-complete problems for succinct specifications (preliminary version)
• Classes of Pebble Games and Complete Problems
• Computing correlated equilibria in multi-player games
• Describing parameterized complexity classes
• Fixed-Parameter Tractability and Completeness I: Basic Results
• Fixed-parameter tractability and completeness II: On completeness for W[1]
• Fixed-parameter tractability, definability, and model-checking
• scientific article; zbMATH DE number 437576 (Why is no real title available?)
• scientific article; zbMATH DE number 3910446 (Why is no real title available?)
• scientific article; zbMATH DE number 1335885 (Why is no real title available?)
• scientific article; zbMATH DE number 1333597 (Why is no real title available?)
• scientific article; zbMATH DE number 1107742 (Why is no real title available?)
• scientific article; zbMATH DE number 1114020 (Why is no real title available?)
• scientific article; zbMATH DE number 7204473 (Why is no real title available?)
• Linear-Time Succinct Encodings of Planar Graphs via Canonical Orderings
• Local expanders
• Lower bounds for existential pebble games and k-consistency tests
• New techniques for proving fine-grained average-case hardness
• On the complexity of succinct zero-sum games
• On the expected performance of a parallel algorithm for finding maximal independent subsets of a random graph
• On the possibility of faster \textsc{SAT} algorithms
• On the Space Complexity of Parameterized Problems
• Periodic constraint satisfaction problems: polynomial-time algorithms
• Periodic constraint satisfaction problems: Tractable subclasses
• Problems complete for deterministic logarithmic space
• Some combinatorial game problems require Ω( n ^k ) time
• Space-bounded reducibility among combinatorial problems
• Strong computational lower bounds via parameterized complexity
• Succinct Representation of Labeled Graphs
• Succinct Representations of Arbitrary Graphs
• Succinct representations of graphs
• Succinct representations of separable graphs
• The complexity of average-case dynamic subgraph counting
• The complexity of combinatorial problems with succinct input representation
• The complexity of the nucleolus in compact games
• The complexity of Unique \(k\)-SAT: An isolation lemma for \(k\)-CNFs
• The fine-grained complexity of multi-dimensional ordering properties
• The Game World Is Flat: The Complexity of Nash Equilibria in Succinct Games
• The lexicographically first maximal subgraph problems:P-completeness andNC algorithms
• The quickest transshipment problem
• Towards a Study of Low-Complexity Graphs

Cited in

(1)

• (Multivariate) k-SUM as barrier to succinct computation

This page was built for publication: The computational complexity of factored graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7296702)