

A Faster Algorithm for Solving General LPs,
with Shunhua Jiang, Zhao Song, Hengjie Zhang,
STOC'21 (to appear)  Arxiv


Polynomial Data Structure Lower Bounds in the Group Model,
with Gleb Posobin, Alexandr Golovnev, Oded Regev,
FOCS'20 (Invited to SICOMP special issue ) 
ECCC


Static Data Structure Lower Bounds Imply Rigidity,
with Zeev Dvir and Alexander Golovnev,
Invited extended talk at 2018 Simons Lower Bounds semester,
[E.Viola's blog post]
) 

Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds,
with Kasper Green Larsen and Huacheng Yu,
STOC'18 ( Invited to SICOMP special issue) 
[ECCC]
Invited TCS+ Talk, April 2017


On the Communication Complexity of Approximate Fixed Points,
with Tim Roughgarden,


Approximating the best Nash Equilibrium in $n^{o(log n)}$time breaks the Exponential Time Hypothesis,
with Mark Braverman and Young Kun Ko,
Invited TCS+ Talk, March 2017 

Direct Products in Communication Complexity,
with Mark Brverman, Anup Rao and Amir Yehudayoff,
Invited TCS+ talk, February 2013


PhD Thesis : Interactive Information Complexity and Applications
 [link]


Training (Overparametrized) Neural Networks in NearLinear Time,
with Jan Vander Brand, Bingui Peng, Zhao Song,


Faster Dynamic Matrix Inverse for Faster LPs,
with Shunhua Jiang, Zhao Song, Hengjie Zhang,
Summary: Motivated by recent LP solvers, we design a novel dynamic data
structure for maintaining the inverse of an n x n real matrix under
\emph{lowrank} updates, with polynomially faster amortized running time. This data structure leads
to the fastest known LP solver for general (dense) linear programs.


Polynomial Data Structure Lower Bounds in the Group Model,
with Gleb Posobin, Alexandr Golovnev, Oded Regev,
FOCS'20 (Invited to SICOMP special issue ) 
ECCC
Summary:
Proving superlogarithmic data structure lower bounds in the static group model has been a fundamental challenge in computational
geometry since the early 80's. We prove a polynomial lower bound on the query time of
linearspace arithmetic data structures for an explicit rangecounting problem of convex polygons in $\R^2$.


An Adaptive Step Toward the Multiphase Conjecture,
with Young KunKo ,
Summary: We develop a new tool in information complexity and use it to make progress
on Patrascu's Multiphase Conjecture, proving a polynomial (~ $\backslash sqrt\{n\}$) lower bound on weaklyadaptive dynamic data
structures .


Settling the Relationship of Wilber's Bounds for Dynamic Optimality,
with Victor Lecomte ,
Summary: We resolve a 35year open question of Wilber on combinatorial
lower bounds for online binary search trees, related to the longstanding Dynamic Optimality conjecture (Tarjan
and Sleator, 1985).


How to Store a Random Walk,
with Emanuele Viola and Huacheng Yu,
Summary:
We study the problem of "locallydecodable" data compression of correlated data, and show that random walks
can be stored close to their entropy, while facilitating constanttime decoding of any step on a wordRAM.


Lower Bounds for Oblivious NearNeighbor Search,
with Kasper Green Larsen, Tal Malkin and Kevin Yeo,
Summary:
A quadratic improvement over the highest unconditional lower bound for oblivious (secure)
nearneighbor search in dynamic settings.


Data Structure Lower Bounds Imply Rigidity,
with Zeev Dvir and Alexander Golovnev,
Summary:
We prove a new relationship between additive and multiplicative lowrank factorizations of a matrix, and use
it to show a new connection between static data structure lower bounds and matrix rigidity.


Local Decodability of the BurrowsWheeler Transform,
with Sandip Sinha,
Summary:
We show how to compress strings using their BW transform so that each character can be decoded locally,
and use our data structure to achieve an exponential speedup for compressed patternmatching on strings.


Massively Parallel Algorithms for Finding WellConnected Components in Sparse Graphs,
with Sepehr Assadi and Xiaorui Sun,
Summary:
An exponentially faster parallel (MapReduce) algorithm for reachability on sparse expanding graphs.


Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds,
with Kasper Green Larsen and Huacheng Yu,
STOC'18 ( Invited to SICOMP special issue, Invited TCS+ talk)
[ECCC]
Summary:
The first superlogarithmic unconditional lower bound on dynamic decision problems, partially settling Patrascu's
obituary question and the classic "range counting" problem in 2D.


