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

The early registration deadline is November 21, 2025 (but don't wait until the last minute to book your hotel! December in Sydney is peak season, and while there are many hotels in the area, they tend to get booked quickly as summer nears!)

Turns out, the textbooks are all wrong. State of the art LP software has ~5 tricks that differ from the textbook description. All good software uses the same 5 tricks! Three of those tricks, we figured out how to make theoretical use of.

Reminder: #USyd is hiring in #ComputerScience! If you have questions or would like to know more about academia or life in Sydney (or 🇦🇺 Australia), do reach out! Moving here was the best choice I've made. usyd.wd105.myworkdayjobs.com/en-GB/USYD_E... bsky.app/profile/sydn...

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

Joshua A. Grochow, Abhiram Natarajan Gr\"obner Bases Native to Term-ordered Commutative Algebras, with Application to the Hodge Algebra of Minors https://arxiv.org/abs/2510.11212

The previous smoothed analysis paper is now published in TheoretiCS. It is a diamond open access journal and it was a very pleasant experience submitting there. If you have a strong theory paper, I highly recommend sending it there!

The School of #ComputerScience at #USyd is hiring! Multiple continuing (≡ tenure-track) positions in all areas, with particular focus on the ones listed below. Women and candidates from underrepresented groups are encouraged to apply. ⏰ Apply by Dec 1: usyd.wd105.myworkdayjobs.com/en-GB/USYD_E...

Reminder/plug: my graduate-level monograph on "Topics and Techniques in Distribution Testing" (FnT Comm. and Inf Theory, 2022). 📖 ccanonne.github.io/survey-topic... [Latest draft+exercise solns, free] 📗 nowpublishers.com/article/Deta... [Official pub] 📝 github.com/ccanonne/sur... [LaTeX source]

The simplex method is an algorithm that turns an optimization problem, like setting up an investment portfolio, into a geometry problem. Recently, the scientists Sophie Huiberts (left) and Eleon Bach reduced the runtime of the simplex method. www.quantamagazine.org/researchers-...

A Simple and Efficient One-Shot Signature Scheme (Andrew Huang, Vinod Vaikuntanathan) ia.cr/2025/1906

Weak Instances of the Inverse Matrix Code Equivalence Problem (Jesús-Javier Chi-Domínguez) ia.cr/2025/1909

Unambiguous SNARGs for P from LWE with Applications to PPAD Hardness (Liyan Chen, Cody Freitag, Zhengzhong Jin, Daniel Wichs) ia.cr/2025/1913

We’re excited to release the Call for Papers for #FAccT2026 which will be held in Montreal, Canada in June 2026! Abstracts are due on January 8th, papers due on January 13th. Call for Papers: facctconference.org/2026/cfp Important info in thread →

Tenure-track opening @ U. Colorado Boulder Dept. of Math! Esp. (but not only) looking for: algebraic geometry homotopy theory foundations functional analysis number theory interdisciplinary collab. b/w math & computer science or the math of quantum physics www.mathjobs.org/jobs/list/27... #🧮

U. Colorado Boulder Dept. of Computer Science is hiring faculty in: - #Quantum computing (scope include quantum CS theory): jobs.colorado.edu/jobs/JobDeta... - Computer architecture & systems: jobs.colorado.edu/jobs/JobDeta... Come join us! #🧮 🧪 ⚛️ #AcademicSky

SODA notifications are in the inboxes, and this paper will be in the conference :) This is my second paper using extended formulations to prove running time lower bounds. I am surprised that people have been sleeping on this angle, but happy to fill in the gap where needed

CU computer science is doing a search for a tenure-track position in quantum computing this year: jobs.colorado.edu/jobs/JobDeta.... The scope of the search in particular includes quantum CS theory! AMA about how awesome Boulder and Colorado are!

Online CS Theory Seminar Fri 2025-10-03! Excited to have Danillo Barros de Souza (BCAM) presenting "Efficient #Algorithms for Computing Higher-Order Forman-Ricci Curvature from #ComplexNetworks" www.bcamath.org/en/people/bc... www.colorado.edu/cs-theory/th... 🧪 #MathSky #ComplexSystems #Networks

📢 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

Hybrid seminar next Tues 2025-07-29! Physical Computation in the Era of Hardware Specialization by George Tzimpragos & Jennifer Volk, UW Madison. 11am MT in KOBL 105; email host Tamara Lehman for zoom link or to meet w/ the speakers. www.georgetzimpragos.com engineering.wisc.edu/directory/pr...

Hybrid CS Theory Seminar this Fri 2025-07-18! We're excited to have Alexander Kulikov (JetBrains) presenting "Polynomial formulations as a barrier for reduction-based hardness proofs" alexanderskulikov.github.io www.colorado.edu/cs-theory/th... 🧪 #MathSky #Algorithms #Complexity #TCSSky

Hybrid CS Theory Seminar this Tues 2025-06-17! We're excited to have Samuel Everett (U. Chicago) presenting "Structural correspondence in computational tractability and dynamical systems" www.samueleverett.com www.colorado.edu/cs-theory/th... 🧪 #MathSky #Dynamics #Algorithms #Complexity #TCSSky

