|
|
| |
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] |
| |
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 Near-Linear Time,
with Jan Van-der 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{low-rank} 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 super-logarithmic 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
linear-space arithmetic data structures for an explicit range-counting problem of convex polygons in $\R^2$.
|
| |
An Adaptive Step Toward the Multiphase Conjecture,
with Young Kun-Ko ,
Summary: We develop a new tool in information complexity and use it to make progress
on Patrascu's Multiphase Conjecture, proving a polynomial (~ ) lower bound on weakly-adaptive dynamic data
structures .
|
| |
Settling the Relationship of Wilber's Bounds for Dynamic Optimality,
with Victor Lecomte ,
Summary: We resolve a 35-year open question of Wilber on combinatorial
lower bounds for online binary search trees, related to the long-standing 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 "locally-decodable" data compression of correlated data, and show that random walks
can be stored close to their entropy, while facilitating constant-time decoding of any step on a word-RAM.
|
| |
Lower Bounds for Oblivious Near-Neighbor Search,
with Kasper Green Larsen, Tal Malkin and Kevin Yeo,
Summary:
A quadratic improvement over the highest unconditional lower bound for oblivious (secure)
near-neighbor 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 low-rank 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 Burrows-Wheeler 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 pattern-matching on strings.
|
| |
Massively Parallel Algorithms for Finding Well-Connected 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] |
| |
The Minrank of Random Graphs,
with Alexander Golovnev and Oded Regev,
IEEE Transactions on Information Theory (preliminary version in RANDOM'17) |
[ECCC] |
| |
Amortized Dynamic Cell-Probe Lower Bounds from Four-Party 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 2-party problem of computing approximate
fixed-points 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 5-approximation 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 information-theoretic 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 n-bidder games requires Omega(log log n) rounds of
communication, the first super-constant lower bound for general (unbounded-round) 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 approximately-optimal Nash equilibrium in 2-party games under the
ETH conjecture, using a novel adaptation of the ``birthday repetition" technique in 2-prover ``free games" [AIM'13].
|
| |
Welfare and Revenue Guarantees of Competitive Bundling Equilibrium,
with Shahar Dobzinski, Michal Feldman and Inbal Talgam-Cohen,
|
| |
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 direct-product theorem for general two-party communication complexity. This black-box hardness
amplification theorem was key to many subsequent lower bounds in complexity theory and streaming.
|
| |
Direct Product via Round-Preserving 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 0-error 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
two-party 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 self-reduction 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 6998-004)
(Columbia, Fall '20)
[webepage]. |
| |
|
CS Theory (COMS 3261)
(Columbia, Fall '19)
[webepage]. |
| |
|
Advanced Data Structures (COMSE 6998-008)
(Columbia, Spring '19)
[webepage]. |
| |
|
Introduction to Complexity Theory (COMSE 4236) (Columbia, Fall '18) |
| |
|
Information Theory In TCS (COMSE 6998) (Columbia, Fall '17)|
[webepage]. |
| |
|
Data-Structure Lower Bounds Reading
Group (Columbia)|
[webepage]. |
|
|
