Gautam Kamath
@gautamkamath.com
Assistant Prof of CS at the University of Waterloo, Faculty and Canada CIFAR AI Chair at the Vector Institute. Joining NYU Courant in September 2026. Co-EiC of TMLR. My group is The Salon. Privacy, robustness, machine learning.
http://www.gautamkamath.com
http://www.gautamkamath.com
We were then able to show that the domination number of this graph was O(k^1.5), leading to a non-interactive algorithm with the same sample complexity! Recall this is better than the naive O(k^2) sample algorithm, and "halfway" to the lower bound of Omega(k). 9/n
November 28, 2025 at 7:03 PM
We were then able to show that the domination number of this graph was O(k^1.5), leading to a non-interactive algorithm with the same sample complexity! Recall this is better than the naive O(k^2) sample algorithm, and "halfway" to the lower bound of Omega(k). 9/n
Until my student Matt Regehr came along! He came up with a brilliant generalization of the minimum distance estimator! With this framework, he reduced the problem to analyzing the domination number of a particular graph structure. 8/n
November 28, 2025 at 7:03 PM
Until my student Matt Regehr came along! He came up with a brilliant generalization of the minimum distance estimator! With this framework, he reduced the problem to analyzing the domination number of a particular graph structure. 8/n
But what if you consider the stronger constraint of local differential privacy? The bad news: a construction of Duchi and Rogers implies that you need Omega(k) samples. Exponentially more than in the centrally private case! 5/n
November 28, 2025 at 7:03 PM
But what if you consider the stronger constraint of local differential privacy? The bad news: a construction of Duchi and Rogers implies that you need Omega(k) samples. Exponentially more than in the centrally private case! 5/n
Hypothesis selection is the following problem: given n samples from a probability distribution, and k hypothesis distributions, how do you learn which one is (nearly) the closest? 2/n
November 28, 2025 at 7:03 PM
Hypothesis selection is the following problem: given n samples from a probability distribution, and k hypothesis distributions, how do you learn which one is (nearly) the closest? 2/n
🧵New paper, at #NeurIPS2025: "Query-Efficient Locally Private Hypothesis Selection via the Scheffe Graph" with Alireza F. Pour, Matthew Regehr (@matt19234.bsky.social), David P. Woodruff
Breaks the O(k^2) barrier I've been stuck on since 2019! arxiv.org/abs/2509.16180 1/n
Breaks the O(k^2) barrier I've been stuck on since 2019! arxiv.org/abs/2509.16180 1/n
November 28, 2025 at 7:03 PM
🧵New paper, at #NeurIPS2025: "Query-Efficient Locally Private Hypothesis Selection via the Scheffe Graph" with Alireza F. Pour, Matthew Regehr (@matt19234.bsky.social), David P. Woodruff
Breaks the O(k^2) barrier I've been stuck on since 2019! arxiv.org/abs/2509.16180 1/n
Breaks the O(k^2) barrier I've been stuck on since 2019! arxiv.org/abs/2509.16180 1/n
Wanna do a postdoc at NYU? We have postings for Faculty Fellows at both @nyudatascience.bsky.social and @nyucourant.bsky.social CS in the new School for Mathematics, Computing, and Data Science!
Come work with the best!
Courant CS: apply.interfolio.com/175537
CDS: apply.interfolio.com/174686
Come work with the best!
Courant CS: apply.interfolio.com/175537
CDS: apply.interfolio.com/174686
November 21, 2025 at 4:00 PM
Wanna do a postdoc at NYU? We have postings for Faculty Fellows at both @nyudatascience.bsky.social and @nyucourant.bsky.social CS in the new School for Mathematics, Computing, and Data Science!
Come work with the best!
Courant CS: apply.interfolio.com/175537
CDS: apply.interfolio.com/174686
Come work with the best!
Courant CS: apply.interfolio.com/175537
CDS: apply.interfolio.com/174686
A modest demonstration, but Nano Banana Pro with Gemini 3 Pro gets this simple task mostly right! At least no imaginary people this time.
(The aspect ratios are a bit off for some)
(The aspect ratios are a bit off for some)
November 21, 2025 at 12:50 PM
A modest demonstration, but Nano Banana Pro with Gemini 3 Pro gets this simple task mostly right! At least no imaginary people this time.
(The aspect ratios are a bit off for some)
(The aspect ratios are a bit off for some)
Thoughtful (as always) blog post from Nicholas Carlini. "Are large language models worth it?" A nice read giving his perspective on risks of ML models.
Post: nicholas.carlini.com/writing/2025...
For people who prefer, this is the video of the talk from @colmweb.org www.youtube.com/watch?v=PngH...
Post: nicholas.carlini.com/writing/2025...
For people who prefer, this is the video of the talk from @colmweb.org www.youtube.com/watch?v=PngH...
November 19, 2025 at 4:56 PM
Thoughtful (as always) blog post from Nicholas Carlini. "Are large language models worth it?" A nice read giving his perspective on risks of ML models.
Post: nicholas.carlini.com/writing/2025...
For people who prefer, this is the video of the talk from @colmweb.org www.youtube.com/watch?v=PngH...
Post: nicholas.carlini.com/writing/2025...
For people who prefer, this is the video of the talk from @colmweb.org www.youtube.com/watch?v=PngH...
At least if the reviewer ghosts you, you know you have to find another reviewer...
(The reviewer did come through at the 11th and a half hour though!)
(The reviewer did come through at the 11th and a half hour though!)
November 17, 2025 at 6:09 PM
At least if the reviewer ghosts you, you know you have to find another reviewer...
(The reviewer did come through at the 11th and a half hour though!)
(The reviewer did come through at the 11th and a half hour though!)
I am recruiting PhD students at NYU Courant to conduct research in learning theory, algorithmic statistics, and trustworthy machine learning, starting Fall 2026. Please share widely! Deadline to apply is December 12, 2025.
November 13, 2025 at 3:00 PM
I am recruiting PhD students at NYU Courant to conduct research in learning theory, algorithmic statistics, and trustworthy machine learning, starting Fall 2026. Please share widely! Deadline to apply is December 12, 2025.
I admire Don Knuth for many things. But perhaps the most admirable is quitting email before I was even born.
From cs.stanford.edu/~knuth/email...
From cs.stanford.edu/~knuth/email...
November 12, 2025 at 2:57 PM
I admire Don Knuth for many things. But perhaps the most admirable is quitting email before I was even born.
From cs.stanford.edu/~knuth/email...
From cs.stanford.edu/~knuth/email...
AI generated or not? Appetizing or not?
November 12, 2025 at 2:56 PM
AI generated or not? Appetizing or not?
Small update to my blog post on organizing academic workshops. Make sure the poster arrangement is welcoming and allows people to navigate freely! If it's cramped and crowded, that can be a major turnoff.
November 11, 2025 at 4:44 PM
Small update to my blog post on organizing academic workshops. Make sure the poster arrangement is welcoming and allows people to navigate freely! If it's cramped and crowded, that can be a major turnoff.
Fried chicken is all you need
November 9, 2025 at 11:33 PM
Fried chicken is all you need
A few weeks ago everyone was super hype about Nano Banana. Meanwhile, I ask it to do super basic things and it fails. What am I doing wrong??
(why would I want a collage of these amazing researchers? Stay tuned CC @let-all.com 👀)
More fails in the transcript: gemini.google.com/share/5cc80f...
(why would I want a collage of these amazing researchers? Stay tuned CC @let-all.com 👀)
More fails in the transcript: gemini.google.com/share/5cc80f...
November 7, 2025 at 3:52 PM
A few weeks ago everyone was super hype about Nano Banana. Meanwhile, I ask it to do super basic things and it fails. What am I doing wrong??
(why would I want a collage of these amazing researchers? Stay tuned CC @let-all.com 👀)
More fails in the transcript: gemini.google.com/share/5cc80f...
(why would I want a collage of these amazing researchers? Stay tuned CC @let-all.com 👀)
More fails in the transcript: gemini.google.com/share/5cc80f...
Announcing (w @adamsmith.xyz @thejonullman.bsky.social) the 2025 edition of the Foundations of Responsible Computing Job Market Profiles!
Check out 40 job market candidates in mathematical research in computation and society writ large!
Link:
drive.google.com/file/d/1zvsr...
Check out 40 job market candidates in mathematical research in computation and society writ large!
Link:
drive.google.com/file/d/1zvsr...
October 20, 2025 at 12:00 PM
Announcing (w @adamsmith.xyz @thejonullman.bsky.social) the 2025 edition of the Foundations of Responsible Computing Job Market Profiles!
Check out 40 job market candidates in mathematical research in computation and society writ large!
Link:
drive.google.com/file/d/1zvsr...
Check out 40 job market candidates in mathematical research in computation and society writ large!
Link:
drive.google.com/file/d/1zvsr...
Looking back on a phenomenal workshop in Ascona -- what a fantastic experience! Every talk was captivating. And Zurich afterwards made its mark as one of my favourite European cities.
Thanks again Fanny Yang, Niao He, Santiago Mazuelas for organizing such a memorable workshop!
Thanks again Fanny Yang, Niao He, Santiago Mazuelas for organizing such a memorable workshop!
October 18, 2025 at 7:10 PM
Looking back on a phenomenal workshop in Ascona -- what a fantastic experience! Every talk was captivating. And Zurich afterwards made its mark as one of my favourite European cities.
Thanks again Fanny Yang, Niao He, Santiago Mazuelas for organizing such a memorable workshop!
Thanks again Fanny Yang, Niao He, Santiago Mazuelas for organizing such a memorable workshop!
Field trip with The Salon, on the way to the Symposium on Mathematical Foundations of Trustworthy Learning in Ascona, Switzerland! CC @argymouz.bsky.social @matt19234.bsky.social
October 12, 2025 at 1:14 PM
Field trip with The Salon, on the way to the Symposium on Mathematical Foundations of Trustworthy Learning in Ascona, Switzerland! CC @argymouz.bsky.social @matt19234.bsky.social
The asymmetry between the 1st and 4th options shows that weak accepts and weak rejects don't mirror each other. Uniformly weak support for a paper can be damning, and a paper usually needs a champion.
(Also, 5.8% of people are sickos.)
(Also, 5.8% of people are sickos.)
October 10, 2025 at 6:50 PM
The asymmetry between the 1st and 4th options shows that weak accepts and weak rejects don't mirror each other. Uniformly weak support for a paper can be damning, and a paper usually needs a champion.
(Also, 5.8% of people are sickos.)
(Also, 5.8% of people are sickos.)
I'm in Switzerland next week! On Friday, October 17, I'll be giving a talk at @eth-ai-center.bsky.social on memorization in diffusion models. Please join if you're around!
October 9, 2025 at 2:01 PM
I'm in Switzerland next week! On Friday, October 17, I'll be giving a talk at @eth-ai-center.bsky.social on memorization in diffusion models. Please join if you're around!
Getting mixed signals here
September 26, 2025 at 7:48 PM
Getting mixed signals here
While I'm here, let me advertise that Reed CS is hiring this year in Systems! It's a wonderful set of people in the deparment, really engaged students, and (unlike many college) you can live in a city. Deadline October 17
Definitely apply if you're looking for a "PUI" position
Definitely apply if you're looking for a "PUI" position
September 16, 2025 at 2:03 PM
While I'm here, let me advertise that Reed CS is hiring this year in Systems! It's a wonderful set of people in the deparment, really engaged students, and (unlike many college) you can live in a city. Deadline October 17
Definitely apply if you're looking for a "PUI" position
Definitely apply if you're looking for a "PUI" position
I'm in Portland, Oregon visiting Reed College (@reed.edu) as part of the external review for their computer science department!
This picture looks like a typical New England liberal arts college, but the PNW remains one of the most beautiful parts of the US.
This picture looks like a typical New England liberal arts college, but the PNW remains one of the most beautiful parts of the US.
September 15, 2025 at 5:46 PM
I'm in Portland, Oregon visiting Reed College (@reed.edu) as part of the external review for their computer science department!
This picture looks like a typical New England liberal arts college, but the PNW remains one of the most beautiful parts of the US.
This picture looks like a typical New England liberal arts college, but the PNW remains one of the most beautiful parts of the US.
Anyone who's done a PhD knows the feeling
September 14, 2025 at 1:41 PM
Anyone who's done a PhD knows the feeling
Always a pleasant reminder every time I stop by my local public library @kitchlibrary.bsky.social (see bottom right)
September 10, 2025 at 1:58 PM
Always a pleasant reminder every time I stop by my local public library @kitchlibrary.bsky.social (see bottom right)