Advanced Concepts in Computational Theory

Slide Note

Explore the latest research on improved composition theorems for functions and relations, background on Boolean circuits, P vs. NP through circuits, and topics like Karchmer-Wigderson Relation, Communication Complexity, and Circuit complexity. Discover intriguing conjectures, intricate algorithms, and the interplay between different theoretical concepts in computer science.

sha_cam Follow

Uploaded on Sep 26, 2024 | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

E N D

Presentation Transcript

Improved Composition Theorems for Functions and Relations Sajin Koroth University of Haifa joint work with Or Meir University of Haifa

Background Boolean circuits Size : number of internal gates Depth : The length of the longest path from root to a leaf ?(?) : minimum depth of any circuit computing ? Circuit computing Parity on 2 bits

P vs NP through circuits P has Poly Size circuits NP is believed not to Unfortunately for ?? : 5 ? 1 ? lower bounds for weaker class of circuits

?? ?? ??1 and ? ?? ??1 ??1 : poly size, ? log ? depth, fan-in 2 ??1 : efficient parallel algorithms Weaker goal : ?? ??1 Belief : ? ??1 explicit function ? in ? with ? ? = ? log ?

Compositions and ? ?? ??1 Karchmer Raz and Wigderson 91 : study composition of functions tostudy depth Given ?:{0,1}? {0,1} and g:{0,1}? {0,1} define ? ? as a function on ?? bits

KRW Conjecture Fact : ? ? ? ? ? + ?(?) KRW Conjecture : ? ? ? ? ? + ?(?) If KRW Conjecture is true : explicit? in ? such that ? ? = (log ?) Implies ? ???

Communication Complexity Relation ? = ?,?,? ? ?,? ?,? ? Alice can t see Bob s input, Bob can t see Alice s input Goal : compute ? s.t., ?,?,? ? Cost of a protocol on (x,y) : The total number of bits Cost of a protocol : worst case over (x,y) For this talk : no randomness CC(R) : Minimum cost of a protocol solving R ? ?

Karchmer Wigderson Relation Let ?:{0,1}? {0,1} ? ? 1(1) ? ? 1(0) Goal : Find an index ? [?] for which ?? ?? Objective : Minimize the total number of bits spoken

Circuit complexity to communication KW 90 : ?? ??? = ?(?) Goal : find ?,?? ?? ? ? 1(1) ? ? 1(0)

KRW conjecture (communication version) ? ? = ??(???) KRW conjecture : ? ? ? ? ? + ?(?) ?? ??? ? ?? ??? + ??(???) KW relation of ? ? :

Simplifying functions Universal relation KRW conjecture implies ? ???and this is a very hard problem KRW suggested a simplification : universal relation Known : ?? ?? = ? Goal : find ?,?? ?? Promise : ? ? ? ? 1(1) ? ? ? 1(0) ?

Composition of Universal Relations Similar to ? ?, but drop ?, drop ? Suggested by KRW 95 : ?? ?? ?? ?? ?? + ?? ?? Promise 1 : ? ? Promise 2 : ?? ?? implies ?? ??

Known results First progress: Edmonds, Impagliazzo, Rudich and Sgall (EIRS) EIRS 91: ?? ?? ?? ? + ? ? The result is for ? = ? ? H stad and Wigderson 90: Alternate proof. Almost tight for ? = ?. HW 90 : ?? ?? ?? 2? 1

Composition of functions with universal relation : ? ?? Gavinsky, Meir, Weinstein and Wigderson (GMWW 14) defined ? ?? for any function ?: 0,1? {0,1} GMWW 14 : study ? ?? as next step between ?? ?? and ? ? GMWW 14 : ?? ? ?? log ? ? + ? ?(? ? log ?) This talk : log ? ? = ?(?)

Outline Our results Proof Overview Highlight of the key ideas of our improvement

Our Lower bounds ?? ? ?? log ? ? + ? ?(log ?) ?? ?? ?? ? + ? ?(log ?) Relation Relation Known Lower bounds Known Lower bounds Trivial Upper Bounds Bounds Trivial Upper Our Lower bound Our Lower bound ? + ? ?( ?) EIRS 91 ? + ? ?( ?) EIRS 91 ? + ? ?(log ?) ? + ? ?(log ?) log ? ? + ? ?(log ?) ?? ?? ?? ?? ? ?? ? + ? ? + ? log ?(?) + ? ? 1 +? log ? ? + ? log ? GMWW 14 ?

Motivation The KRW conjecture implies these conjectures To get ? ??1 from the KRW conjecture : ? ? for arbitrary ?, random ? Close to ? ?? But : need ? = 2 (?) Earlier : significant loss at ? = ?(?2) Detour: Avoiding ? = ?(??): ? ? for random ?, arbitrary ? Problem : Close to ?? ?, don t know lower bounds!

Basic intuition behind the lower bound Proof for ?? ?? Players have to solve ?? on at least one row They need the promise: ?? ?? Need to solve ?? to know for sure ?? ?? Notation : matrix part, vector part of players input

Adversarial Argument Takes protocol solving ?? ?? and produces an error transcript Deterministic protocol

Adversarial Argument for ?? Takes of length ? 2 and produces an error transcript Alice : ?? , Bob : ??, Goal : ? ? s.t. ?? ? (??)? After n-2 steps

High Level Idea Divide communication into two stages First stage : first ? ? bits (? : slack term) Intuition : players ideally solving ?? Second Stage : rest of the communication First stage transcript : ? bits in the second stage

An easy case Input to ?? ?? : ( ?,? , ?,? ). Matrix part : ?,?, vector part : ?,? Players don t speak about matrix part in the first stage They know nothing about any row second stage : at least ? bits (??(??))

Another easy case Players don t speak about vector part in the first stage They haven t solved ??at all #rows with more than ? bit of information < ? ? Make these rows useless. Set ??= ?? second stage : at least ? ? bits (??(??))

Challenging case Players speak about both matrix and column parts in the first stage They haven t solved ?? yet. They don t know any row where ?? ?? Goal : ensure communication about matrix part is wasted Strategy : Classify rows into : revealed and unrevealed Revealed : players spoke more than bits about the row. Unrevealed row : ? ? bits in the second stage For every revealed row : fix ??= ??

Fixing Revealed Rows need to fix ??= ?? for every revealed row Suppose : players learned ? bits about the matrix part Number of revealed rows : ?/? Constraint : #(revealed rows) < ? (? : bits not known about vector part) Lower bound : ? ? + ? ? subject to ? ?< ? First stage: m- ? EIRS : ?, ? = ? = ? ? ?< ?, ? > ? Lower bound : ? ? + ? ? k bits m- ? m-? bits m- ?

Our analysis Main Idea : first stage : communication (matrix part), ? bits + communication (vector part), ? ? ? bits Hence info unknown in vector :? ? + ? Lower bound : ? ? + ? ? subject to ? ?< ? Set ? > 1 ? ?< ? + ?. Hence ? ?< ? is satisfied

A complication first stage : communication (matrix part), ? bits + communication (vector part), ? ? ? bits Fixing ??= ??, could reveal a bit on the matrices Unrevealed row after fixing : ? + ?/? bits Solution : An Iterative Adversary a revealed row,? bits ? ? bits remaining ? ? + 1 bits remaining