CU Boulder CS Theory
LightNews LightNews
bouldertheory.bsky.social
CU Boulder CS Theory
@bouldertheory.bsky.social
320 followers 73 following 17 posts
Computer science theory group at the University of Colorado Boulder https://www.colorado.edu/cs-theory/
Posts Replies Media Videos
bouldertheory.bsky.social
Optimization Algorithms for Planar Graphs

On 14 Nov 2025 our sabbatical visitor Philip Klein (Brown University) gave a great hybrid seminar on algorithms for planar graphs!

cs.brown.edu/people/facul...
www.colorado.edu/cs-theory/th...

That's it for this semester - have a good end of semester all!
Map of Boston/Cambridge with a red tour highlighted with several dots along the way. The tour is roughly in the shape of a cycle, but with a few offshoots along the way. Text: The world is flat...but it's not Euclidean! Traveling-salesperson tour in ~~the plane~~ a planar embedded graph
November 23, 2025 at 4:46 PM
bouldertheory.bsky.social
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
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.
October 28, 2025 at 9:38 PM
bouldertheory.bsky.social
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
A grid of 0s and 1s with the 1s highlighted blue One row is circled in red Next to it, a vector q = 0100
October 17, 2025 at 5:16 PM
bouldertheory.bsky.social
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, ...
July 14, 2025 at 5:07 PM
bouldertheory.bsky.social
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.
March 4, 2025 at 7:17 PM
bouldertheory.bsky.social
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...
Table with different calibration measures, indicating which are complete, sound, and how truthful they are. Subsampled Smooth Calibration Error is highlighted as being complete, sound, and (O(1),0)-truthful. Better than everything else in the table except incomparable to Proper Scoring Rules, which are (1,0)-truthful, but Proper Scoring Rules aren't complete. Details of the rest of the table follow All are sound All except for Proper Scoring Rules are complete Truthful values are as follows: Expected Calibration Error, Maximum Swap Regret: 0-Omega(T) gap Smooth Calibration, Distance from Calibration, Interval Calibration, Laplace-Kernel Calibration: 0-Omega(Sqrt(T)) gap U-Calibration Error: O(1)-Omega(Sqrt(T)) gap
November 14, 2024 at 4:11 PM
bouldertheory.bsky.social
Hybrid CS Theory Seminar this Friday 2024-11-08

We're excited to have Xun Gao, CU Boulder Physics's newest prof, speaking on

"#Quantum Supremacy: #Complexity Theory and the Role of Noise"

colorado.edu/cs-theory/th...
Two quantum circuits, one labeled "Ideal RCS" with many gates followed by measurements. The other labeled "noisy RCS" which has little blue dots in between all the gates representing noise
November 5, 2024 at 5:11 PM
bouldertheory.bsky.social
Hybrid CS Theory Seminar this Friday 2024-10-18

We're excited to have Anthony Ostuni from UCSD presenting:

"Locality Bounds for Sampling Hamming Slices​"

based on joint work w/ Daniel M. Kane and Kewen Wu.

aostuni.github.io
colorado.edu/cs-theory/th...

#sampling #complexity #MathSky #CS
A diagram with the top row labeled U^m (uniform distribution on m bits) and the bottom row labeled f(U^m). The labels are in blue. Top row has x1, x2, x3, ... Bottom row has y1, y2, y3, y4, y5, y6, ... Grouped into adjacent pairs with red ovals y1, y3, and y5 have blue circles around them x1 has two black lines coming down from it to y1, y2 Similar lines from x2 to y3, y4 and from x3 to y5, y6 The line from x_1 to y_1 is labeled N(y_1) in red, the line from x_2 to y_3 is labeled N(y_3) in red, the line from x_3 to y_6 (sic!) is labeled N(y_5) in red Below y1 and y2 are the labels x1 and 1-x1 Below y3 and y4 are the labels x2, 1-x2 Below y5 and y6 are x3, 1-x3
October 15, 2024 at 5:40 PM