bouldertheory.bsky.social
CU Boulder CS Theory
@bouldertheory.bsky.social
270 followers 71 following 14 posts
Computer science theory group at the University of Colorado Boulder https://www.colorado.edu/cs-theory/
www.colorado.edu
Posts Media Videos Starter Packs
Reposted by CU Boulder CS Theory
joshuagrochow.bsky.social
Joshua Grochow @joshuagrochow.bsky.social · 5d
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
2 9
Reposted by CU Boulder CS Theory
sophie.huiberts.me
Sophie Huiberts @sophie.huiberts.me · 6d
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
An unconditional lower bound for the active-set method in convex quadratic maximization
We prove that the active-set method needs an exponential number of iterations in the worst-case to maximize a convex quadratic function subject to linear constraints, regardless of the pivot rule used...
arxiv.org
1 1 14
Reposted by CU Boulder CS Theory
huckbennett.bsky.social
Huck Bennett @huckbennett.bsky.social · 7d
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!
Tenure-Track Faculty in Quantum Computing
jobs.colorado.edu
8 15
bouldertheory.bsky.social
CU Boulder CS Theory @bouldertheory.bsky.social · 10d
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
Danillo Barros de Souza | BCAM - Basque Center for Applied Mathematics
Postdoctoral Fellow at BCAM.
www.bcamath.org
1 3 5
Reposted by CU Boulder CS Theory
tcsplus.bsky.social
TCS+ @tcsplus.bsky.social · 11d
📢 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
TCS+ RSVP: Janani Sundaresan (2025/10/08)
Title: Distributed Triangle Detection is Hard in Few Rounds
forms.gle
1 5 6
bouldertheory.bsky.social
CU Boulder CS Theory @bouldertheory.bsky.social · Jul 15
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...
1 2
bouldertheory.bsky.social
CU Boulder CS Theory @bouldertheory.bsky.social · Jul 14
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
Fine-Grained Reductions Network of many problems, together with arrows between them representing fine-grained reductions, as well as the lower bounds on those problems assuming the (Strong) Exponential Time Hypothesis. Example problems include 3/2-approximate Diameter, SAT, Dominating Set, Edit Distance, All Pairs Shortest Paths, 3-SUM, Collinearity, Hitting Set, ...
2 6
bouldertheory.bsky.social
CU Boulder CS Theory @bouldertheory.bsky.social · Jun 15
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
Samuel Everett's webpage and research profile
Sam Everett's academic and research website.
www.samueleverett.com
1 5
Reposted by CU Boulder CS Theory
lance.fortnow.com
Lance Fortnow @lance.fortnow.com · Apr 14
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...
2 5
Reposted by CU Boulder CS Theory
sophie.huiberts.me
Sophie Huiberts @sophie.huiberts.me · Apr 8
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.
Optimal Smoothed Analysis of the Simplex Method
Smoothed analysis is a method for analyzing the performance of algorithms, used especially for those algorithms whose running time in practice is significantly better than what can be proven through w...
arxiv.org
1 8 71
bouldertheory.bsky.social
CU Boulder CS Theory @bouldertheory.bsky.social · Apr 4
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...
Varun Gupta
www.varungupta.info
Reposted by CU Boulder CS Theory
awm-math.org
The Association for Women in Mathematics @awm-math.org · Mar 25
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
2 5
Reposted by CU Boulder CS Theory
eprint.ing.bot
ePrint Updates @eprint.ing.bot · Mar 21
Division polynomials for arbitrary isogenies (Katherine E. Stange) ia.cr/2025/521
Abstract. Following work of Mazur-Tate and Satoh, we extend the definition of division polynomials to arbitrary isogenies of elliptic curves, including those whose kernels do not sum to the identity. In analogy to the classical case of division polynomials for multiplication-by-n, we demonstrate recurrence relations, identities relating to classical elliptic functions, the chain rule describing relationships between division polynomials on source and target curve, and generalizations to higher dimension (i.e., elliptic nets).
1 2
Reposted by CU Boulder CS Theory
tomgur.bsky.social
Tom Gur @tomgur.bsky.social · Mar 21
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
Dowling Fellowship Research Associate (Fixed Term) - Job Opportunities - University of Cambridge
Dowling Fellowship Research Associate (Fixed Term) in the Department of Computer Science and Technology at the University of Cambridge.
www.jobs.cam.ac.uk
1 7 21
Reposted by CU Boulder CS Theory
valeriadepaiva.bsky.social
Valeria de Paiva @valeriadepaiva.bsky.social · Mar 20
Women in Logic 2025 call for papers is out! Check sites.google.com/view/wil2025...
4 6
Reposted by CU Boulder CS Theory
sophie.huiberts.me
Sophie Huiberts @sophie.huiberts.me · Mar 16
June 3-6: MIP USA
July 1-3: MIP Europe

