Buchumschlag

Query complexity of Boolean functions on the middle slice of the cube

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Gerbner, Dániel, Keszegh, Balázs, Nagy, Dániel T., Nagy, Kartal, Pálvölgyi, Dömötör, Patkós, Balázs, Wiener, Gábor
Format:	Preprint
Veröffentlicht:	2023
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

On dual-ABAB-free and related hypergraphs
von: Keszegh, Balázs, et al.
Veröffentlicht: (2024)

A note on vertex Turán problems in the Kneser cube
von: Gerbner, Dániel, et al.
Veröffentlicht: (2024)

The complexity of recognizing $ABAB$-free hypergraphs
von: Damásdi, Gábor, et al.
Veröffentlicht: (2024)

Identification of a monotone Boolean function with $k$ "reasons" as a combinatorial search problem
von: Gerbner, Dániel, et al.
Veröffentlicht: (2024)

Coloring Geometric Hypergraphs: A Survey
von: Damásdi, Gábor, et al.
Veröffentlicht: (2025)

Orientation of convex sets
von: Ágoston, Péter, et al.
Veröffentlicht: (2022)

Orientation of good covers
von: Ágoston, Péter, et al.
Veröffentlicht: (2022)

Finding the diameter of a tree with distance queries
von: Gerbner, Dániel, et al.
Veröffentlicht: (2025)

Turán problems for simplicial complexes
von: Axenovich, Maria, et al.
Veröffentlicht: (2025)

Partitioned Matching Games for International Kidney Exchange
von: Benedek, Márton, et al.
Veröffentlicht: (2023)

A new discrete theory of pseudoconvexity
von: Keszegh, Balázs
Veröffentlicht: (2022)

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

Three-chromatic geometric hypergraphs
von: Damásdi, Gábor, et al.
Veröffentlicht: (2021)

Between the deterministic and non-deterministic query complexity
von: Gerbner, Dániel
Veröffentlicht: (2019)

On the number of tangencies among $1$-intersecting $x$-monotone curves
von: Ackerman, Eyal, et al.
Veröffentlicht: (2023)

On the minimum Hamming distance between vectorial Boolean and affine functions
von: Nagy, Gabor P.
Veröffentlicht: (2025)

Rainbow Turán problems for forbidden subposets
von: Patkós, Balázs
Veröffentlicht: (2025)

Size, diversity, minimum degree, sturdiness, dömdödöm
von: Patkós, Balázs
Veröffentlicht: (2025)

Anti-Ramsey forbidden poset problems
von: Patkós, Balázs
Veröffentlicht: (2026)

Unavoidable patterns and plane paths in dense topological graphs
von: Keszegh, Balázs, et al.
Veröffentlicht: (2025)

Note on polychromatic coloring of hereditary hypergraph families II
von: Pálvölgyi, Dömötör
Veröffentlicht: (2026)

On the maximum number of tangencies among $1$-intersecting curves
von: Ackerman, Eyal, et al.
Veröffentlicht: (2026)

The Zarankiewicz Problem for Polygon Visibility Graphs
von: Ackerman, Eyal, et al.
Veröffentlicht: (2025)

An Invariance Principle for the Multi-slice, with Applications
von: Braverman, Mark, et al.
Veröffentlicht: (2021)

A new intersection condition in extremal set theory
von: Nagy, Kartal
Veröffentlicht: (2025)

Classification of Non-redundancy of Boolean Predicates of Arity 4
von: Brakensiek, Joshua, et al.
Veröffentlicht: (2026)

$k$-dimensional transversals for fat convex sets
von: Jung, Attila, et al.
Veröffentlicht: (2023)

Saturation of edge-ordered graphs
von: Bošković, Vladimir, et al.
Veröffentlicht: (2024)

The double Hall property and cycle covers in bipartite graphs
von: Barát, János, et al.
Veröffentlicht: (2023)

The maximum number of digons formed by pairwise crossing pseudocircles
von: Ackerman, Eyal, et al.
Veröffentlicht: (2024)

On the number of digons in arrangements of pairwise intersecting circles
von: Ackerman, Eyal, et al.
Veröffentlicht: (2024)

Stabbing non-piercing sets and face lengths in large girth plane graphs
von: Pálvölgyi, Dömötör, et al.
Veröffentlicht: (2025)

On Triangles in Colored Pseudoline Arrangements
von: Radtke, Yan Alves, et al.
Veröffentlicht: (2026)

Improved Lower Bounds for all Odd-Query Locally Decodable Codes
von: Basu, Arpon, et al.
Veröffentlicht: (2024)

VC-Dimension vs Degree: An Uncertainty Principle for Boolean Functions
von: Chang, Fan, et al.
Veröffentlicht: (2025)

A note on infinite versions of $(p,q)$-theorems
von: Jung, Attila, et al.
Veröffentlicht: (2024)

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

Monochromatic configurations on a circle
von: Damásdi, Gábor, et al.
Veröffentlicht: (2025)

A note on the Erdős Matching Conjecture
von: Martin, Ryan R., et al.
Veröffentlicht: (2024)

On a generalization of a result of Kleitman
von: Martin, Ryan R., et al.
Veröffentlicht: (2024)