Jeff's thesis step by step resolved the open question left by the sos lower bound for planted clique (poetically, part of my PhD thesis): bounding the spectra of low degree matrix functions of ultra sparse random graphs (his theses shows applications far beyond sos lower bounds)
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...
I taught the version you wrote. To be honest, I taught whatever appeared in these great notes by Sepehr and assumed that it was the algorithm in the paper. I'd trust you on the history of this algorithm, I'm only masquerading as a property tester. ;-)
sepehr.assadi.info/courses/cs51...
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!
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!
FWIW, my goal in bringing up Avi's excellent book and the last chapter that I quoted in particular was to clarify that "useful" as used in Shriram's post could/should be interpreted more broadly.
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.
Parallel pancakes, or, a stack of pancakes by another name?
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.
sounds like a setting that must have a phase transition... :-)
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.
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
