Cover Image

Inapproximability of the independent set polynomial in the complex plane

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Bezakova, Ivona, Galanis, Andreas, Goldberg, Leslie Ann, Stefankovic, Daniel
Format:	Preprint
Published:	2017
Subjects:	Computational Complexity Discrete Mathematics
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Critical window for approximate counting in dense Ising models
by: Galanis, Andreas, et al.
Published: (2026)

Counting Subgraphs in Somewhere Dense Graphs
by: Bressan, Marco, et al.
Published: (2022)

Optimal Inapproximability of Promise Equations over Finite Groups
by: Butti, Silvia, et al.
Published: (2024)

Approximately Counting Answers to Conjunctive Queries with Disequalities and Negations
by: Focke, Jacob, et al.
Published: (2021)

Tight Inapproximability of Target Set Reconfiguration
by: Ohsaka, Naoto
Published: (2024)

Probabilistically Checkable Reconfiguration Proofs and Inapproximability of Reconfiguration Problems
by: Hirahara, Shuichi, et al.
Published: (2023)

Asymptotically Optimal Inapproximability of E$k$-SAT Reconfiguration
by: Hirahara, Shuichi, et al.
Published: (2025)

Asymptotically Optimal Inapproximability of Maxmin $k$-Cut Reconfiguration
by: Hirahara, Shuichi, et al.
Published: (2024)

Logarithmic Mixing of Random Walks on Dynamical Random Cluster Models
by: Galanis, Andreas, et al.
Published: (2026)

Sampling from the random cluster model on random regular graphs at all temperatures via Glauber dynamics
by: Galanis, Andreas, et al.
Published: (2023)

Relations between monotone complexity measures based on decision tree complexity
by: Byramji, Farzan, et al.
Published: (2024)

Computational complexity of the Weisfeiler-Leman dimension
by: Lichter, Moritz, et al.
Published: (2024)

On the complexity of freezing automata networks of bounded pathwidth
by: Goles, Eric, et al.
Published: (2025)

On the satisfiability of random $3$-SAT formulas with $k$-wise independent clauses
by: Caragiannis, Ioannis, et al.
Published: (2024)

On full-separating sets and related codes in graphs
by: Chakraborty, Dipayan, et al.
Published: (2024)

On the complexity of the Maker-Breaker happy vertex game
by: Hilaire, Mathieu, et al.
Published: (2026)

On the parameterized complexity of the Maker-Breaker domination game
by: Bagan, Guillaume, et al.
Published: (2026)

More efficient sifting for grid norms, and applications to multiparty communication complexity
by: Kelley, Zander, et al.
Published: (2025)

Rational degree is polynomially related to degree
by: Kothari, Robin, et al.
Published: (2026)

Algorithms and complexity for monitoring edge-geodetic sets in graphs
by: Foucaud, Florent, et al.
Published: (2024)

On Computational Aspects of Ordered Matching Problems
by: Čertík, Michal, et al.
Published: (2025)

Complexity Aspects of Homomorphisms of Ordered Graphs
by: Čertík, Michal, et al.
Published: (2025)

On Computational Aspects of Cores of Ordered Graphs
by: Čertík, Michal, et al.
Published: (2025)

On Closure Properties of Read-Once Oblivious Algebraic Branching Programs
by: Armand, Jules, et al.
Published: (2025)

On the enumeration of Tarski fixed points
by: Müller, Julian
Published: (2023)

Edge-Disjoint Paths in Eulerian Digraphs
by: Cavallaro, Dario, et al.
Published: (2024)

Monotone Bounded-Depth Complexity of Homomorphism Polynomials
by: Bhargav, C. S., et al.
Published: (2025)

Gap Preserving Reductions Between Reconfiguration Problems
by: Ohsaka, Naoto
Published: (2022)

Gap Amplification for Reconfiguration Problems
by: Ohsaka, Naoto
Published: (2023)

Is Graph Local Complementation Inherently Sequential?
by: Concha-Vega, Pablo
Published: (2025)

An Algorithm for Monitoring Edge-geodetic Sets in Chordal Graphs
by: Marcille, Clara, et al.
Published: (2026)

Enumerating Minimal Defensive Alliances
by: Feng, Zhidan, et al.
Published: (2023)

Three Hardness Results for Graph Similarity Problems
by: Sun, He, et al.
Published: (2023)

How to Reconfigure Your Alliances
by: Fernau, Henning, et al.
Published: (2025)

List Decoding Quotient Reed-Muller Codes
by: Gotlib, Omri, et al.
Published: (2025)

Property Testing in Bounded Degree Hypergraphs
by: Aaronson, Hugo, et al.
Published: (2025)

Infinitely growing configurations in Emil Post's tag system problem
by: Kurilenko, Nikita V.
Published: (2021)

The Parameterized Complexity of Terminal Monitoring Set
by: Aravind, N. R., et al.
Published: (2024)

Maximal Line Digraphs
by: Japhet, Quentin, et al.
Published: (2024)

Complexity of the Freezing Majority Rule with L-shaped Neighborhoods
by: Concha-Vega, Pablo, et al.
Published: (2025)