Directed Hypercube Routing, a Generalized Lehman-Ron Theorem, and Monotonicity Testing
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866929615621062656 |
|---|---|
| author | Chakrabarty, Deeparnab Seshadhri, C. |
| author_facet | Chakrabarty, Deeparnab Seshadhri, C. |
| contents | Motivated by applications to monotonicity testing, Lehman and Ron (JCTA, 2001) proved the existence of a collection of vertex disjoint paths between comparable sub-level sets in the directed hypercube. The main technical contribution of this paper is a new proof method that yields a generalization to their theorem: we prove the existence of two edge-disjoint collections of vertex disjoint paths. Our main conceptual contribution are conjectures on directed hypercube flows with simultaneous vertex and edge capacities of which our generalized Lehman-Ron theorem is a special case. We show that these conjectures imply directed isoperimetric theorems, and in particular, the robust directed Talagrand inequality due to Khot, Minzer, and Safra (SIAM J. on Comp, 2018). These isoperimetric inequalities, that relate the directed surface area (of a set in the hypercube) to its distance to monotonicity, have been crucial in obtaining the best monotonicity testers for Boolean functions. We believe our conjectures pave the way towards combinatorial proofs of these directed isoperimetry theorems. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_02206 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Directed Hypercube Routing, a Generalized Lehman-Ron Theorem, and Monotonicity Testing Chakrabarty, Deeparnab Seshadhri, C. Discrete Mathematics Data Structures and Algorithms Combinatorics Motivated by applications to monotonicity testing, Lehman and Ron (JCTA, 2001) proved the existence of a collection of vertex disjoint paths between comparable sub-level sets in the directed hypercube. The main technical contribution of this paper is a new proof method that yields a generalization to their theorem: we prove the existence of two edge-disjoint collections of vertex disjoint paths. Our main conceptual contribution are conjectures on directed hypercube flows with simultaneous vertex and edge capacities of which our generalized Lehman-Ron theorem is a special case. We show that these conjectures imply directed isoperimetric theorems, and in particular, the robust directed Talagrand inequality due to Khot, Minzer, and Safra (SIAM J. on Comp, 2018). These isoperimetric inequalities, that relate the directed surface area (of a set in the hypercube) to its distance to monotonicity, have been crucial in obtaining the best monotonicity testers for Boolean functions. We believe our conjectures pave the way towards combinatorial proofs of these directed isoperimetry theorems. |
| title | Directed Hypercube Routing, a Generalized Lehman-Ron Theorem, and Monotonicity Testing |
| topic | Discrete Mathematics Data Structures and Algorithms Combinatorics |
| url | https://arxiv.org/abs/2409.02206 |