Search for tag: "arc colloquium"

Yin Tat Lee - Solving Linear Programs in the Current Matrix Multiplication Time

We show how to solve linear programs with accuracy epsilon in time n^{omega+o(1)} log(1/epsilon) where omega~2.3728639 is the current matrix multiplication constant. This hits a natural barrier of…

From  Kathryn Gentilello 2 Months ago 9 views 0  

Will Perkins - Abstract polymer models, the cluster expansion, and applications

I will give two lectures introducing abstract polymer models and the cluster expansion from statistical physics. I will describe some of the original applications of these tools in statistical…

From  Kathryn Gentilello 2 Months ago 1 views 0  

Ola Svensson - Lecture 2: Different approaches for asymmetric TSP

The traveling salesman problem is one of the most fundamental optimization problems. Given n cities and pairwise distances, it is the problem of finding a tour of minimum distance that visits each…

From  Kathryn Gentilello 3 Months ago 6 views 0  

Ola Svensson - Lecture 3: A constant-factor approximation algorithm for asymmetric TSP

The traveling salesman problem is one of the most fundamental optimization problems. Given n cities and pairwise distances, it is the problem of finding a tour of minimum distance that visits each…

From  Kathryn Gentilello 3 Months ago 13 views 0  

Kunal Talwar - Amplification Theorems for Differentially Private Machine Learning

A rigorous foundational approach to private data analysis has emerged in theoretical computer science in the last decade, with differential privacy and its close variants playing a central role. We…

From  Kathryn Gentilello 4 Months ago 17 views 0  

Will Perkins - Algorithmic Pirogov-Sinai theory

We develop efficient algorithms to approximate the partition function and sample from the hard-core and Potts models on lattices at sufficiently low temperatures in the phase coexistence regime. In…

From  Kathryn Gentilello 9 Months ago 12 views 0  

Sampath Kannan - Fairness in Algorithmic Decision Making

In this talk we survey some formulations of fairness requirements for decision making under uncertainty. We then discuss results from 3 recent papers:1) Treating individuals fairly is not in conflict…

From  Kathryn Gentilello 9 Months ago 22 views 0  

Lap Chi Lau - The Paulsen problem, continuous operator scaling, and smoothed analysis

The Paulsen problem is a basic open problem in operator theory. We define a continuous version of the operator scaling algorithm to solve this problem. A key step is to show that the continuous…

From  Kathryn Gentilello 10 Months ago 16 views 0  

Mary Wootters - Improved Decoding of Folded Reed-Solomon and Multiplicity Codes

List-decoding is an important primitive in the theory of error correcting codes, and it has long been a goal to obtain explicit constructions of capacity-achieving, efficiently list-decodable codes. …

From  Kathryn Gentilello 10 Months ago 20 views 0  

Tselil Schramm - (Nearly) Efficient Algorithms for the Graph Matching Problem in Correlated Random Graphs

The Graph Matching problem is a robust version of the Graph Isomorphism problem: given two not-necessarily-isomorphic graphs, the goal is to find a permutation of the vertices which maximizes the…

From  Kathryn Gentilello 10 Months ago 46 views 0  

Anand Louis - On the complexity of clustering problems

Euclidean k-means clustering, a problem having numerous applications, is NP-hard in the worst case but often solved efficiently in practice using simple heuristics. A quest for understanding the…

From  Kathryn Gentilello 11 Months ago 42 views 0  

Entropy, Log-Concavity, and a Deterministic Approximation Algorithm for Counting Bases of Matroids - Nima Anari

We give a deterministic 2^O(rank) approximation algorithm to count the number of bases of a given matroid and the number of common bases of any two matroids. Based on a lower bound of Azar et al.,…

From  Kathryn Gentilello A year ago 32 views 0  

The Query Complexity of Graph Isomorphism: Bypassing Distribution Testing Lower Bounds - Xiaorui Sun

We study the edge query complexity of graph isomorphism in the property testing model for dense graphs. We give an algorithm that makes n^{1+o(1)} queries, improving on the previous best bound of…

From  Kathryn Gentilello A year ago 53 views 0  

An almost-linear time algorithm for uniform random spanning tree generation - Aaron Schild

We give an $m^{1+o(1)}\beta^{o(1)}$-time algorithm for generating uniformly random spanning trees in weighted graphs with max-to-min weight ratio $\beta$. In the process, we illustrate how…

From  Kathryn Gentilello A year ago 32 views 0  

Black Holes, Firewalls, and the Limits of Quantum Computers - Scott Aaronson

Quantum computers are proposed devices that would exploit quantum mechanics to solve certain specific problems dramatically faster than we know how to solve them with today's computers. In the…

From  Kathryn Gentilello A year ago 13 views 0  

A characterization of $L_p$ mixing, cutoff and hypercontractivity via maximal inequalities and hitting times - Jonathan Hermon

There are several works characterizing the total-variation mixing time of a reversible Markov chain in term of natural probabilistic concepts such as stopping times and hitting times. In contrast,…

From  Kathryn Gentilello A year ago 19 views 0