Enric Boix-Adserà

CoRR, 2024

2023

Polynomial-time algorithms for multimarginal optimal transport problems with structure.

[BibT_eX]

[DOI]

Math. Program., May, 2023

PROPANE: Prompt design as an inverse problem.

[BibT_eX]

[DOI]

CoRR, 2023

When can transformers reason with abstract symbols?

[BibT_eX]

[DOI]

CoRR, 2023

The NTK approximation is valid for longer than you think.

[BibT_eX]

[DOI]

Etai Littwin

CoRR, 2023

Transformers learn through gradual rank increase.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023

SGD learning on neural networks: leap complexity and saddle-to-saddle dynamics.

[BibT_eX]

[DOI]

Enric Boix Adserà

Theodor Misiakiewicz

Proceedings of the Thirty Sixth Annual Conference on Learning Theory, 2023

2022

Wasserstein Barycenters Are NP-Hard to Compute.

[BibT_eX]

[DOI]

SIAM J. Math. Data Sci., 2022

GULP: a prediction-based metric between representations.

[BibT_eX]

[DOI]

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

On the non-universality of deep learning: quantifying the cost of symmetry.

[BibT_eX]

[DOI]

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

The merged-staircase property: a necessary and nearly sufficient condition for SGD learning of sparse functions on two-layer neural networks.

[BibT_eX]

[DOI]

Enric Boix Adserà

Theodor Misiakiewicz

Proceedings of the Conference on Learning Theory, 2-5 July 2022, London, UK., 2022

2021

Wasserstein barycenters can be computed in polynomial time in fixed dimension.

[BibT_eX]

[DOI]

J. Mach. Learn. Res., 2021

The multiplayer Colonel Blotto game.

[BibT_eX]

[DOI]

Benjamin L. Edelman

Siddhartha Jayanti

Games Econ. Behav., 2021

Hardness results for Multimarginal Optimal Transport problems.

[BibT_eX]

[DOI]

Discret. Optim., 2021

The staircase property: How hierarchical structure can guide deep learning.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, 2021

Chow-Liu++: Optimal Prediction-Centric Learning of Tree Ising Models.

[BibT_eX]

[DOI]

Guy Bresler

Frederic Koehler

Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021

2020

Graph Powering and Spectral Robustness.

[BibT_eX]

[DOI]

SIAM J. Math. Data Sci., 2020

High-precision Wasserstein barycenters in polynomial time.

[BibT_eX]

[DOI]

CoRR, 2020

2019

Approximating the Determinant of Well-Conditioned Matrices by Shallow Circuits.

[BibT_eX]

[DOI]

Lior Eldar

Saeed Mehraban

CoRR, 2019

Randomized Concurrent Set Union and Generalized Wake-Up.

[BibT_eX]

[DOI]

Siddhartha V. Jayanti

Robert E. Tarjan

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

Sample Efficient Active Learning of Causal Trees.

[BibT_eX]

[DOI]

Kristjan H. Greenewald

Dmitriy Katz

Karthikeyan Shanmugam

Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019

Subadditivity Beyond Trees and the Chi-Squared Mutual Information.

[BibT_eX]

[DOI]

Enric Boix Adserà

Proceedings of the IEEE International Symposium on Information Theory, 2019

The Average-Case Complexity of Counting Cliques in Erdős-Rényi Hypergraphs.

[BibT_eX]

[DOI]

Matthew S. Brennan

Guy Bresler

Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science, 2019

2018

An Information-Percolation Bound for Spin Synchronization on General Graphs.

[BibT_eX]

[DOI]