Cover Image

XOR Lemmas for Communication via Marginal Information

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Iyer, Siddharth, Rao, Anup
Format:	Preprint
Published:	2023
Subjects:	Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

An XOR Lemma for Deterministic Communication Complexity
by: Iyer, Siddharth, et al.
Published: (2024)

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

Lifting for Arbitrary Gadgets
by: Iyer, Siddharth
Published: (2025)

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

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

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

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

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

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

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

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

A Distance Amplification Lemma for Monotonicity
by: Minzer, Dor
Published: (2025)

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

Most Juntas Saturate the Hardcore Lemma
by: Kumar, Vinayak M.
Published: (2025)

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

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

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

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

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

On Applications of Extended Jack's Lemma
by: Kumar, S. Sivaprasad, et al.
Published: (2021)

The Limits of Tractable Marginalization
by: Broadrick, Oliver, et al.
Published: (2025)

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

Communication complexity of pointer chasing via the fixed-set lemma
by: Viola, Emanuele
Published: (2025)

New Algebrization Barriers to Circuit Lower Bounds via Communication Complexity of Missing-String
by: Chen, Lijie, et al.
Published: (2025)

Quantum Advantage from Sampling Shallow Circuits: Beyond Hardness of Marginals
by: Grier, Daniel, et al.
Published: (2025)

Efficient quantum circuits for high-dimensional representations of SU(n) and Ramanujan quantum expanders
by: Iyer, Vishnu, et al.
Published: (2026)

Pseudoentanglement Ain't Cheap
by: Grewal, Sabee, et al.
Published: (2024)

Pseudodeterministic Communication Complexity
by: Göös, Mika, et al.
Published: (2025)

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

Improved Stabilizer Estimation via Bell Difference Sampling
by: Grewal, Sabee, et al.
Published: (2023)

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

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

Optimal Communication Complexity of Chained Index
by: Sundaresan, Janani
Published: (2024)

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

No Complete Problem for Constant-Cost Randomized Communication
by: Fang, Yuting, et al.
Published: (2024)

NP-Completeness of Multicast Beamforming in Wireless Communication
by: Shrestha, Sagar
Published: (2025)

Randomized $\tilde{O}(m\sqrt{n})$ Bellman-Ford from Fineman and the Boilermakers
by: Rao, Satish
Published: (2025)

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

Equality is Far Weaker than Constant-Cost Communication
by: Göös, Mika, et al.
Published: (2025)

Constant-Cost Communication is not Reducible to k-Hamming Distance
by: Fang, Yuting, et al.
Published: (2024)