STOC Theory Fest in Prague June 23-27. Registration now open. Early deadline is May 6. acm-stoc.org/stoc202... You can apply for student support. Deadline April 27. acm-stoc.org/stoc202...

I first got into smoothed analysis and linear programming during my master's. Now, 9 years later, we finally have matching upper and lower bounds. I spent a huge part of my life on this, and it feels weird that it's now finished.

Excited to have Varun Gupta in our Theory seminar online tomorrow (Fri 4 Apr 2025), speaking on Tractable Agreement Protocols! www.varungupta.info www.colorado.edu/cs-theory/th...

Join the Duke Association for Women in Math Chapter for a virtual women in math career panel entitled "Mathematics in Industry and Beyond" this Thursday, March 27th from 5 to 6 PM. Register at us06web.zoom.us/webinar/regi.... #AWM #Duke #WomenInMath #MathCareers #Industry #STEM

Division polynomials for arbitrary isogenies (Katherine E. Stange) ia.cr/2025/521

Prakash Murali and I are seeking to jointly recruit a postdoctoral researcher (Dowling postdoctoral fellow) at Cambridge focused on quantum algorithms, complexity, error correction, and architecture. Further details: www.jobs.cam.ac.uk/job/50485/ Deadline: 7 April 2025

Women in Logic 2025 call for papers is out! Check sites.google.com/view/wil2025...

June 3-6: MIP USA July 1-3: MIP Europe Tell your friends, tell your students, tell your friends' students!

Hybrid CS Theory Seminar today 2025-03-14 We're excited to have Spencer Peters from Cornell presenting "Recursive Lattice Reduction" spencerpeters.io www.colorado.edu/cs-theory/th... #MathSky #Algorithms #ComputationalComplexity

📢 Our second TCS+ talk will be next week Wednesday, March 19 (10amPT, 1pm ET, 18:00 CET): Tom Gur (@tomgur.bsky.social), from the University of Cambridge, will talk about "A Zero-Knowledge PCP Theorem"! RSVP to receive the link (available one day prior to the talk): forms.gle/Zwyn13NkKNSr...

The next few talks on TCS+ (@tcsplus.bsky.social): 🍰 Tom Gur on Zero-Knowledge PCPs (March 19) (@tomgur.bsky.social) 🍰 Or Zamir on streaming and optimal F₂ moment estimation (April 9) 🍰 Ryan Williams on time v. memory (April 23) (@rrwilliams.bsky.social) Sweet!

Women in Logic Online Speaker: Sonja Smets Title: Logic and Computation of Social Behavior Date: Wednesday, March 19, 2025 Time: 17:00 CEST Venue: Online via Zoom You can register for free at tuwien.zoom.us/meeting/regi....

Online CS Theory Seminar this Friday 2025-03-07! We're excited to have Erin Wolf Chambers from Notre Dame presenting "Computing optimal homotopies" wolfchambers.github.io www.colorado.edu/cs-theory/th... #MathSky 🧪 #Topology #ComputationalTopology #AppliedTopology #Algorithms

The STOC 2025 Theory Fest is looking for workshop proposals! Apply here: stoc2025theoryfest.netlify.app Deadline is March 9th, so act fast!

I've posted a lightly revised version (mostly revising the discussion at the end) to ECCC eccc.weizmann.ac.il/report/2025/...

What a fantastic initiative! Beyond funding/visa issues, this will also benefit people with family constraints, those concerned about reducing their carbon footprint, and many others. I'm looking forward to the online Junior-Senior Lunch!

Work with Surendra Ghentiyala and Noah Stephens-Davidowitz to be presented at ITCS '25 in a few days: "The more the merrier! On total coding and lattice problems and the complexity of finding multicollisions," eccc.weizmann.ac.il/report/2024/.... Check out Surendra's talk if you're attending! 1/

Online CS Theory Seminar this Friday 2024-12-13 We're excited to have Benjamin Rossman from Duke presenting on Choiceless Computation! users.cs.duke.edu/~br148/ www.colorado.edu/cs-theory/th...

From next year's organizers: ISAAC 2025, the 36th International Symposium on Algorithms and Computation, will be in Taiwan (Tainan City), Dec 8-10!

I recorded my current talk for youtube! If you are interested in linear programming or theoretical computer science, this is for you

Raise your hand if you are coming to FSTTCS or planning to follow along online so we can prepare a #FSTTCS2024 starter pack!

Putting together a starter pack of CS academics in Australia (+NZ), hit me up to be added. go.bsky.app/N5x6GLQ

The University of Michigan theory group is amazing, and has one the largest and best collections of junior theory faculty in the world!

FYI: postdoc positions at the EnCORE Institute, at UCSD! They're "looking for exceptional candidates in all areas of foundations of data science including Algorithms, ML Theory, Optimization, AI foundations, and Computational Neuroscience." ⏰ Deadline: Jan 15 academicjobsonline.org/ajo/jobs/28847

Hybrid CS Theory Seminar this Friday 2024-11-15 We're excited to have Mingda Qiao from MIT presenting "Truthfulness of Calibration Measures" sites.google.com/site/acmonst... www.colorado.edu/cs-theory/th...

I made a starter pack for Theoretical Computer Science (broadly construed)! #TheoryCS #TCSSky #MathSky #AcademicSky 🧪 go.bsky.app/2jS2SGw