Pravesh K Kothari
@praveshkkothari.bsky.social
Assistant Professor @PrincetonCS
Research: Theoretical Computer Science, Optimization, Algorithmic Statistics.
Research: Theoretical Computer Science, Optimization, Algorithmic Statistics.
Recommend this very nice exposition by Arsen Vasilyan on testable learning. I haven't thought about it since reading the inspirational Rubinfeld-Vasilyan paper and writing "moment-matching" follow-up paper with Adam Klivans and Arvind Gollakota. But perhaps it's time to look at it again. :)
New post on the Learning Theory Alliance blog, by Arsen Vasilyan. This covers the recently introduced testable learning paradigm of Rubinfeld and Vasilyan, from their STOC 2023 paper. A great chance to catch up on all the exciting work that's happened in this area!
www.let-all.com/blog/2025/07...
www.let-all.com/blog/2025/07...
July 22, 2025 at 6:22 PM
Recommend this very nice exposition by Arsen Vasilyan on testable learning. I haven't thought about it since reading the inspirational Rubinfeld-Vasilyan paper and writing "moment-matching" follow-up paper with Adam Klivans and Arvind Gollakota. But perhaps it's time to look at it again. :)
If you want to check out a less technical version of the first applications of Kikuchi graphs, check out our new CACM Research Highlight cacm.acm.org/research-hig...
and technical perspective by Uri Feige who was the early pioneer of the problems and models cacm.acm.org/research-hig...
and technical perspective by Uri Feige who was the early pioneer of the problems and models cacm.acm.org/research-hig...
New Spectral Algorithms for Refuting Smoothed k-SAT – Communications of the ACM
cacm.acm.org
March 14, 2025 at 2:31 AM
If you want to check out a less technical version of the first applications of Kikuchi graphs, check out our new CACM Research Highlight cacm.acm.org/research-hig...
and technical perspective by Uri Feige who was the early pioneer of the problems and models cacm.acm.org/research-hig...
and technical perspective by Uri Feige who was the early pioneer of the problems and models cacm.acm.org/research-hig...
I taught this very cool algorithm (due to Funda Ergün, Sampath Kannan, S. Ravi Kumar, Ronitt Rubinfeld, and Mahesh Viswanathan) in a one-lecture intro to property testing in my Advanced Algorithm class. Neat, teachable idea!
It's the weekend, time to finally relax! Maybe with a small 🧩?
You are given an array of n (distinct) numbers, with the promise that it is either sorted or *significantly* unsorted: to sort it, at least 10% of the entries must be moved. Which case is it?
Give a (randomized) algo for that. #TCSSky
You are given an array of n (distinct) numbers, with the promise that it is either sorted or *significantly* unsorted: to sort it, at least 10% of the entries must be moved. Which case is it?
Give a (randomized) algo for that. #TCSSky
December 15, 2024 at 5:05 AM
I taught this very cool algorithm (due to Funda Ergün, Sampath Kannan, S. Ravi Kumar, Ronitt Rubinfeld, and Mahesh Viswanathan) in a one-lecture intro to property testing in my Advanced Algorithm class. Neat, teachable idea!
Reposted by Pravesh K Kothari
A reminder about NY Theory Day in a week! Fri Dec 6th! Talks by Amir Abboud, Sanjeev Khanna, Rotem Oshman, and Ron Rothblum! At NYU Tandon!
sites.google.com/view/nyctheo...
Registration is free, but please register for building access.
See you all there!
sites.google.com/view/nyctheo...
Registration is free, but please register for building access.
See you all there!
Home
About
The New York Theory Day is a workshop aimed to bring together the theoretical computer science community in the New York metropolitan area for a day of interaction and discussion. The Theory Da...
sites.google.com
November 30, 2024 at 5:04 PM
A reminder about NY Theory Day in a week! Fri Dec 6th! Talks by Amir Abboud, Sanjeev Khanna, Rotem Oshman, and Ron Rothblum! At NYU Tandon!
sites.google.com/view/nyctheo...
Registration is free, but please register for building access.
See you all there!
sites.google.com/view/nyctheo...
Registration is free, but please register for building access.
See you all there!
In fact, the principles of TOC should be taught not just to our majors but to college students at large. Back at CMU, Anil Ada and I created a course just for that. www.computational-lens.com
November 28, 2024 at 1:06 PM
In fact, the principles of TOC should be taught not just to our majors but to college students at large. Back at CMU, Anil Ada and I created a course just for that. www.computational-lens.com
An intro to TOC class should indeed focus on "useful" ideas. But "useful" is often incredibly narrowlt defined. TOC is more way than its theorems, it's a way of modeling & thinking about problems that is applicable much more broadly across sciences & engg. Wigderson argues better than I could.
My take—certainly how I approach both PL and formal methods—is that we should focus on "the other 90%". There's 10% of the class who are just like us; you can teach them almost *anything*, and they'll get the rest in grad school. But those methods don't work, and even turn off, the 90%. ↵
November 28, 2024 at 1:04 PM
An intro to TOC class should indeed focus on "useful" ideas. But "useful" is often incredibly narrowlt defined. TOC is more way than its theorems, it's a way of modeling & thinking about problems that is applicable much more broadly across sciences & engg. Wigderson argues better than I could.
Conventional wisdom says that a d^k time/sample bound is necessary for clustering non spherical Gaussian Mixtures. But there's essentially only 1 hard family known -- parallel pancakes. It turns out that new algo ideas allow significant improvement for mixtures that steer clear of parallel pancakes.
In arxiv.org/abs/2411.12438 we obtain new results for clustering mixtures of non-spherical Gaussians! Highlight: poly(d) * f(w_min) algorithm for mixtures of arbitrary zero-mean TVD-separated Gaussians. W/ Prashanti Anderson, Mitali Bafna, @praveshkkothari.bsky.social, and David Steurer.
Dimension Reduction via Sum-of-Squares and Improved Clustering Algorithms for Non-Spherical Mixtures
We develop a new approach for clustering non-spherical (i.e., arbitrary component covariances) Gaussian mixture models via a subroutine, based on the sum-of-squares method, that finds a low-dimensiona...
arxiv.org
November 26, 2024 at 11:42 AM
Conventional wisdom says that a d^k time/sample bound is necessary for clustering non spherical Gaussian Mixtures. But there's essentially only 1 hard family known -- parallel pancakes. It turns out that new algo ideas allow significant improvement for mixtures that steer clear of parallel pancakes.
Reposted by Pravesh K Kothari
I’ve just attended a Bourbaki seminar for the first time, given by Michael Harris. Full marks to him for starting with “un moment de silence pour les enfants de Gaza”.
The reason I’m here is that later Yuval Wigderson will be talking about last year’s big breakthrough on Ramsey’s theorem.
The reason I’m here is that later Yuval Wigderson will be talking about last year’s big breakthrough on Ramsey’s theorem.
November 23, 2024 at 10:16 AM
I’ve just attended a Bourbaki seminar for the first time, given by Michael Harris. Full marks to him for starting with “un moment de silence pour les enfants de Gaza”.
The reason I’m here is that later Yuval Wigderson will be talking about last year’s big breakthrough on Ramsey’s theorem.
The reason I’m here is that later Yuval Wigderson will be talking about last year’s big breakthrough on Ramsey’s theorem.
Reposted by Pravesh K Kothari
Recorded an extended version of my MFCS'24 invited talk. The talk presents my personal experiences in entering learning theory with a TCS background. The target audience is mostly TCS researchers. Hope some of you might enjoy it.
youtu.be/ZYe2mITwww4
youtu.be/ZYe2mITwww4
From Theoretical Computer Science to Learning Theory
YouTube video by Kasper Green Larsen
youtu.be
November 22, 2024 at 12:05 PM
Recorded an extended version of my MFCS'24 invited talk. The talk presents my personal experiences in entering learning theory with a TCS background. The target audience is mostly TCS researchers. Hope some of you might enjoy it.
youtu.be/ZYe2mITwww4
youtu.be/ZYe2mITwww4