Copertina

Computational hardness of detecting graph lifts and certifying lift-monotone properties of random regular graphs

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Kunisky, Dmitriy, Yu, Xifan
Natura:	Preprint
Pubblicazione:	2024
Soggetti:	Computational Complexity Data Structures and Algorithms Combinatorics Probability
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

Statistical inference of a ranked community in a directed graph
di: Kunisky, Dmitriy, et al.
Pubblicazione: (2024)

Inference of rankings planted in random tournaments
di: Kunisky, Dmitriy, et al.
Pubblicazione: (2024)

A degree 4 sum-of-squares lower bound for the clique number of the Paley graph
di: Kunisky, Dmitriy, et al.
Pubblicazione: (2022)

The stochastic block model has the overlap graph property for modularity
di: Bhamidi, Shankar, et al.
Pubblicazione: (2026)

Some easy optimization problems have the overlap-gap property
di: Li, Shuangping, et al.
Pubblicazione: (2024)

Hardness of sampling for the anti-ferromagnetic Ising model on random graphs
di: Huang, Neng, et al.
Pubblicazione: (2024)

Average-Case Matrix Discrepancy: Asymptotics and Online Algorithms
di: Kunisky, Dmitriy, et al.
Pubblicazione: (2023)

Low coordinate degree algorithms II: Categorical signals and generalized stochastic block models
di: Kunisky, Dmitriy
Pubblicazione: (2024)

Tensor cumulants for statistical inference on invariant distributions
di: Kunisky, Dmitriy, et al.
Pubblicazione: (2024)

Polynomial-time sampling despite disorder chaos
di: Ma, Eric, et al.
Pubblicazione: (2025)

Smoothed analysis for graph isomorphism
di: Anastos, Michael, et al.
Pubblicazione: (2024)

On the complexity of global Roman domination problem in graphs
di: Reddy, Sangam Balchandar, et al.
Pubblicazione: (2026)

The Low-Degree Hardness of Finding Large Independent Sets in Sparse Random Hypergraphs
di: Dhawan, Abhishek, et al.
Pubblicazione: (2024)

Sharp Online Hardness for Large Balanced Independent Sets
di: Dhawan, Abhishek, et al.
Pubblicazione: (2025)

Optimal Hardness of Online Algorithms for Large Common Induced Subgraphs
di: Gamarnik, David, et al.
Pubblicazione: (2026)

Algorithmic Phase Transition for Large Independent Sets in Dense Hypergraphs
di: Dhawan, Abhishek, et al.
Pubblicazione: (2026)

Isometric path complexity of graphs
di: Chakraborty, Dibyayan, et al.
Pubblicazione: (2022)

Detection of local geometry in random graphs: information-theoretic and computational limits
di: Bok, Jinho, et al.
Pubblicazione: (2026)

On graphs coverable by k shortest paths
di: Dumas, Maël, et al.
Pubblicazione: (2022)

Computational Complexity of Swish
di: Horiyama, Takashi, et al.
Pubblicazione: (2026)

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

Burning rooted graph products
di: Peca-Medlin, John
Pubblicazione: (2026)

Cycle-factors of regular graphs via entropy
di: Christoph, Micha, et al.
Pubblicazione: (2025)

Computing the $D$-base and $D$-relation in finite closure systems
di: Adaricheva, Kira, et al.
Pubblicazione: (2024)

Complexity of the (Connected) Cluster Vertex Deletion problem on $H$-free graphs
di: Le, Hoang-Oanh, et al.
Pubblicazione: (2024)

Complexity of Paired Domination Problems on Circle and $k$-Polygon Graphs
di: Mu, Ta-Yu, et al.
Pubblicazione: (2024)

Low coordinate degree algorithms I: Universality of computational thresholds for hypothesis testing
di: Kunisky, Dmitriy
Pubblicazione: (2024)

Universal entrywise eigenvector fluctuations in delocalized spiked matrix models and asymptotics of rounded spectral algorithms
di: Chen, Shujing, et al.
Pubblicazione: (2025)

Quality control in sublinear time: a case study via random graphs
di: Marcussen, Cassandra, et al.
Pubblicazione: (2025)

Computational and statistical lower bounds for low-rank estimation under general inhomogeneous noise
di: De, Debsurya, et al.
Pubblicazione: (2025)

Stable Algorithms Lower Bounds for Estimation
di: Yu, Xifan, et al.
Pubblicazione: (2026)

Uniform Sampling of Proper Graph Colorings via Soft Coloring and Partial Rejection Sampling
di: Moka, Sarat, et al.
Pubblicazione: (2026)

Random tensor isomorphism under orthogonal and unitary actions
di: Chizewer, Jeremy, et al.
Pubblicazione: (2026)

On the average-case complexity landscape for Tensor-Isomorphism-complete problems over finite fields
di: Li, Tiange, et al.
Pubblicazione: (2026)

The complexity of testing all properties of planar graphs, and the role of isomorphism
di: Basu, Sabyasachi, et al.
Pubblicazione: (2021)

Parameterized Shortest Path Reconfiguration
di: Bousquet, Nicolas, et al.
Pubblicazione: (2024)

Forest Covers and Bounded Forest Covers
di: Gaur, Daya Ram, et al.
Pubblicazione: (2024)

Constant congestion linkages in polynomially strong digraphs in polynomial time
di: Lopes, Raul, et al.
Pubblicazione: (2024)

On $[1,2]$-Domination in Interval and Circle Graphs
di: Meybodi, Mohsen Alambardar, et al.
Pubblicazione: (2024)

Fourier Analysis of Iterative Algorithms
di: Jones, Chris, et al.
Pubblicazione: (2024)