Login
Talks & Seminars
Title: A Short List of Equalities Induces Large Sign Rank
Mr. Nikhil Mande, TIFR
Date & Time: September 19, 2018 14:00
Venue: Room # 105, 01st Floor, Department of Computer Science and Engineering, New CSE/CC Building
Abstract:
We exhibit a natural function F_n on n variables, computable by a linear sized decision list of “Equalities”, but whose sign rank is exp(Omega(n^{1/4})). The simplicity of F_n yields the following two consequences. 1) F_n can be computed by linear sized depth-2 threshold formulas when the weights of the threshold gates are unrestricted (THR o THR), but any THR o MAJ circuit computing it requires size exp(Omega(n^{1/4})). This provides the first exponential separation between the boolean circuit complexity classes THR o MAJ and THR o THR, answering a question of Amano and Maruoka [MFCS’05] and Hansen and Podolskii [CCC'10]. In contrast, Goldmann, Hastad and Razborov [Computational Complexity’92] had shown more than 25 years ago that functions efficiently computable by MAJ o THR circuits can also be efficiently computed by MAJ o MAJ circuits. Thus, while weights at the bottom layer do not matter when the top is light, we discover that they do when the top is heavy. 2) The function F_n lies in the communication complexity class P^MA under the natural partition of the inputs. Since F_n has large sign rank, this implies P^MA is not a subset of UPP, strongly resolving a conjecture of Goos, Pitassi and Watson [ICALP’16]. In order to prove our main result, we view F_n as an XOR function, and develop a technique to lower bound the sign rank of such functions. This requires novel arguments that allow us to conclude that polynomials of low Fourier weight cannot approximate certain functions, even if they are allowed unrestricted degree. Based on joint work with Arkadev Chattopadhyay (TIFR), to appear in FOCS 2018.
Speaker Profile:
Details are available at http://www.tcs.tifr.res.in/~nikhil/.
List of Talks

Webmail

Username:
Password:
Faculty CSE IT
Forgot Password
    [+] Sitemap     Feedback