illustration of intersecting lines with various shapes at the connecting points signifying algorithms on a green gradient background

Algorithms

Current selections

Sort by: Most recent

Clear selections

Publication

Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimation

Ilias Diakonikolas, Daniel M. Kane, Daniel Kongsgaard, Jerry Li, Kevin Tian

STOC 2022 | June 2022

Publication

Two Coupled Rejection Metrics Can Tell Adversarial Examples Apart

Tianyu Pang, Huishuai Zhang, Di He, Yinpeng Dong, Hang Su, Wei Chen, Jun Zhu, Tie-Yan Liu, Tie-Yan Liu

CVPR 2022 | June 2022

Publication

Clustering Mixtures with Almost Optimal Separation in Polynomial Time

Jerry Li, Allen Liu

STOC 2022 | June 2022

Publication

The Optimal Error Resilience of Interactive Communication Over Binary Channels

Meghal Gupta, Rachel Yun Zhang

STOC 2022 | June 2022

Publication

Interactive Error Correcting Codes Over Binary Erasure Channels Resilient to > 1/2 Adversarial Corruption

Meghal Gupta, Yael Tauman Kalai, Rachel Zhang

STOC 2022 | June 2022

Publication

Online Edge Coloring via Tree Recurrences and Correlation Decay

Janardhan (Jana) Kulkarni, Yang Liu, Yang Liu, Yang Liu, Ashwin Sah, Mehtaab Sawhney, Jakub Tarnawski

STOC 2022 | June 2022

Microsoft Research Blog

Azure Quantum innovation: Efficient error correction of topological qubits with Floquet codes

May 5, 2022 | Bela Bauer, Matthew Hastings, Jeongwan Haah

Technological innovation that enables scaling of quantum computing underpins the Microsoft Azure Quantum (opens in new tab) program. In March of this year, we announced (opens in new tab) our demonstration of the underlying physics…

Qubits arranged in a square array on a two-dimensional surface. Measurements are done on the qubits in a sequence of checks, shown as a repeating pattern of three steps. In each step, one measures a check on each pair of neighboring qubits, shown as a line connecting those qubits, with the lines moving in a repeating pattern over the three steps.

Publication

Lower Bounds for Non-Convex Stochastic Optimization

Yossi Arjevani, Yair Carmon, John C. Duchi, Dylan Foster, Nathan Srebro, Blake E. Woodworth

Mathematical Programming | May 2022

Publication

Adaptive Greedy versus Non-Adaptive Greedy for Influence Maximization

Wei Chen, Binghui Peng, Grant Schoenebeck, Biaoshuai Tao

Journal of Artificial Intelligence Research | May 2022, Vol 74: pp. 303-351

Publication

Generalization Bounds for Data-Driven Numerical Linear Algebra

Peter Bartlett, Piotr Indyk, Tal Wagner

May 2022