Copertina

A Distance Amplification Lemma for Monotonicity

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autore principale:	Minzer, Dor
Natura:	Preprint
Pubblicazione:	2025
Soggetti:	Computational Complexity Discrete Mathematics
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

Parallel Repetition for $3$-Player XOR Games
di: Bhangale, Amey, et al.
Pubblicazione: (2024)

Multi-Pass Streaming Lower Bounds for Approximating Max-Cut
di: Fei, Yumou, et al.
Pubblicazione: (2025)

Gap Amplification for Reconfiguration Problems
di: Ohsaka, Naoto
Pubblicazione: (2023)

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

Algorithmizing the Multiplicity Schwartz-Zippel Lemma
di: Bhandari, Siddharth, et al.
Pubblicazione: (2021)

A Courcelle-Type Metatheorem for Rank-Bounded Unconstrained Binary Optimization
di: Harary, Marc
Pubblicazione: (2025)

Finding Minimum Distance Preservers: A Parameterized Study
di: Simonov, Kirill, et al.
Pubblicazione: (2026)

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

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

How to Reconfigure Your Alliances
di: Fernau, Henning, et al.
Pubblicazione: (2025)

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

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

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

On the Incompressibility of Truth With Application to Circuit Complexity
di: Tonon, Luke
Pubblicazione: (2025)

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

Enumeration With Nice Roman Domination Properties
di: Mann, Kevin
Pubblicazione: (2025)

The PPP-completeness of the Ward-Szabo theorem
di: Ishizuka, Takashi
Pubblicazione: (2025)

Maximum Reachability Orientation of Mixed Graphs
di: Hörsch, Florian
Pubblicazione: (2025)

Parameterized Complexity of Segment Routing
di: Bazgan, Cristina, et al.
Pubblicazione: (2025)

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

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

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

Gap Preserving Reductions Between Reconfiguration Problems
di: Ohsaka, Naoto
Pubblicazione: (2022)

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

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

Enumerating Minimal Defensive Alliances
di: Feng, Zhidan, et al.
Pubblicazione: (2023)

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

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

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

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

Maximal Line Digraphs
di: Japhet, Quentin, et al.
Pubblicazione: (2024)

Inapproximability of the independent set polynomial in the complex plane
di: Bezakova, Ivona, et al.
Pubblicazione: (2017)

Faster algorithms for graph homomorphism via tractable constraint satisfaction
di: Carbonnel, Clément
Pubblicazione: (2026)

$m$-Eternal Dominating Set Problem on Subclasses of Chordal Graphs
di: Rai, Ashutosh, et al.
Pubblicazione: (2026)

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

Complexity of Boolean automata networks under block-parallel update modes
di: Perrot, Kévin, et al.
Pubblicazione: (2024)

On the equivalence of two post-quantum cryptographic families
di: Meneghetti, Alessio, et al.
Pubblicazione: (2021)

Graphs without a partition into two proportionally dense subgraphs
di: Bazgan, Cristina, et al.
Pubblicazione: (2018)

Distance Vector Domination
di: Cordasco, Gennaro, et al.
Pubblicazione: (2024)

Effective Bounds for Restricted $3$-Arithmetic Progressions in $\mathbb{F}_p^n$
di: Bhangale, Amey, et al.
Pubblicazione: (2023)