Omri Weinstein

CoRR, October, 2025

Proof of Work With External Utilities.

[BibT_eX]

[DOI]

Yogev Bar-On

Ilan Komargodski

CoRR, May, 2025

Changing Base Without Losing Pace: A GPU-Efficient Alternative to MatMul in DNNs.

[BibT_eX]

[DOI]

Nir Ailon

Akhiad Bercovich

CoRR, March, 2025

Proofs of Useful Work from Arbitrary Matrix Multiplication.

[BibT_eX]

[DOI]

Ilan Komargodski

Itamar Schen

IACR Cryptol. ePrint Arch., 2025

Approximating the Held-Karp Bound for Metric TSP in Nearly Linear Work and Polylogarithmic Depth.

[BibT_eX]

[DOI]

Zhuan Khye Koh

Sorrachai Yingchareonthawornchai

Proceedings of the 57th Annual ACM Symposium on Theory of Computing, 2025

A Framework for Building Data Structures from Communication Protocols.

[BibT_eX]

[DOI]

Alexandr Andoni

Proceedings of the 57th Annual ACM Symposium on Theory of Computing, 2025

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

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

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

[BibT_eX]

[DOI]

Bento Natura

Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, 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

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

Lower Bounds for Oblivious Near-Neighbor Search.

[BibT_eX]

[DOI]

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

Polynomial Data Structure Lower Bounds in the Group Model.

[BibT_eX]

[DOI]

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

An Adaptive Step Toward the Multiphase Conjecture.

[BibT_eX]

[DOI]

Young Ko

Electron. Colloquium Comput. Complex., 2019

Local decodability of the Burrows-Wheeler transform.

[BibT_eX]

[DOI]

Sandip Sinha

Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

Static data structure lower bounds imply rigidity.

[BibT_eX]

[DOI]

Zeev Dvir

Alexander Golovnev

Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 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

Crossing the logarithmic barrier for dynamic Boolean data structure lower bounds.

[BibT_eX]

[DOI]

Kasper Green Larsen

Huacheng Yu

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 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

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

[BibT_eX]

[DOI]

Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

The Minrank of Random Graphs.

[BibT_eX]

[DOI]

Alexander Golovnev

Oded Regev

Proceedings of the Approximation, 2017

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

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

[BibT_eX]

[DOI]

Huacheng Yu

Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science, 2016

On the Communication Complexity of Approximate Fixed Points.

[BibT_eX]

[DOI]

Tim Roughgarden

Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science, 2016

Distributed Signaling Games.

[BibT_eX]

[DOI]

Moran Feldman

Moshe Tennenholtz

Proceedings of the 24th Annual European Symposium on Algorithms, 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

Dictatorship is the Most Informative Balanced Function at the Extremes.

[BibT_eX]

[DOI]

Or Ordentlich

Ofer Shayevitz

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

The Simultaneous Communication of Disjointness with Applications to Data Streams.

[BibT_eX]

[DOI]

David P. Woodruff

Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, 2015

Welfare Maximization with Limited Interaction.

[BibT_eX]

[DOI]

Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, 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

Toward better formula lower bounds: an information complexity approach to the KRW composition conjecture.

[BibT_eX]

[DOI]

Proceedings of the Symposium on Theory of Computing, 2014

2013

From information to exact communication.

[BibT_eX]

[DOI]

Proceedings of the Symposium on Theory of Computing Conference, 2013

Direct Product via Round-Preserving Compression.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages, and Programming - 40th International Colloquium, 2013

Direct Products in Communication Complexity.

[BibT_eX]

[DOI]

Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, 2013

Information Lower Bounds via Self-reducibility.

[BibT_eX]

[DOI]

Proceedings of the Computer Science - Theory and Applications, 2013

2012

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

[BibT_eX]

[DOI]

ACM Trans. Comput. Theory, 2012

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

[BibT_eX]

[DOI]

Proceedings of the COLT 2012, 2012

A Discrepancy Lower Bound for Information Complexity.

[BibT_eX]

[DOI]

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2012

2011

On the Furthest Hyperplane Problem and Maximal Margin Clustering

[BibT_eX]

[DOI]

Edo Liberty

Shachar Lovett