Tell your friends, tell your students, tell your friends' students!
2 8
bouldertheory.bsky.social
CU Boulder CS Theory @bouldertheory.bsky.social · Mar 14
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
Home - Spencer Peters
spencerpeters.io
1
Reposted by CU Boulder CS Theory
tcsplus.bsky.social
TCS+ @tcsplus.bsky.social · Mar 11
📢 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...
TCS+ RSVP: Tom Gur (2025/03/19)
Title: A Zero-Knowledge PCP Theorem
forms.gle
7 8
Reposted by CU Boulder CS Theory
ccanonne.github.io
Clément Canonne @ccanonne.github.io · Mar 6
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!
1 11 32
Reposted by CU Boulder CS Theory
womeninlogic.bsky.social
Women In Logic @womeninlogic.bsky.social · Mar 4
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....
Welcome! You are invited to join a meeting: Women in Logic Online with Sonja Smets. After registering, you will receive a confirmation email about joining the meeting.
Welcome! You are invited to join a meeting: Women in Logic Online with Sonja Smets. After registering, you will receive a confirmation email about joining the meeting.
tuwien.zoom.us
1 2
bouldertheory.bsky.social
CU Boulder CS Theory @bouldertheory.bsky.social · Mar 4
(Are we always excited? Yes. Will it ever be less exciting after having hosted hundreds of talks? We hope not!)
1
bouldertheory.bsky.social
CU Boulder CS Theory @bouldertheory.bsky.social · Mar 4
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
"Annulus with many spikes" A triangulation of an annulus, with the dual graph overlayed on top of the triangulation, and surrounded by a red blob where some part of the blob seem to wind in and around the edges of the graph.
1 1 6
Reposted by CU Boulder CS Theory
rrwilliams.bsky.social
Ryan Williams @rrwilliams.bsky.social · Mar 1
The STOC 2025 Theory Fest is looking for workshop proposals!
Apply here:
stoc2025theoryfest.netlify.app
Deadline is March 9th, so act fast!
Vite + React + TS
stoc2025theoryfest.netlify.app
2 7
Reposted by CU Boulder CS Theory
rrwilliams.bsky.social
Ryan Williams @rrwilliams.bsky.social · Feb 24
I've posted a lightly revised version (mostly revising the discussion at the end) to ECCC
eccc.weizmann.ac.il/report/2025/...
2 5 21
Reposted by CU Boulder CS Theory
tomgur.bsky.social
Tom Gur @tomgur.bsky.social · Jan 4
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!
onlineparallels.bsky.social
Online Parallels (mastodon @onlineparallels) @onlineparallels.bsky.social · Jan 3
Are you a TCS researcher who wants to attend #ITCS25 but faces barriers (such as insufficient travel funding or #visa issues)? Consider attending our online parallel event here! More info: sites.google.com/view/itcs202...
#OnlineParallels
ITCS'25 online parallel
What we do Welcome! This site is about an online parallel event for the conference ITCS'25 that aims to provide an inclusive platform for the TCS researchers unable to attend the conference in person....
sites.google.com
5 10