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
Reposted by CU Boulder CS Theory
focs2025.bsky.social
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!)
October 27, 2025 at 11:12 PM
Reposted by CU Boulder CS Theory
sophie.huiberts.me
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.
October 27, 2025 at 1:43 AM
Reposted by CU Boulder CS Theory
ccanonne.github.io
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...
October 27, 2025 at 7:44 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
Reposted by CU Boulder CS Theory
arxiv-math-ac.bsky.social
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
October 14, 2025 at 4:05 AM
Reposted by CU Boulder CS Theory
sophie.huiberts.me
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!
TheoretiCS - Homepage
TheoretiCS is a Diamond Open Access electronic journal covering all areas of Theoretical Computer Science (TCS). Access to all papers is free. Authors are not required to pay any publication fees or article processing charges, and retain copyright.
theoretics.episciences.org
October 15, 2025 at 11:19 AM
Reposted by CU Boulder CS Theory
sydneycompsci.bsky.social
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...
The School of Computer Science at The University of Sydney (Sydney, Australia) invites applications for several academic positions at all levels with demonstrable strong research experience in, but not limited to, the following areas, with particular focus on science, medical and societal applications: - Computer Systems and Computing Infrastructures - Cybersecurity and Trustworthy Digital Systems - Machine Learning and Artificial Intelligence - Robotics and Autonomous Systems
October 1, 2025 at 8:25 PM
Reposted by CU Boulder CS Theory
ccanonne.github.io
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]
Table of contents of the monograph
November 15, 2024 at 8:02 PM
Reposted by CU Boulder CS Theory
quantamagazine.bsky.social
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-...
October 16, 2025 at 12:45 PM
Reposted by CU Boulder CS Theory
theory.report
Postdoc at Georgia Tech (apply by December 1, 2025)
The Algorithms and Randomness Center (ARC) at Georgia Tech seeks postdocs for 2-year positions beginning Fall 2026. ARC postdocs can work with any ARC-affiliated faculty in CS, Math, or ISYE. To apply, please send a cover letter, CV, research statement, and contact information for three references to the email [email protected] . For full consideration, please apply by 12/1/2025. Website: https://arc.gatech.edu/postdocs/ Email: [email protected] By shacharlovett
cstheory-jobs.org
October 16, 2025 at 3:48 PM
Reposted by CU Boulder CS Theory
eprint.ing.bot
A Simple and Efficient One-Shot Signature Scheme (Andrew Huang, Vinod Vaikuntanathan) ia.cr/2025/1906
Abstract. One-shot signatures (OSS) are a powerful and uniquely quantum cryptographic primitive which allows anyone, given common reference string, to come up with a public verification key pk and a secret signing state $\ket{\mathsf{sk}}$. With the secret signing state, one can produce the signature of any one message, but no more. In a recent breakthrough work, Shmueli and Zhandry (CRYPTO 2025) constructed one-shot signatures, either unconditionally in a classical oracle model or assuming post-quantum indistinguishability obfuscation and the hardness of Learning with Errors (LWE) in the plain model. In this work, we address the inefficiency of the Shmueli-Zhandry construction which signs messages bit-by-bit, resulting in signing keys of Θ(λ⁴) qubits and signatures of size Θ(λ³) bits for polynomially long messages, where λ is the security parameter. We construct a new, simple, direct, and efficient one-shot signature scheme which can sign messages of any polynomial length using signing keys of Θ(λ²) qubits and signatures of size Θ(λ²) bits. We achieve corresponding savings in runtimes, in both the oracle model and the plain model. In addition, unlike the Shmueli-Zhandry construction, our scheme achieves perfect correctness. Our scheme also achieves strong signature incompressibility, which implies a public-key quantum fire scheme with perfect correctness among other applications, correcting an error in a recent work of Çakan, Goyal and Shmueli (QCrypt 2025) and recovering their applications. Image showing part 2 of abstract.
October 17, 2025 at 1:56 AM
Reposted by CU Boulder CS Theory
eprint.ing.bot
Weak Instances of the Inverse Matrix Code Equivalence Problem (Jesús-Javier Chi-Domínguez) ia.cr/2025/1909
Abstract. Nowadays, the Matrix Code Equivalence Problem shows potential applicability in constructing efficient and secure advanced digital signatures, focusing on linkable ring signatures, threshold signatures, and blind signatures. Current constructions of these advanced signatures rely on relaxed instantiations of the Matrix Code Equivalence Problem: given two pairs of equivalent matrix codes, find (if it exists) the secret isometry connecting the pairs. For example, the linkable ring signature construction by Chou et al. (AFRICACRYPT, 2023) builds on top of the Inverse Matrix Code Equivalence Problem: given three equivalent matrix codes, where one pair of the codes is connected by the secret isometry and another by the inverse of that isometry, find the secret isometry. This paper studies the Inverse Matrix Code Equivalence Problem, focusing on the family of instances where the secret isometry is (skew) symmetric. Our main contribution corresponds to a new algorithm for solving these instances of the Inverse Matrix Code Equivalence Problem. As an implication, we identify weak instances of this kind of instantiation of the Inverse Matrix Code Equivalence Problem, for around 70% of the possible parameter set choices (i.e., code dimension k, and code lengths m and n), our algorithm runs (heuristically) in polynomial time. In addition, our results spotlight an additional 35% of parameter sets where the best algorithm for solving the Matrix Code Equivalence Problem, proposed by Couvreur and Levrat (Crypto, 2025), does not apply. Our results have a crucial security impact on the recent blind signature construction proposed by Kuchta, LeGrow, and Persichetti (ePrint IACR, 2025), whose security is closely related to the hardness of solving these kinds of instances of the Inverse Matrix Code Equivalent Problem. Image showing part 2 of abstract.
October 17, 2025 at 2:12 AM
Reposted by CU Boulder CS Theory
eprint.ing.bot
Unambiguous SNARGs for P from LWE with Applications to PPAD Hardness (Liyan Chen, Cody Freitag, Zhengzhong Jin, Daniel Wichs) ia.cr/2025/1913
Abstract. We construct the first unambiguous succinct non-interactive arguments (SNARGs) for P and incrementally verifiable computation (IVC) for P from the polynomial hardness of learning with errors (LWE). Unambiguity guarantees that it is computationally hard to find two distinct accepting proofs for the same statement. As an application, we establish the first PPAD hardness result based on the polynomial hardness of LWE combined with a widely believed complexity assumption. Central to our approach is a new notion of rate-1 witness-unambiguous batch arguments for NP, which we give the first construction from the polynomial hardness of LWE. This notion may be of independent interest.
October 17, 2025 at 2:12 AM
Reposted by CU Boulder CS Theory
facct.bsky.social
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 →
ACM FAccT - 2026 CFP
facctconference.org
October 17, 2025 at 1:27 PM
Reposted by CU Boulder CS Theory
joshuagrochow.bsky.social
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...

#🧮
MathJobs from the the American Mathematical Society
Mathjobs is an automated job application system sponsored by the AMS.
www.mathjobs.org
October 12, 2025 at 12:44 AM
Reposted by CU Boulder CS Theory
joshuagrochow.bsky.social
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
October 3, 2025 at 6:05 PM
Reposted by CU Boulder CS Theory
sophie.huiberts.me
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
October 3, 2025 at 2:14 PM
Reposted by CU Boulder CS Theory
huckbennett.bsky.social
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
October 2, 2025 at 2:40 PM
bouldertheory.bsky.social
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
September 28, 2025 at 11:07 PM
Reposted by CU Boulder CS Theory
tcsplus.bsky.social
📢 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
September 27, 2025 at 9:42 PM
bouldertheory.bsky.social
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...
July 15, 2025 at 7:22 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
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
June 15, 2025 at 4:47 PM