Copertina

An XOR Lemma for Deterministic Communication Complexity

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Iyer, Siddharth, Rao, Anup
Natura:	Preprint
Pubblicazione:	2024
Soggetti:	Computational Complexity
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

XOR Lemmas for Communication via Marginal Information
di: Iyer, Siddharth, et al.
Pubblicazione: (2023)

Strong XOR Lemma for Information Complexity
di: Sawettamalya, Pachara, et al.
Pubblicazione: (2024)

One-Way Communication Complexity of Partial XOR Functions
di: Podolskii, Vladimir V., et al.
Pubblicazione: (2023)

Lifting for Arbitrary Gadgets
di: Iyer, Siddharth
Pubblicazione: (2025)

Simple Circuit Extensions for XOR in PTIME
di: Carmosino, Marco, et al.
Pubblicazione: (2025)

Refuting the Direct Sum Conjecture for Total Functions in Deterministic Communication Complexity
di: Mackenzie, Simon, et al.
Pubblicazione: (2024)

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

Refuting approaches to the log-rank conjecture for XOR functions
di: Hatami, Hamed, et al.
Pubblicazione: (2023)

Intersection and Union Hierarchies of Deterministic Context-Free Languages and Pumping Lemmas
di: Yamakami, Tomoyuki
Pubblicazione: (2021)

Expanders Meet Reed-Muller: Easy Instances of Noisy k-XOR
di: Błasiok, Jarosław, et al.
Pubblicazione: (2026)

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

Toward Better Depth Lower Bounds: Strong Composition of XOR and a Random Function
di: Chukhin, Nikolai, et al.
Pubblicazione: (2024)

NP-Completeness of Deterministic Communication Complexity via Relaxed Interlacing
di: Gaspers, Serge, et al.
Pubblicazione: (2025)

Deterministic Lifting Theorems for One-Way Number-on-Forehead Communication
di: Yang, Guangxu, et al.
Pubblicazione: (2025)

Algorithmic Structure in Subset Sum: Deterministic In-Bound Navigation and the Counting Complexity Divide
di: Nkosi, Thami
Pubblicazione: (2025)

Feasibly Constructive Proof of Schwartz-Zippel Lemma and the Complexity of Finding Hitting Sets
di: Atserias, Albert, et al.
Pubblicazione: (2024)

A Near-Optimal Polynomial Distance Lemma Over Boolean Slices
di: Amireddy, Prashanth, et al.
Pubblicazione: (2025)

A Distance Amplification Lemma for Monotonicity
di: Minzer, Dor
Pubblicazione: (2025)

SAT, Gadgets, Max2XOR, and Quantum Annealers
di: Ansótegui, Carlos, et al.
Pubblicazione: (2024)

Pseudodeterministic Communication Complexity
di: Göös, Mika, et al.
Pubblicazione: (2025)

Structure in Communication Complexity and Constant-Cost Complexity Classes
di: Hatami, Hamed, et al.
Pubblicazione: (2024)

Communication Complexity is NP-hard
di: Hirahara, Shuichi, et al.
Pubblicazione: (2025)

Most Juntas Saturate the Hardcore Lemma
di: Kumar, Vinayak M.
Pubblicazione: (2025)

Quantum Lovász Local Lemma: Shearer's Bound is Tight
di: He, Kun, et al.
Pubblicazione: (2018)

Near Optimal Algorithms for Noisy $k$-XOR under Low-Degree Heuristic
di: Mao, Songtao
Pubblicazione: (2026)

Multiparty Communication Complexity of Collision Finding
di: Beame, Paul, et al.
Pubblicazione: (2024)

Optimal Communication Complexity of Chained Index
di: Sundaresan, Janani
Pubblicazione: (2024)

A Hierarchy for Constant Communication Complexity
di: Ambainis, Andris, et al.
Pubblicazione: (2025)

Average-Case Reductions for $k$-XOR and Tensor PCA
di: Bresler, Guy, et al.
Pubblicazione: (2026)

Fine-Grained Cryptanalysis: Tight Conditional Bounds for Dense k-SUM and k-XOR
di: Dinur, Itai, et al.
Pubblicazione: (2021)

Schwarz-Pick Lemma for Invariant Harmonic Functions on the Complex Unit Ball
di: Jaglan, Kapil, et al.
Pubblicazione: (2026)

Deterministic Weighted Automata under Partial Observability
di: Michaliszyn, Jakub, et al.
Pubblicazione: (2024)

Trinomials and Deterministic Complexity Limits for Real Solving
di: Boniface, Emma, et al.
Pubblicazione: (2022)

An Exponential Separation between Deterministic CDCL and DPLL Solvers
di: Samar, Sahil, et al.
Pubblicazione: (2026)

A Quantum Pigeonhole Principle and Two Semidefinite Relaxations of Communication Complexity
di: Dvořák, Pavel, et al.
Pubblicazione: (2024)

Average-Case Hardness of Binary-Encoded Clique in Proof and Communication Complexity
di: de Rezende, Susanna F., et al.
Pubblicazione: (2026)

One-way Communication Complexity of Minimum Vertex Cover in General Graphs
di: Derakhshan, Mahsa, et al.
Pubblicazione: (2025)

Deterministic Hardness of Approximation For SVP in all Finite $\ell_p$ Norms
di: Hair, Isaac M, et al.
Pubblicazione: (2026)

Low-Stabilizer-Complexity Quantum States Are Not Pseudorandom
di: Grewal, Sabee, et al.
Pubblicazione: (2022)

Communication Complexity of Disjointness under Product Distributions
di: Hunter, Zach, et al.
Pubblicazione: (2026)