2 citations · 3 across the 5 of their papers we have counts for
8 papers
The Switching Lemma shows what the Switching Lemma cannot prove: an unconditional natural-proofs barrier
Bruno Loff, Suhail Sherif, Navid Talebanfard +1
Razborov and Rudich (JCSS'97) observed that all known lower-bound proofs follow a certain pattern: when showing that a function is hard, along the way the proof provides us wit…
A Quantum Pigeonhole Principle and Two Semidefinite Relaxations of Communication Complexity
Pavel Dvořák, Bruno Loff, Suhail Sherif
We study semidefinite relaxations of combinatorial statements. By relaxing the pigeonhole principle, we obtain a new "quantum" pigeonhole principle which is a stronger statem…
An improved protocol for ExactlyN with more than 3 players
Lianna Hambardzumyan, Toniann Pitassi, Suhail Sherif +2
The ExactlyN problem in the number-on-forehead (NOF) communication setting asks players, each of whom can see every input but their own, if the input numbers add up to .…
Lifting to Parity Decision Trees Via Stifling
Arkadev Chattopadhyay, Nikhil S. Mande, Swagato Sanyal +1
We show that the deterministic decision tree complexity of a (partial) function or relation lifts to the deterministic parity decision tree (PDT) size complexity of the compose…
Near-Optimal Lower Bounds For Convex Optimization For All Orders of Smoothness
Ankit Garg, Robin Kothari, Praneeth Netrapalli +1
We study the complexity of optimizing highly smooth convex functions. For a positive integer , we want to find an -approximate minimum of a convex function , given oracle…
One-way communication complexity and non-adaptive decision trees
Nikhil S. Mande, Swagato Sanyal, Suhail Sherif
We study the relationship between various one-way communication complexity measures of a composed function with the analogous decision tree complexity of the outer function. We con…
No quantum speedup over gradient descent for non-smooth convex optimization
Ankit Garg, Robin Kothari, Praneeth Netrapalli +1
We study the first-order convex optimization problem, where we have black-box access to a (not necessarily smooth) function and its (sub)gradient. O…
Towards Stronger Counterexamples to the Log-Approximate-Rank Conjecture
Arkadev Chattopadhyay, Ankit Garg, Suhail Sherif
We give improved separations for the query complexity analogue of the log-approximate-rank conjecture i.e. we show that there are a plethora of total Boolean functions on input…