Sotabase

Career

· Assistant Professor, Columbia University2017–
· Simons Society Junior Fellow Postdoc, Courant Institute (NYU)2015–
· PhD in Theoretical Computer Science, Princeton University2010–
· B.Sc in Mathematics and Computer Science, Tel Aviv University2006–

Publications (62)

Preface
Annual Conference Computational Learning Theory · 2012
492
cited
Faster Dynamic Matrix Inverse for Faster LPs
arXiv.org · 2020
112
cited
Direct Products in Communication Complexity
IEEE Annual Symposium on Foundations of Computer Science · 2013
85
cited
From information to exact communication
Symposium on the Theory of Computing · 2013
83
cited
Inapproximabilty of Densest κ-Subgraph from Average Case Hardness
2011
82
cited
Training (Overparametrized) Neural Networks in Near-Linear Time
Information Technology Convergence and Services · 2020
82
cited
A faster algorithm for solving general LPs
Symposium on the Theory of Computing · 2021
74
cited
Approximating the best Nash Equilibrium in no(log n)-time breaks the Exponential Time Hypothesis
Electron. Colloquium Comput. Complex. · 2015
67
cited
Massively Parallel Algorithms for Finding Well-Connected Components in Sparse Graphs
ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing · 2018
59
cited
ETH Hardness for Densest-k-Subgraph with Perfect Completeness
ACM-SIAM Symposium on Discrete Algorithms · 2015
57
cited
A Discrepancy Lower Bound for Information Complexity
Algorithmica · 2011
49
cited
Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds
Information Theory and Applications Workshop · 2017
41
cited
Toward better formula lower bounds: an information complexity approach to the KRW composition conjecture
Symposium on the Theory of Computing · 2014
40
cited
Direct Product via Round-Preserving Compression
International Colloquium on Automata, Languages and Programming · 2013
39
cited
Welfare Maximization with Limited Interaction
IEEE Annual Symposium on Foundations of Computer Science · 2015
33
cited
Static data structure lower bounds imply rigidity
Electron. Colloquium Comput. Complex. · 2018
29
cited
Training Overparametrized Neural Networks in Sublinear Time
arXiv.org · 2022
29
cited
The Minrank of Random Graphs
IEEE Transactions on Information Theory · 2016
28
cited
An Interactive Information Odometer and Applications
Symposium on the Theory of Computing · 2015
26
cited
Information Lower Bounds via Self-Reducibility
Theory of Computing Systems · 2013
26
cited
Sotabase