A diagram with several parts linked by arrows and the statement of a theorem. Theorem: The trivial sublink problem is NP-hard. Diagram: A of a graph (network) on 5 vertices with 5 distinct colors, along with its 5x5 adjacency matrix (0s and 1s) With an arrow that says "Build braid word" to a 5-strand braid, where each of the five strands has a color corresponding to one of the 5 vertices. An arrow from the braid that say s"Take trace closure of braid (and simplify greedily)" Pointing to a 5-component link, where each component has a color corresponding to the color of one of the strands.

Online CS Theory Seminar this Fri 2026-03-27!

We're excited to have Eric Samperton (Purdue Uni.) presenting "Complexity of Algebraic Problems in Low-Dimensional Topology"

www.math.purdue.edu/~esampert/
www.colorado.edu/cs-theory/th...

#MathSky #TCSSky #complexity #topology

ACM SIGACT - SIGACT Distinguished Service Award

"Nominations can be made by any member of the Theory of Computing community."
sigact.org/prizes/servi... #TCSSky

ACM SIGACT - SIGACT Distinguished Service Award

Since SIGACT is on X but not BlueSky,* advertising the SIGACT Distinguished Service Award here, "given annually to an individual or group who has made substantial service contributions to the Theoretical CS community" #TCSSky

⏰ Nominate by April 30!
sigact.org/prizes/servi...

*I know. Ugh.

Postdoctoral Research Associate in Theoretical Computer Science and Algorithms Full time, fixed term for two years (with the possibility of extension) Located on the Camperdown Campus, University of Sydney Base Salary Academic Level A $109,263 - $121,054 + 17% superannuation Abo...

On the postdoc job market? "As foretold" some time ago, the Sydney Algorithms and Computing Theory group at @sydneycompsci.bsky.social is hiring postdocs (2 years, renewable) in Theoretical Computer Science and Algorithms!

usyd.wd105.myworkdayjobs.com/en-GB/USYD_E... #TCSSky

Theoretical CS community! I have a small favor to ask. If you ever used, read, watched some of the (excellent IMO) exposition content by Ryan O'Donnell, would you mind filling this very short survey, and maybe say how useful to you it was?

📝 forms.gle/xrvc2mLRbMqK...

Please spread this! #TCSSky

Content for the COMP4270 and COMP5270 Course on “Randomised and Advanced Algorithms” at the University of Sydney ##

I am thinking of converting my lecture notes for my "Randomized #Algorithms" class into a textbook over this semester. What do you think, and what would you like to see?

More tutorials/exercises? Examples of assignments? Something else?

🔗 ccanonne.github.io/teaching/COM... #TCSSky

We are so excited this is happening! Ask me any questions, #TCSSky #MathSky!

Also, we are looking for a couple more project leaders, so if you want to know more about what that involves, please get in touch.

If you know people in Theoretical CS or adjacent who just joined BlueSky (or just did yourself), please tag them or say hi in this thread! #TCSSky (I'll follow them/you, let's strengthen our research community here)

The logo of the DCFS 2026 conference.

Please submit your research papers and join us at the 27th International Conference on Descriptional Complexity of Formal Systems (DCFS 2026), to be held in Kingston, Canada from August 9 to 11, 2026!
Details: research.cs.queensu.ca/dcfs2026/
#tcssky #mathsky

The logo of the CIAA 2026 conference.

Please submit your research papers and join us at the 30th International Conference on Implementation and Application of Automata (CIAA 2026), to be held in Kingston, Canada from August 5 to 8, 2026!
Details: research.cs.queensu.ca/ciaa2026/
#tcssky #mathsky

Internet Oracle - Wikipedia

TIL why we use the word "oracle" in theoretical CS for blackbox abstractions. Because of some joke from the seventies!

We were absurd before it was cool.
en.wikipedia.org/wiki/Interne... #TCSSky

The first page of my paper, "Improved Randomized Approximation of Hard Universality and Emptiness Problems", coauthored with Pantelis Andreou of Dalhousie University and Stavros Konstantinidis of Saint Mary's University.

Check out my latest paper in JALC! "Improved Randomized Approximation of Hard Universality and Emptiness Problems":
jalc.de/issues/2025/...
(arXiv link: arxiv.org/abs/2403.08707)
#TCSSky #MathSky

Sydney Algorithms and Computing Theory (SACT)

