Buchumschlag

Sensitivity and Hamming graphs

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Asensio, Sara, Filmus, Yuval, García-Marco, Ignacio, Knauer, Kolja
Format:	Preprint
Veröffentlicht:	2025
Schlagworte:	Combinatorics Computational Complexity
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Sensitivity of $m$-ary functions and low degree partitions of Hamming graphs
von: Asensio, Sara, et al.
Veröffentlicht: (2024)

Sensitivity and Hamming Graphs
von: Sara Asensio, et al.
Veröffentlicht: (2026)

Sparse juntas on the biased hypercube
von: Dinur, Irit, et al.
Veröffentlicht: (2017)

Boolean functions on high-dimensional expanders
von: Dikstein, Yotam, et al.
Veröffentlicht: (2018)

Coloring minimal Cayley graphs
von: García-Marco, Ignacio, et al.
Veröffentlicht: (2024)

The Complexity Classes of Hamming Distance Recoverable Robust Problems
von: Grüne, Christoph
Veröffentlicht: (2022)

Between proper and square coloring of planar graphs, hardness and extremal graphs
von: Delépine, Thomas
Veröffentlicht: (2026)

Classification aggregation: a quantitative impossibility theorem
von: Filmus, Yuval
Veröffentlicht: (2026)

$C_{2k+1}$-coloring of bounded-diameter graphs
von: Piecyk, Marta
Veröffentlicht: (2024)

A parameterized algorithm for $K_r$-factors in graphs of high minimum degree
von: Gan, Luyining, et al.
Veröffentlicht: (2023)

Finding large $k$-colorable induced subgraphs in (bull, chair)-free and (bull,E)-free graphs
von: Hodur, Nadzieja, et al.
Veröffentlicht: (2025)

The Borsuk number of a graph
von: Cáceres, José, et al.
Veröffentlicht: (2026)

What is and is not inside a Cayley graph?
von: Knauer, Kolja, et al.
Veröffentlicht: (2025)

Shrinkage under Random Projections, and Cubic Formula Lower Bounds for $\mathsf{AC}^0$
von: Filmus, Yuval, et al.
Veröffentlicht: (2020)

On endomorphism universality of sparse graph classes
von: Knauer, Kolja, et al.
Veröffentlicht: (2022)

Hamiltonian connectivity of some base-cobase graphs
von: Martínez-Sandoval, Leonardo, et al.
Veröffentlicht: (2025)

Combinatorial refinement on circulant graphs
von: Kluge, Laurence
Veröffentlicht: (2022)

Non-crossing $H$-graphs: a generalization of proper interval graphs admitting FPT algorithms
von: Bonomo-Braberman, Flavia, et al.
Veröffentlicht: (2025)

On full-separating sets and related codes in graphs
von: Chakraborty, Dipayan, et al.
Veröffentlicht: (2024)

Temporal Reachability Dominating Sets: contagion in temporal graphs
von: Kutner, David C., et al.
Veröffentlicht: (2023)

A structural description of Zykov and Blanche Descartes graphs
von: Marin, Malory, et al.
Veröffentlicht: (2024)

On the hardness of recognizing graphs of small mim-width and its variants
von: la Tour, Max Dupré, et al.
Veröffentlicht: (2025)

Complexity results for a cops and robber game on directed graphs
von: Ben-Ameur, Walid, et al.
Veröffentlicht: (2024)

Random regular graph states are complex at almost any depth
von: Ghosh, Soumik, et al.
Veröffentlicht: (2024)

Aggregation of evaluations without unanimity
von: Filmus, Yuval
Veröffentlicht: (2025)

On rigid regular graphs and a problem of Babai and Pultr
von: Knauer, Kolja, et al.
Veröffentlicht: (2025)

Complexity and algorithms for matching cut problems in graphs without long induced paths and cycles
von: Le, Hoang-Oanh, et al.
Veröffentlicht: (2023)

Smoothed analysis for graph isomorphism
von: Anastos, Michael, et al.
Veröffentlicht: (2024)

Constant Rate Isometric Embeddings of Hamming Metric into Edit Metric
von: Bhattacharya, Sudatta, et al.
Veröffentlicht: (2025)

Noise Sensitivity and Learning Lower Bounds for Hierarchical Functions
von: Li, Rupert, et al.
Veröffentlicht: (2025)

Cell structure of mediangle graphs
von: Chepoi, Victor, et al.
Veröffentlicht: (2025)

On the complexity of global Roman domination problem in graphs
von: Reddy, Sangam Balchandar, et al.
Veröffentlicht: (2026)

Complexity Framework For Forbidden Subgraphs V: Beyond Simple Graphs
von: Eagling-Vose, Tala, et al.
Veröffentlicht: (2025)

Refuting Perfect Matchings in Spectral Expanders is Hard
von: Biswas, Ari, et al.
Veröffentlicht: (2025)

Monotone Circuit Complexity of Matching
von: Cavalar, Bruno, et al.
Veröffentlicht: (2025)

Hunting a rabbit: complexity, approximability and some characterizations
von: Ben-Ameur, Walid, et al.
Veröffentlicht: (2025)

Improved Small Set Expansion in High Dimensional Expanders
von: Kaufman, Tali, et al.
Veröffentlicht: (2025)

A near-optimal Quadratic Goldreich-Levin algorithm
von: Briët, Jop, et al.
Veröffentlicht: (2025)

Assembly Addition Chains
von: Cronin, Leroy, et al.
Veröffentlicht: (2025)

Tensor rank and dimension expanders
von: Dvir, Zeev
Veröffentlicht: (2025)