Omri Weinstein

Sorrachai Yingchareonthawornchai

CoRR, 2024

Hardness Amplification for Dynamic Binary Search Trees.

[BibT_eX]

[DOI]

Victor Lecomte

Sorrachai Yingchareonthawornchai

Proceedings of the 35th International Symposium on Algorithms and Computation, 2024

2023

A Faster Interior-Point Method for Sum-of-Squares Optimization.

[BibT_eX]

[DOI]

Bento Natura

Algorithmica, September, 2023

Infinite Lewis Weights in Spectral Graph Theory.

[BibT_eX]

[DOI]

Amit Suliman

CoRR, 2023

The Complexity of Dynamic Least-Squares Regression.

[BibT_eX]

[DOI]

Binghui Peng

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

Quartic Samples Suffice for Fourier Interpolation.

[BibT_eX]

[DOI]

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

2022

Dynamic Kernel Sparsifiers.

[BibT_eX]

[DOI]

CoRR, 2022

Discrepancy Minimization in Input-Sparsity Time.

[BibT_eX]

[DOI]

Yichuan Deng

Zhao Song

CoRR, 2022

Training Overparametrized Neural Networks in Sublinear Time.

[BibT_eX]

[DOI]

CoRR, 2022

Sparse Fourier Transform over Lattices: A Unified Approach to Signal Reconstruction.

[BibT_eX]

[DOI]

CoRR, 2022

A Dynamic Fast Gaussian Transform.

[BibT_eX]

[DOI]

CoRR, 2022

Dynamic Least-Squares Regression.

[BibT_eX]

[DOI]

Binghui Peng

CoRR, 2022

Fast Distance Oracles for Any Symmetric Norm.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 2022

2021

A faster algorithm for solving general LPs.

[BibT_eX]

[DOI]

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

Training (Overparametrized) Neural Networks in Near-Linear Time.

[BibT_eX]

[DOI]

Proceedings of the 12th Innovations in Theoretical Computer Science Conference, 2021

2020

Distributed Signaling Games.

[BibT_eX]

[DOI]

Moran Feldman

Moshe Tennenholtz

ACM Trans. Economics and Comput., 2020

Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds.

[BibT_eX]

[DOI]

Kasper Green Larsen

Huacheng Yu

SIAM J. Comput., 2020

Faster Dynamic Matrix Inverse for Faster LPs.

[BibT_eX]

[DOI]

CoRR, 2020

How to Store a Random Walk.

[BibT_eX]

[DOI]

Emanuele Viola

Huacheng Yu

Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

An Adaptive Step Toward the Multiphase Conjecture.

[BibT_eX]

[DOI]

Young Kun-Ko

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

Settling the Relationship Between Wilber's Bounds for Dynamic Optimality.

[BibT_eX]

[DOI]

Victor Lecomte

Proceedings of the 28th Annual European Symposium on Algorithms, 2020

2019

Lower Bounds for Oblivious Near-Neighbor Search.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2019

An Adaptive Step Toward the Multiphase Conjecture.

[BibT_eX]

[DOI]

Young Ko

Electron. Colloquium Comput. Complex., 2019

Massively Parallel Algorithms for Finding Well-Connected Components in Sparse Graphs.

[BibT_eX]

[DOI]

Sepehr Assadi

Xiaorui Sun

Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, 2019

2018

Local Decodability of the Burrows-Wheeler Transform.

[BibT_eX]

[DOI]

Sandip Sinha

Electron. Colloquium Comput. Complex., 2018

Static Data Structure Lower Bounds Imply Rigidity.

[BibT_eX]

[DOI]

Zeev Dvir

Alexander Golovnev

Electron. Colloquium Comput. Complex., 2018

2017

Toward Better Formula Lower Bounds: The Composition of a Function and a Universal Relation.

[BibT_eX]

[DOI]

SIAM J. Comput., 2017

Coding with asymmetric prior knowledge.

[BibT_eX]

[DOI]

CoRR, 2017

2016

Amortized Dynamic Cell-Probe Lower Bounds from Four-Party Communication.

[BibT_eX]

[DOI]

Huacheng Yu

Electron. Colloquium Comput. Complex., 2016

On the Communication Complexity of Approximate Fixed Points.

[BibT_eX]

[DOI]

Tim Roughgarden

Electron. Colloquium Comput. Complex., 2016

The Minrank of Random Graphs.

[BibT_eX]

[DOI]

Alexander Golovnev

Oded Regev

Electron. Colloquium Comput. Complex., 2016

An improved upper bound for the most informative boolean function conjecture.

[BibT_eX]

[DOI]

Or Ordentlich

Ofer Shayevitz

Proceedings of the IEEE International Symposium on Information Theory, 2016

2015

Interactive Information Complexity and Applications

[BibT_eX]

[DOI]

PhD thesis, 2015

Information Complexity and the Quest for Interactive Compression.

[BibT_eX]

[DOI]

SIGACT News, 2015

The Simultaneous Communication of Disjointness with Applications to Data Streams.

[BibT_eX]

[DOI]

David P. Woodruff

Electron. Colloquium Comput. Complex., 2015

Dictatorship is the Most Informative Balanced Function at the Extremes.

[BibT_eX]

[DOI]

Or Ordentlich

Ofer Shayevitz

Electron. Colloquium Comput. Complex., 2015

ETH Hardness for Densest-k-Subgraph with Perfect Completeness.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2015

Welfare Maximization with Limited Interaction.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2015

Information Complexity and the Quest for Interactive Compression (A Survey).

[BibT_eX]

[DOI]

CoRR, 2015

ETH Hardness for Densest-$k$-Subgraph with Perfect Completeness.

[BibT_eX]

[DOI]

CoRR, 2015

Welfare and Revenue Guarantees for Competitive Bundling Equilibrium.

[BibT_eX]

[DOI]

Proceedings of the Web and Internet Economics - 11th International Conference, 2015

An Interactive Information Odometer and Applications.

[BibT_eX]

[DOI]

Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

Approximating the best Nash Equilibrium in no(log n)-time breaks the Exponential Time Hypothesis.

[BibT_eX]

[DOI]

Young Kun-Ko

Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

2014

An Interactive Information Odometer with Applications.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2014

Approximating the best Nash Equilibrium in no(log n)-time breaks the Exponential Time Hypothesis.

[BibT_eX]

[DOI]

Young Kun-Ko

Electron. Colloquium Comput. Complex., 2014

Display Advertising with Information Mediators.

[BibT_eX]

[DOI]

Moran Feldman

Moshe Tennenholtz

CoRR, 2014

2013

Toward Better Formula Lower Bounds: An Information Complexity Approach to the KRW Composition Conjecture.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2013

Direct product via round-preserving compression.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2013

2012

Approximating the Influence of Monotone Boolean Functions in O(√n) Query Complexity.

[BibT_eX]

[DOI]

ACM Trans. Comput. Theory, 2012

Direct Products in Communication Complexity.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2012

Information lower bounds via self-reducibility.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2012

From Information to Exact Communication.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2012

Unsupervised SVMs: On the Complexity of the Furthest Hyperplane Problem.

[BibT_eX]

[DOI]

Proceedings of the COLT 2012, 2012

2011

A discrepancy lower bound for information complexity.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2011

On the Furthest Hyperplane Problem and Maximal Margin Clustering

[BibT_eX]

[DOI]

Edo Liberty

Shachar Lovett