All

What are you looking for?

All
Projects
Results
Organizations

Quick search

  • Projects supported by TA ČR
  • Excellent projects
  • Projects with the highest public support
  • Current projects

Smart search

  • That is how I find a specific +word
  • That is how I leave the -word out of the results
  • “That is how I can find the whole phrase”

Lower Bounds for Elimination via Weak Regularity

The result's identifiers

  • Result code in IS VaVaI

    <a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F17%3A10368568" target="_blank" >RIV/00216208:11320/17:10368568 - isvavai.cz</a>

  • Result on the web

    <a href="http://drops.dagstuhl.de/opus/volltexte/2017/7012/pdf/LIPIcs-STACS-2017-21.pdf" target="_blank" >http://drops.dagstuhl.de/opus/volltexte/2017/7012/pdf/LIPIcs-STACS-2017-21.pdf</a>

  • DOI - Digital Object Identifier

    <a href="http://dx.doi.org/10.4230/LIPIcs.STACS.2017.21" target="_blank" >10.4230/LIPIcs.STACS.2017.21</a>

Alternative languages

  • Result language

    angličtina

  • Original language name

    Lower Bounds for Elimination via Weak Regularity

  • Original language description

    We consider the problem of elimination in communication complexity, that was first raised by Ambainis et al. and later studied by Beimel et al. [4] for its connection to the famous direct sum question. In this problem, let f be any boolean function. Alice and Bob get k inputs x_1, . . . , x_k and y_1, . . . , y_k respectively. They want to output a k-bit vector v, such that there exists one index i for which v_i is not equal to f(x_i, y_i). We prove a general result lower bounding the randomized communication complexity of the elimination problem for f using its discrepancy. Consequently, we obtain strong lower bounds for the functions InnerProduct and Greater-Than, that work for exponentially larger values of k than the best previous bounds. To prove our result, we use a pseudo-random notion called regularity that was first used by Raz and Wigderson. We show that functions with small discrepancy are regular. We also observe that a weaker notion, that we call weak-regularity, already implies hardness of elimination. Finally, we give a different proof, borrowing ideas from Viola, to show that Greater-Than is weakly regular.

  • Czech name

  • Czech description

Classification

  • Type

    D - Article in proceedings

  • CEP classification

  • OECD FORD branch

    10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Result continuities

  • Project

  • Continuities

    R - Projekt Ramcoveho programu EK

Others

  • Publication year

    2017

  • Confidentiality

    S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Data specific for result type

  • Article name in the collection

    34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)

  • ISBN

    978-3-95977-028-6

  • ISSN

    1868-8969

  • e-ISSN

    neuvedeno

  • Number of pages

    14

  • Pages from-to

    1-14

  • Publisher name

    Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik

  • Place of publication

    Dagstuhl, Germany

  • Event location

    Hannover

  • Event date

    Mar 8, 2017

  • Type of event by nationality

    WRD - Celosvětová akce

  • UT code for WoS article