The SACT group at #USyd 🇦🇺 has a number of postdoc positions available (2+ years) in all areas of TCS, with one focusing on streaming and one on planning and synthesis. Expected start mid- or end 2026.

Excellent candidates are encouraged to contact us by email, or during #FOCS2025 #TCSSky

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

Two graphs with an arrow between them labeled "x3" First graph has a ndoe with three edges, connected to quadrilateral shapes labeled A,B,C, that also have additional outgoing edges Second graph has three such nodes, with three copies of A, three of B, three of C, in various positions and orientations, hooked up in a complicated way.

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

Poster for the event, with the title (A Celebration of TCS), the location, the url and a QR code, and a picture depicting a range of people (as emojis) being the vertices of a highly connected graph.

Dec 11-13 at #USyd, just before #FOCS2025: "A Celebration of Theoretical Computer Science": now with a poster!

Info and (free) registration: sites.google.com/view/celebra... #TCSSky

A grid of 0s and 1s with the 1s highlighted blue One row is circled in red Next to it, a vector q = 0100

Hybrid CS Theory Seminar next Fri 2025-10-24!

We're excited to have Alexander Golovnev (Georgetown University), presenting "Online Orthogonal Vectors Revisited"

golovnev.org
www.colorado.edu/cs-theory/th...

#MathSky #Algorithms #Complexity #TCSSky

Confirmed Speakers (Inspirational and Rising Stars) Prof. Shafi Goldwasser (MIT) Prof. Meena Mahajan (Institute of Mathematical Sciences, Chennai) Ioana-Oriana Bercea (KTH) Lorenzo Ciardo (Oxford University) Jane Lange (MIT) Yihui Quek (EPFL) Santhoshini Velusamy (TTIC to University of Waterloo) Hanzhi Wang (BARC to U Melbourne)

Truly a fantastic line-up of speakers! Also: poster session (most likely involving gelato), reception, networking, Q&A: sites.google.com/view/celebra...

All that on the (beautiful) #USyd campus, in summery December, just before FOCS! #TCSSky

TCS+ - 2025-2026 2025/10/08: Janani Sundaresan, "Distributed Triangle Detection is Hard in Few Rounds" Janani Sundaresan (University of Waterloo)

The recording and slides of this week's talk by Janani Sundaresan, on how "Distributed Triangle Detection is Hard in Few Rounds", are now available online!

www.tcsplus.org/welcome/past... #TCSSky

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...

🎉 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

News for September 2025 | Property Testing Review

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

TCS+ RSVP: Janani Sundaresan (2025/10/08) Title: Distributed Triangle Detection is Hard in Few Rounds

📢 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

- 8 Oct, Wed, 1pm TCS+ Talk: Janani Sundaresan (U Waterloo) - 22 Oct, Wed, 1pm TCS+ Talk: Ian Mertz (Charles University) - 5 Nov, Wed, 1pm TCS+ Talk: Aparna Gupte (MIT) (Times are Eastern time)

And as a teaser, here are the first 3 talks of the season! #TCSSky
- Janani Sundaresan, on her #FOCS2025 result showing hardness of distributed triangle detection
- Ian Mertz, with a survey talk on catalytic computing
- Aparna Gupte, on her #STOC2025 result on quantum one-time programs

Reminder: submit a workshop proposal for #FOCS2025 by ⏰ September 5!

"Workshops often serve the vital purpose of introducing researchers to new areas and agendas. We also encourage workshops focusing on connections between TCS and other areas." #TCSSky

Details: focs.computer.org/2025/call-fo...

Has anybody developed the theory of STRICT correlated equilibria of a finite game?

#econsky #mathsky #ECsky #TCSsky

I was playing around with it a bit, and here are some things that are easy to show about the set CE^S of strict correlated equilibrium distributions.

Researchers subjectively believe in their directions before progressing through them. #science #TCSsky
Quote: "Many people believed that there’s no better way. Duan wasn’t one of them. He’d long dreamed of building a shortest-paths algorithm that could break through the sorting barrier."

I don't know how significant Geometry, Topology, or Algebra, will be on machine learning. Nonetheless, It's great to see a paper surveying and introducing such emerging fields. #AI #MathSky #TCSsky
arxiv.org/abs/2407.09468

Where else would we find a TCS community, if not in the US? #TCSsky

Could you enter the home inside and take pictures? Seeing the office of A. Turing would be super cool. #TCSsky

A beautiful and accessible, yet under-rated, TCS introductory book: nature-of-computation.org #TCSsky #TCS