Lower bounds for elimination via weak regularity

DOI10.4230/LIPICS.STACS.2017.21MaRDI QIDQ4636619zbMATH OpenOpenAlexFDO

Authors Arkadev Chattopadhyay, Pavel Dvořák, Michal Koucký, Bruno Loff, Sagnik Mukhopadhyay

Publication date 19 April 2018

Full work available at URL http://drops.dagstuhl.de/opus/volltexte/2017/7012/pdf/LIPIcs-STACS-2017-21.pdf/

zbMATH Keywords

discrepancyregularitycommunication complexityeliminationgreater-than

Mathematics Subject Classification ID

Randomized algorithms (68W20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10)

Recommendations

• The communication complexity of enumeration, elimination, and selection
• scientific article; zbMATH DE number 1769898
• Choosing, agreeing, and eliminating in communication complexity

Cited in

(10)

• On derandomized composition of Boolean functions
• Query-to-communication lifting for \(\mathsf{P}^{\mathsf{NP}}\)
• Lifting Theorems for Equality
• Simulation theorems via pseudo-random properties
• From expanders to hitting distributions and simulation theorems
• Choosing, agreeing, and eliminating in communication complexity
• Query-to-communication lifting for BPP using inner product
• A Wowzer-type lower bound for the strong regularity lemma
• The communication complexity of enumeration, elimination, and selection
• The choice and agreement problems of a random function

This page was built for publication: Lower bounds for elimination via weak regularity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4636619)