Lower bounds for elimination via weak regularity

DOI10.4230/LIPICS.STACS.2017.21zbMATH Open1402.68072OpenAlexW2605122076MaRDI QIDQ4636619FDOQ4636619

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/

Recommendations

• The communication complexity of enumeration, elimination, and selection
• scientific article; zbMATH DE number 1769898
• Choosing, agreeing, and eliminating in communication complexity
• A discrepancy lower bound for information complexity
• A discrepancy lower bound for information complexity

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)

Cited In (9)

• Query-to-communication lifting for \(\mathsf{P}^{\mathsf{NP}}\)
• Simulation theorems via pseudo-random properties
• From Expanders to Hitting Distributions and Simulation Theorems
• The communication complexity of enumeration, elimination, and selection
• Query-To-Communication Lifting for BPP Using Inner Product
• On derandomized composition of Boolean functions
• A Wowzer-type lower bound for the strong regularity lemma
• The choice and agreement problems of a random function
• Lifting Theorems for Equality

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)