The Minrank of Random Graphs,
with Alexander Golovnev and Oded Regev,
IEEE Transactions on Information Theory (preliminary version in RANDOM'17) 
[ECCC]
Summary:
We settle the problem of linear index coding over random knowledge graphs, by proving a tight (\Theta(n/lgn))
bound on the minrank of random ErdosRenyi graphs.


Amortized Dynamic CellProbe Lower Bounds from FourParty Communication,
with Huacheng Yu,
Summary:
We develop a new techniques for proving amortized dynamic data structure lower bounds (through a new
nondeterministic communication model), and use it to settle the complexity of dynamic weighted 2D range counting.


On the Communication Complexity of Approximate Fixed Points,
with Tim Roughgarden,
Summary:
We prove the first communication lower bounds on the 2party problem of computing approximate
fixedpoints of a composition of two Lipschitz functions f*g. Our "geometric lifting" technique was subsequently
used to settle the important open problem of distributed computation of approximate Nash equilibria.


An Improved Upper Bound for the Most Informative Boolean Function Conjecture
with Or Ordentlich and Ofer Shayevitz,
Summary:
We improve the previously best known lower bound on the highest "correlation" a Boolean function can
have with a noisy binary string, relating hypercontractivity to mutual information.


Distributed Signaling Games
with Moran Feldman and Moshe Tennenholtz,
Summary:
We introduce a more realistic model of "signaling" in auctions where agents have knowledge
on the underlying prior value. We design an equilibrium and a 5approximation to revenue
in a natural special class .


Information Complexity and the Quest for Interactive
Compression
SIGACT News Complexity Column, June 2015 issue (invited survey) 
[ECCC] 

ETH Hardness for Densest$k$Subgraph
with Perfect Completeness
with Mark Braverman, Young Kun Ko and Aviad Rubinstein,
Summary:
We give a tight ~n^log(n) lower bound for the problem of finding a dense subgraph in a graph containing a
large clique (Feige&Seltser), using informationtheoretic tools to analyze the ``birthday repetition" reduction.


Welfare Maximization with Limited Interaction,
with Noga Alon, Noam Nisan and Ran Raz,
Summary:
We prove that finding an approximate maximum matching in nbidder games requires Omega(log log n) rounds of
communication, the first superconstant lower bound for general (unboundedround) communication.


The Simultaneous Communication of Disjointness with Applications to Data Streams,
with David P. Woodruff,
Summary:
We settle the simultaneous communication complexity of multiparty (NIH) set disjointness and use it to prove
an essentially tight lower bound on streaming frequency moments.


Approximating the best Nash Equilibrium in $n^{o(log n)}$time breaks the Exponential Time Hypothesis,
with Mark Braverman and Young Kun Ko,
SODA '15 (Invited TCS+ Talk) 
[ECCC]
Summary:
We settle the problem of finding an approximatelyoptimal Nash equilibrium in 2party games under the
ETH conjecture, using a novel adaptation of the ``birthday repetition" technique in 2prover ``free games" [AIM'13].


Welfare and Revenue Guarantees of Competitive Bundling Equilibrium,
with Shahar Dobzinski, Michal Feldman and Inbal TalgamCohen,


An Interactive Information Odometer with Applications,,
with Mark Braverman,
STOC '15 ,

[ECCC]
Summary:
We develop a novel interactive technique that allows two players to keep an online estimate of the internal information
cost of their communication, and use it to settle the direct product problem for information complexity in terms
of communication.


Toward Better Formula Lower Bounds: An Information Complexity Approach
to the KRW Composition Conjecture,
with Dmitry Gavinsky, Or Meir and Avi Wigderson,
STOC '14
(Invited to Algorithmica special issue)  [ECCC]
Summary:
We use information complexity techniques to give the first improvement in a decade for the important
KRW conjecture (for separating P from NC1).


Direct Products in Communication Complexity,
with Mark Brverman, Anup Rao and Amir Yehudayoff,
FOCS '13 (Invited TCS+ Talk)  [ECCC]
Summary:
We prove the first directproduct theorem for general twoparty communication complexity. This blackbox hardness
amplification theorem was key to many subsequent lower bounds in complexity theory and streaming.


Direct Product via RoundPreserving Compression,
with Mark Brverman, Anup Rao and Amir Yehudayoff,


From Information to Exact Communication,
with Mark Braverman, Ankit Garg and Denis Pankratov,
Summary:
We develop a framework for proving exact bounds on the 0error information
cost of communication problems, via martingale theory, and use it to settle the communication complexity
of Set Disjointness (0.482n).


A Discrepancy Lower Bound for Information Complexity,
with Mark Braverman,
Summary:
The first technique (in a line of subsequent works) for proving lower bounds on the information complexity of
twoparty randomized communication problems.


Information Lower Bounds via Self Reducibility,
with Mark Braverman, Ankit Garg and Denis Pankratov,
CSR '13 (Best paper award)  [ECCC]
Summary:
We use selfreduction methods to prove strong information lower bounds on two of the most studied functions in
the communication complexity literature: Gap Hamming Distance (GHD) and Inner Product (IP).


Unsupervised SVM's: On the Furthest Hyperplane Problem,
with Zohar Karnin, Edo Liberty, Shachar Lovett, and Roy Schwartz,


Approximating the Influence of a Monotone Boolean function in O(sqrt(n)) query complexity,
with Dana Ron, Ronitt Rubinfeld, Alex Smorodinsky and Muli Safra,


Inapproximabilty of Densest $k$Subgraph from Average Case Hardness,
with Noga Alon, Sanjeev Arora, Rajsekar Manokaran and Dana Moshkovitz,


PhD Thesis : Interactive Information Complexity and Applications
 [link]



Information Theory in TCS (COMSE 6998004)
(Columbia, Fall '20)
[webepage]. 


CS Theory (COMS 3261)
(Columbia, Fall '19)
[webepage]. 


Advanced Data Structures (COMSE 6998008)
(Columbia, Spring '19)
[webepage]. 


Introduction to Complexity Theory (COMSE 4236) (Columbia, Fall '18) 


Information Theory In TCS (COMSE 6998) (Columbia, Fall '17)
[webepage]. 


DataStructure Lower Bounds Reading
Group (Columbia)
[webepage]. 

