Cover Image

Optimal Hardness of Online Algorithms for Large Independent Sets

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Gamarnik, David, Kızıldağ, Eren C., Warnke, Lutz
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms Computational Complexity Discrete Mathematics Combinatorics Probability 68Q87, 60C05, 05C80, 68Q25, 68R10, 68W27
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Computing the probability of intersection
by: Barvinok, Alexander
Published: (2025)

Finding cliques and dense subgraphs using edge queries
by: Csóka, Endre, et al.
Published: (2023)

Algorithms for Minimum Membership Dominating Set Problem
by: Reddy, Sangam Balchandar, et al.
Published: (2024)

Fundamentals of Partial Rejection Sampling
by: Jerrum, Mark
Published: (2021)

Efficient Algorithms for Injectivity and Bounded Surjectivity of One-dimensional Nonlinear Cellular Automata
by: Wang, Chen, et al.
Published: (2023)

The random $k$-SAT Gibbs uniqueness threshold revisited
by: Chatterjee, Arnab, et al.
Published: (2025)

Random $2$-SAT: The set of atoms of the limiting empirical marginal distribution
by: Müller, Noela, et al.
Published: (2024)

Coordinatewise Balanced Covering for Linear Gain Graphs, with an Application to Coset-List Min-2-Lin over Powers of Two
by: Alpay, Faruk, et al.
Published: (2026)

WalkSAT is linear on random 2-SAT
by: Berenbrink, Petra, et al.
Published: (2024)

Refutation of Spectral Graph Theory Conjectures with Search Algorithms)
by: Roucairol, Milo, et al.
Published: (2024)

Computational thresholds in high-dimensional statistics: the case of graph alignment
by: Massoulié, Laurent
Published: (2025)

On the Average-Case Performance of Greedy for Maximum Coverage
by: Balkanski, Eric, et al.
Published: (2026)

Optimal non-adaptive algorithm for edge estimation
by: Bishnu, Arijit, et al.
Published: (2025)

Hamiltonicity Parameterized by Mim-Width is (Indeed) Para-NP-Hard
by: Bergougnoux, Benjamin, et al.
Published: (2025)

An Algorithm to Recover Shredded Random Matrices
by: Atamanchuk, Caelan, et al.
Published: (2023)

How to Compute a Moving Sum
by: Maslen, David K., et al.
Published: (2025)

Extending the Extension: Deterministic Algorithm for Non-monotone Submodular Maximization
by: Buchbinder, Niv, et al.
Published: (2024)

New Theoretical Insights and Algorithmic Solutions for Reconstructing Score Sequences from Tournament Score Sets
by: Liu, Bowen
Published: (2025)

Algorithms for Generating Small Random Samples
by: Cicirello, Vincent A.
Published: (2024)

Asymptotic size of the Karp-Sipser Core in Configuration Model
by: Chatterjee, Arnab, et al.
Published: (2025)

A new lower bound for deterministic pop-stack-sorting
by: Bauer, Morgan, et al.
Published: (2023)

Enumeration Kernels of Polynomial Size for Cuts of Bounded Degree
by: Komusiewicz, Christian, et al.
Published: (2023)

The Power of Filling in Balanced Allocations
by: Los, Dimitrios, et al.
Published: (2022)

Mean-Biased Processes for Balanced Allocations
by: Los, Dimitrios, et al.
Published: (2023)

The degree-restricted random process is far from uniform
by: Molloy, Michael, et al.
Published: (2022)

Resident fitness computation in linear time and other algorithmic aspects of interacting trajectories
by: Friedl, Katalin, et al.
Published: (2025)

Shortest Paths without a Map, but with an Entropic Regularizer
by: Bubeck, Sébastien, et al.
Published: (2022)

BFS versus DFS for random targets in ordered trees
by: Dimitrov, Stoyan, et al.
Published: (2024)

On (In)approximability of MaxMin Independent Set Reconfiguration
by: Hoang, Hung P., et al.
Published: (2026)

A Study of NP-Completeness and Undecidable Word Problems in Semigroups
by: Abdullah, Duaa, et al.
Published: (2025)

Algorithmic Universality, Low-Degree Polynomials, and Max-Cut in Sparse Random Graphs
by: Cheairi, Houssam El, et al.
Published: (2024)

The Algorithmic Phase Transition of Random Graph Alignment Problem
by: Du, Hang, et al.
Published: (2023)

Improved Computational Lower Bound of Estimation for Multi-Frequency Group Synchronization
by: Li, Zhangsong
Published: (2026)

Model-Checking for First-Order Logic with Disjoint Paths Predicates in Proper Minor-Closed Graph Classes
by: Golovach, Petr A., et al.
Published: (2022)

Near-Optimal Bootstrapping of Hitting Sets for Algebraic Models
by: Kumar, Mrinal, et al.
Published: (2018)

Symmetric Rule-Based Achlioptas Processes for Random $k$-SAT
by: Chatterjee, Arnab
Published: (2025)

Optimal Discretization is Fixed-parameter Tractable
by: Kratsch, Stefan, et al.
Published: (2020)

An Improved Drift Theorem for Balanced Allocations
by: Los, Dimitrios, et al.
Published: (2023)

Tangled Paths: A Random Graph Model from Mallows Permutations
by: Enright, Jessica, et al.
Published: (2021)

Pliability and Approximating Max-CSPs
by: Romero, Miguel, et al.
Published: (2019)