research
∙
03/30/2023
Sum-of-Squares Lower Bounds for Densest k-Subgraph
Given a graph and an integer k, Densest k-Subgraph is the algorithmic ta...
share
research
∙
12/05/2022
Benchmarking Offline Reinforcement Learning Algorithms for E-Commerce Order Fraud Evaluation
Amazon and other e-commerce sites must employ mechanisms to protect thei...
research
∙
11/02/2022
Exact Completeness of LP Hierarchies for Linear Codes
Determining the maximum size A_2(n,d) of a binary code of blocklength n ...
research
∙
10/06/2022
Random Max-CSPs Inherit Algorithmic Hardness from Spin Glasses
We study random constraint satisfaction problems (CSPs) in the unsatisfi...
research
∙
02/02/2022
Unified Scaling Laws for Routed Language Models
The performance of a language model has been shown to be effectively mod...
research
∙
12/16/2021
A Complete Linear Programming Hierarchy for Linear Codes
A longstanding open problem in coding theory is to determine the best (a...
research
∙
12/08/2021
Improving language models by retrieving from trillions of tokens
We enhance auto-regressive language models by conditioning on document c...
research
∙
11/17/2021
Sum-of-Squares Lower Bounds for Sparse Independent Set
The Sum-of-Squares (SoS) hierarchy of semidefinite programs is a powerfu...
research
∙
07/01/2021
Almost-Orthogonal Bases for Inner Product Polynomials
In this paper, we consider low-degree polynomials of inner products betw...
research
∙
09/03/2020
Sum-of-Squares Lower Bounds for Sherrington-Kirkpatrick via Planted Affine Planes
The Sum-of-Squares (SoS) hierarchy is a semi-definite programming meta-a...
research
∙
07/11/2019
Spherical Discrepancy Minimization and Algorithmic Lower Bounds for Covering the Sphere
Inspired by the boolean discrepancy problem, we study the following opti...
research
∙
02/01/2019
TF-Replicator: Distributed Machine Learning for Researchers
We describe TF-Replicator, a framework for distributed machine learning ...
research
∙
05/16/2017