Congratulations to Venkat Guruswami, new director of the Simons Institute for the Theory of Computing (@simonsinstitute.bsky.social)! And congrats to us, the Theoretical CS community, for having someone as good, dedicated, and wonderful as him at the helm of a place so important to us! #TCSSky
October 30, 2025 at 8:18 PM
Congratulations to Venkat Guruswami, new director of the Simons Institute for the Theory of Computing (@simonsinstitute.bsky.social)! And congrats to us, the Theoretical CS community, for having someone as good, dedicated, and wonderful as him at the helm of a place so important to us! #TCSSky
Monthly digest of the property testing papers: ptreview.sublinear.info/2025/10/news...
Always fun to see what the community has been up to! Some exciting papers, as usual, and a little something for everyone. #TCSSky
Always fun to see what the community has been up to! Some exciting papers, as usual, and a little something for everyone. #TCSSky
News for September 2025 | Property Testing Review
ptreview.sublinear.info
October 4, 2025 at 9:54 AM
Monthly digest of the property testing papers: ptreview.sublinear.info/2025/10/news...
Always fun to see what the community has been up to! Some exciting papers, as usual, and a little something for everyone. #TCSSky
Always fun to see what the community has been up to! Some exciting papers, as usual, and a little something for everyone. #TCSSky
📢 Our first TCS+ talk of the season will be Wednesday, Oct 8 (10amPT, 1pm ET, 19:00 CEST): Janani Sundaresan, from U Waterloo, will tell us how "Distributed Triangle Detection is Hard in Few Rounds"!
RSVP to receive the link (available one day prior to the talk): forms.gle/sHdV8uoKYVpq... #TCSSky
RSVP to receive the link (available one day prior to the talk): forms.gle/sHdV8uoKYVpq... #TCSSky
TCS+ RSVP: Janani Sundaresan (2025/10/08)
Title: Distributed Triangle Detection is Hard in Few Rounds
forms.gle
September 27, 2025 at 9:42 PM
📢 Our first TCS+ talk of the season will be Wednesday, Oct 8 (10amPT, 1pm ET, 19:00 CEST): Janani Sundaresan, from U Waterloo, will tell us how "Distributed Triangle Detection is Hard in Few Rounds"!
RSVP to receive the link (available one day prior to the talk): forms.gle/sHdV8uoKYVpq... #TCSSky
RSVP to receive the link (available one day prior to the talk): forms.gle/sHdV8uoKYVpq... #TCSSky
Computer scientists investigate the relationship between informal and formal mathematics. This area is very fertile, yet promising. The tutorial recording is in: machine-learning-for-theorem-proving.github.io #MathSky #TCSsky
March 30, 2025 at 2:49 PM
Computer scientists investigate the relationship between informal and formal mathematics. This area is very fertile, yet promising. The tutorial recording is in: machine-learning-for-theorem-proving.github.io #MathSky #TCSsky
📢 Our fifth TCS+ talk will be Wednesday, May 7 (10amPT, 1pm ET, 19:00 CEST): Palak Jain (@thepalakjain.bsky.social) from Boston University, will tell us about "Enforcing Demographic Coherence"!
RSVP to receive the link (available one day prior to the talk):
forms.gle/MmBBWJizY9RJ... #TCSSky
RSVP to receive the link (available one day prior to the talk):
forms.gle/MmBBWJizY9RJ... #TCSSky
TCS+ RSVP: Palak Jain (2025/05/07)
Title: Enforcing Demographic Coherence: A Harms Aware Framework for Reasoning about Private Data Release
forms.gle
May 1, 2025 at 9:20 PM
📢 Our fifth TCS+ talk will be Wednesday, May 7 (10amPT, 1pm ET, 19:00 CEST): Palak Jain (@thepalakjain.bsky.social) from Boston University, will tell us about "Enforcing Demographic Coherence"!
RSVP to receive the link (available one day prior to the talk):
forms.gle/MmBBWJizY9RJ... #TCSSky
RSVP to receive the link (available one day prior to the talk):
forms.gle/MmBBWJizY9RJ... #TCSSky
🎉 Joachim Gudmundsson's paper "A well-separated pair decomposition for low density graphs" has been accepted at #SODA2026!
📝 Paper: arxiv.org/abs/2411.08204
🔗 More about SODA'26: www.siam.org/conferences-...
#Algorithms #TCSSky #ComputationalGeometry #SIAMDA26
📝 Paper: arxiv.org/abs/2411.08204
🔗 More about SODA'26: www.siam.org/conferences-...
#Algorithms #TCSSky #ComputationalGeometry #SIAMDA26
A well-separated pair decomposition for low density graphs
Low density graphs are considered to be a realistic graph class for modelling road networks. It has advantages over other popular graph classes for road networks, such as planar graphs, bounded highwa...
arxiv.org
October 6, 2025 at 9:25 PM
🎉 Joachim Gudmundsson's paper "A well-separated pair decomposition for low density graphs" has been accepted at #SODA2026!
📝 Paper: arxiv.org/abs/2411.08204
🔗 More about SODA'26: www.siam.org/conferences-...
#Algorithms #TCSSky #ComputationalGeometry #SIAMDA26
📝 Paper: arxiv.org/abs/2411.08204
🔗 More about SODA'26: www.siam.org/conferences-...
#Algorithms #TCSSky #ComputationalGeometry #SIAMDA26
I'm currently updating my lecture notes and course material for the second iteration of my course on randomized algorithms. (Main "big" changes planned: upgrading Chapters 8 and 9)
If you have any suggestions or requests, please reach out!
ccanonne.github.io/teaching/COM... #TCSSky
If you have any suggestions or requests, please reach out!
ccanonne.github.io/teaching/COM... #TCSSky
Content for the COMP4270 and COMP5270 Course on “Randomised and Advanced Algorithms” at the University of Sydney ##
ccanonne.github.io
March 12, 2025 at 12:29 AM
I'm currently updating my lecture notes and course material for the second iteration of my course on randomized algorithms. (Main "big" changes planned: upgrading Chapters 8 and 9)
If you have any suggestions or requests, please reach out!
ccanonne.github.io/teaching/COM... #TCSSky
If you have any suggestions or requests, please reach out!
ccanonne.github.io/teaching/COM... #TCSSky
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 13, 2024 at 9:43 PM
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
Google's algorithms does something nice, recommending me Yael Kalai's new released course 😀. #TCSsky #Cryptography.
MIT OCW: ocw.mit.edu/courses/6-56...
MIT OCW: ocw.mit.edu/courses/6-56...
January 30, 2025 at 8:03 AM
Google's algorithms does something nice, recommending me Yael Kalai's new released course 😀. #TCSsky #Cryptography.
MIT OCW: ocw.mit.edu/courses/6-56...
MIT OCW: ocw.mit.edu/courses/6-56...
On the TCS job market: Tamalika Mukherjee!
Tamalika's research: (1) designing computationally efficient privacy-preserving algorithms for data analysis, (2) understanding their societal implications through the lens of equity and policy. Keywords: sublinear, DP
1/2 #TCSSky #AcademicJobMarket
Tamalika's research: (1) designing computationally efficient privacy-preserving algorithms for data analysis, (2) understanding their societal implications through the lens of equity and policy. Keywords: sublinear, DP
1/2 #TCSSky #AcademicJobMarket
November 25, 2024 at 8:24 PM
On the TCS job market: Tamalika Mukherjee!
Tamalika's research: (1) designing computationally efficient privacy-preserving algorithms for data analysis, (2) understanding their societal implications through the lens of equity and policy. Keywords: sublinear, DP
1/2 #TCSSky #AcademicJobMarket
Tamalika's research: (1) designing computationally efficient privacy-preserving algorithms for data analysis, (2) understanding their societal implications through the lens of equity and policy. Keywords: sublinear, DP
1/2 #TCSSky #AcademicJobMarket
Truly excited to have received this cookbook from the Simons Institute! Now I can eat well – in theory. #TCSSky
simons.berkeley.edu/news/cooks-t...
simons.berkeley.edu/news/cooks-t...
January 21, 2025 at 1:05 AM
Truly excited to have received this cookbook from the Simons Institute! Now I can eat well – in theory. #TCSSky
simons.berkeley.edu/news/cooks-t...
simons.berkeley.edu/news/cooks-t...
🧩 📊 Answers and discussion for last week's #WeaklyQuiz: "what's a randomized 🎲 algorithm anyway?"
Ft. Monte Carol 👩💻 and Las Daves 👨💻 algorithms—or something along those lines! #TCSSky
For an extended writeup of everything in this thread 🧵:
📝 github.com/ccanonne/wee...
1/
Ft. Monte Carol 👩💻 and Las Daves 👨💻 algorithms—or something along those lines! #TCSSky
For an extended writeup of everything in this thread 🧵:
📝 github.com/ccanonne/wee...
1/
March 3, 2025 at 11:15 AM
🧩 📊 Answers and discussion for last week's #WeaklyQuiz: "what's a randomized 🎲 algorithm anyway?"
Ft. Monte Carol 👩💻 and Las Daves 👨💻 algorithms—or something along those lines! #TCSSky
For an extended writeup of everything in this thread 🧵:
📝 github.com/ccanonne/wee...
1/
Ft. Monte Carol 👩💻 and Las Daves 👨💻 algorithms—or something along those lines! #TCSSky
For an extended writeup of everything in this thread 🧵:
📝 github.com/ccanonne/wee...
1/
It's for education; maybe one day we see software engineers adopt something similar to it. #TCSSky
I wanted my Algorithms students to program NP hardness reductions so we developed Karp. A domain specific language for writing Karp reductions. Our students are quite good with a debugger, so reducing learning Theory to debugging seemed like a win. docs.racket-lang.org/karp/index.h...
Karp: A Language for NP Reductions
docs.racket-lang.org
November 27, 2024 at 5:55 AM
It's for education; maybe one day we see software engineers adopt something similar to it. #TCSSky
On the TCS job market: Eli Chien!
Eli works on TCS∩ML: e.g., Machine Unlearning, hidden-state DP analysis and their application to graph ML. He recently generalized the celebrated shifted-divergence analysis to non-convex non-smooth setting for hidden-state DP-SGD.
1/2 #TCSSky #AcademicJobMarket
Eli works on TCS∩ML: e.g., Machine Unlearning, hidden-state DP analysis and their application to graph ML. He recently generalized the celebrated shifted-divergence analysis to non-convex non-smooth setting for hidden-state DP-SGD.
1/2 #TCSSky #AcademicJobMarket
November 26, 2024 at 8:15 PM
If you want to know more about the Code of Conduct at #FOCS2025, or more generally the SafeToC initiative:
- Code of Conduct: focs.computer.org/2025/code-of...
- SafeToC: safetoc.org #TCSSky
- Code of Conduct: focs.computer.org/2025/code-of...
- SafeToC: safetoc.org #TCSSky
Code of Conduct – FOCS 2025
focs.computer.org
March 29, 2025 at 4:29 AM
If you want to know more about the Code of Conduct at #FOCS2025, or more generally the SafeToC initiative:
- Code of Conduct: focs.computer.org/2025/code-of...
- SafeToC: safetoc.org #TCSSky
- Code of Conduct: focs.computer.org/2025/code-of...
- SafeToC: safetoc.org #TCSSky
Remember to fill this form if you're on the #TCSSky job market and want me to post about you!
It's tough to gain visibility as a young researcher, and it's job market season! Are you a theoretical computer science PhD/postdoc on the job market?
I don't have a crazy juge audience but I'll try to help a bit: fill this form, and I'll tweet your pitch and info!
docs.google.com/forms/d/e/1F...
I don't have a crazy juge audience but I'll try to help a bit: fill this form, and I'll tweet your pitch and info!
docs.google.com/forms/d/e/1F...
Theoretical CS Job Market 2024
docs.google.com
December 1, 2024 at 9:12 PM
Remember to fill this form if you're on the #TCSSky job market and want me to post about you!
Again, many other great papers — this is just a very small sample, and very biased. Have a look yourself! acm-stoc.org/stoc2025/acc... #TCSSky
STOC 2025 - 57th ACM Symposium on Theory of Computing
acm-stoc.org
February 7, 2025 at 11:10 PM
Again, many other great papers — this is just a very small sample, and very biased. Have a look yourself! acm-stoc.org/stoc2025/acc... #TCSSky
Another TCS+ talk to look forward to: next week, Palak Jain (@thepalakjain.bsky.social) on a new data #privacy framework they introduce!
📋 forms.gle/ateNLcRo59H1... #TCSSky
📋 forms.gle/ateNLcRo59H1... #TCSSky
📢 Our fifth TCS+ talk will be Wednesday, May 7 (10amPT, 1pm ET, 19:00 CEST): Palak Jain (@thepalakjain.bsky.social) from Boston University, will tell us about "Enforcing Demographic Coherence"!
RSVP to receive the link (available one day prior to the talk):
forms.gle/MmBBWJizY9RJ... #TCSSky
RSVP to receive the link (available one day prior to the talk):
forms.gle/MmBBWJizY9RJ... #TCSSky
TCS+ RSVP: Palak Jain (2025/05/07)
Title: Enforcing Demographic Coherence: A Harms Aware Framework for Reasoning about Private Data Release
forms.gle
May 1, 2025 at 9:24 PM
Another TCS+ talk to look forward to: next week, Palak Jain (@thepalakjain.bsky.social) on a new data #privacy framework they introduce!
📋 forms.gle/ateNLcRo59H1... #TCSSky
📋 forms.gle/ateNLcRo59H1... #TCSSky
Training datasets are biased against theorists. #TCSsky
Dear Google search. I don't mean private parties. I never mean private parties. I am neither hip nor a socialite. It's private parities. I meant what I said. Every time. Thank you.
February 24, 2025 at 7:55 PM
Training datasets are biased against theorists. #TCSsky
Online CS Theory Seminar this Fri 2025-10-31!
We're excited to have Miriam Backens (INRIA & LORIA), presenting "Computational counting problems and quantum information theory"
members.loria.fr/MBackens/
www.colorado.edu/cs-theory/th...
#MathSky #Algorithms #Complexity #TCSSky #Quantum
We're excited to have Miriam Backens (INRIA & LORIA), presenting "Computational counting problems and quantum information theory"
members.loria.fr/MBackens/
www.colorado.edu/cs-theory/th...
#MathSky #Algorithms #Complexity #TCSSky #Quantum
October 28, 2025 at 9:38 PM
Online CS Theory Seminar this Fri 2025-10-31!
We're excited to have Miriam Backens (INRIA & LORIA), presenting "Computational counting problems and quantum information theory"
members.loria.fr/MBackens/
www.colorado.edu/cs-theory/th...
#MathSky #Algorithms #Complexity #TCSSky #Quantum
We're excited to have Miriam Backens (INRIA & LORIA), presenting "Computational counting problems and quantum information theory"
members.loria.fr/MBackens/
www.colorado.edu/cs-theory/th...
#MathSky #Algorithms #Complexity #TCSSky #Quantum
On the TCS job market: Rishav Chourasia!
Rishav's primary interests are differential privacy and learning theory. He showed that hidden-state DP-GD achieves convergent privacy under strong convexity, cited as a "breakthrough" by Altschuler and Talwar (2022).
1/2 #TCSSky #AcademicJobMarket
Rishav's primary interests are differential privacy and learning theory. He showed that hidden-state DP-GD achieves convergent privacy under strong convexity, cited as a "breakthrough" by Altschuler and Talwar (2022).
1/2 #TCSSky #AcademicJobMarket
December 2, 2024 at 7:37 PM
On the TCS job market: Rishav Chourasia!
Rishav's primary interests are differential privacy and learning theory. He showed that hidden-state DP-GD achieves convergent privacy under strong convexity, cited as a "breakthrough" by Altschuler and Talwar (2022).
1/2 #TCSSky #AcademicJobMarket
Rishav's primary interests are differential privacy and learning theory. He showed that hidden-state DP-GD achieves convergent privacy under strong convexity, cited as a "breakthrough" by Altschuler and Talwar (2022).
1/2 #TCSSky #AcademicJobMarket
we need more long these 🙂. Research is a subjective experience than students usually think. #TCSsky #AcademicSky
Found slides by Ankur Moitra (presented at a TCS For All event) on "How to do theoretical research." Full of great advice!
My favourite: "Find the easiest problem you can't solve. The more embarrassing, the better!"
Slides: drive.google.com/file/d/15VaT...
TCS For all: sigact.org/tcsforall/
My favourite: "Find the easiest problem you can't solve. The more embarrassing, the better!"
Slides: drive.google.com/file/d/15VaT...
TCS For all: sigact.org/tcsforall/
December 14, 2024 at 3:54 AM
we need more long these 🙂. Research is a subjective experience than students usually think. #TCSsky #AcademicSky