Sensitivity Conjecture and Complexity Measures in Computer Science
Explore the intriguing Sensitivity Conjecture, its implications, and the relationship between sensitivity, degree, and complexity measures in computer science research. Discover how sensitivity influences communication games, function evaluation, and more.
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. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
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.
E N D
Presentation Transcript
A New Approach to the Sensitivity Conjecture Justin Gilmer Rutgers U. Michal Kouck Charles U. Mike Saks Rutgers U.
A Cooperative Communication Game ? 0,1? Receives message from Alice Outputs set ? s.t. ?? ? Receives ? ?? step by step and bit ? Fills ? in order of ? ???? = max ?,?| ? |
How Alice Communicates ? 0,1? ? {0,1} 3 6 1 5 4 2 ?: ?: 0 1 1 0 ? 1
Example 1 ? 0,1? Alice writes 0 on first ?/2 locations received, then writes 1 3 6 1 5 4 2 ?: ?: 0 1 0 1 ? 0 worst case cost = ?/2 + 1
Example (AND-OR Protocol) ? 0,1? Split [?] into ? groups of size ? Write 0 unless ?? is the last in its group to appear. 3 6 1 2 4 7 5 9 8 ?: 0 ? 0 v: 0 1 0 1 0 0 worst case cost = ?
Let ?(?) denote the minimum cost of any protocol on ? variables. Conjecture: There exists a ? > 0such that ? ? = ?(??). Theorem: This conjecture implies the Sensitivity Conjecture.
Sensitivity of a function 0 1 0 1 1 0 0 1 ? = 0 ? = 1 0 1 1 1 1 0 0 1 0 1 0 1 1 0 1 1 0 1 0 0 1 0 0 1 Sensitivity the number of coordinates that flip value of ?
Degree of a function Degree of the (unique) multilinear polynomial representing the function over reals. OR ?1,?2,?3 Example: ? ?1,?2,?3 = ?1?2?3 ?1?2 ?2?3 ?1?3+ ?1+?2+ ?3
Complexity measures for a function Sensitivity Degree Approximate degree Decision-tree complexity Block sensitivity Certificate complexity polynomially related
Sensitivity conjecture Conjecture: Sensitivity is polynomially related to degree. Thm: A function with a large gap between sensitivity ? and its degree ? gives a good strategy for Alice and Bob.
Small sensitivity small cost ? degree ? sensitivity ? Alice sets each bit ?? so that ? remains non-constant. Setting the last bit to ? sets ? to either 0 or 1. The last bit ?? is a sensitive coordinate of ?. Bob outputs the set ? of sensitive coordinates of ?.
What we know Best protocol (so far): cost < (1 ?) ? Two stronger conjectures are false: If Alice can use an alphabet of size 3, then protocol with cost ?(log ? ). Natural notion of Information cost of a protocol satisfies Cost > 2IC but protocol with 2IC= logO(1)? . In both counterexamples, protocols are monotone For original (unstrengthened) conjecture: any monotone protocol has cost at least ( ?)
3log(n) cost ternary protocol Alice writes 2 on first ? 3 log(?) received locations Uses 0,1 s to encode the set S = {?? 3 log ?, ,??} 3 6 1 2 4 7 5 9 8 ?: 2 1 2 0 b 2 1 2 2 v: Bob can figure out codeword (with one deletion) If ? = 2, Bob knows ? and what is missing from it If ? 2, only 3 log(?) possibilities for ??
Block sensitivity of a function 0 1 0 1 1 0 0 1 ? = 0 ? = 1 0 1 1 1 1 0 0 1 0 1 0 1 1 0 1 1 0 1 0 0 1 0 0 1 0 1 0 1 1 1 0 0 Block sensitivity the maximum number of disjoint blocks of coordinates that flip the value
