Larger Corner-Free Sets from Better NOF Exactly-$N$ Protocols

DOI10.19086/da.28933OpenAlexW3202598313MaRDI QIDQ5028500

Adi Shraibman, Nathan Linial

Publication date: 10 February 2022

Published in: discrete Analysis (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2102.00421

zbMATH Keywords

communication complexitycorner-free sets

Mathematics Subject Classification ID

Circuits, networks (94C99) Arithmetic progressions (11B25) Communication complexity, information complexity (68Q11)

Related Items (3)

Removal lemmas and approximate homomorphisms ⋮ The number of \(k\)-dimensional corner-free subsets of grids ⋮ Multiple recurrence and large intersections for abelian group actions

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The NOF multiparty communication complexity of composed functions
• On the power of small-depth threshold circuits
• On the ratio of optimal integral and fractional covers
• An improved construction of progression-free sets
• Number on the forehead protocols yielding dense Ruzsa-Szemerédi graphs and hypergraphs
• Lower bounds for corner-free sets
• Lower Bounds for Lovász–Schrijver Systems and Beyond Follow from Multiparty Communication Complexity
• On sets of integers containing k elements in arithmetic progression
• Communication Complexity
• Separating Deterministic from Nondeterministic NOF Multiparty Communication Complexity
• The Multiparty Communication Complexity of Exact-T: Improved Bounds and New Problems
• On Certain Sets of Integers
• On Sets of Integers Which Contain No Three Terms in Arithmetical Progression

This page was built for publication: Larger Corner-Free Sets from Better NOF Exactly-$N$ Protocols