Lower Bounds for Elimination via Weak Regularity

DOI10.4230/LIPIcs.STACS.2017.21zbMath1402.68072OpenAlexW2605122076MaRDI QIDQ4636619

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

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

regularitydiscrepancycommunication complexityeliminationgreater-than

Mathematics Subject Classification ID

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

Related Items (7)

Query-to-communication lifting for \(\mathsf{P}^{\mathsf{NP}}\) ⋮ The choice and agreement problems of a random function ⋮ From Expanders to Hitting Distributions and Simulation Theorems ⋮ Simulation theorems via pseudo-random properties ⋮ On derandomized composition of Boolean functions ⋮ Lifting Theorems for Equality ⋮ Query-To-Communication Lifting for BPP Using Inner Product

This page was built for publication: Lower Bounds for Elimination via Weak Regularity