CU Boulder CS Theory

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

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

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

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

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

Table of contents of the monograph

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

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.

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

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.

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

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.

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 →

MathJobs from the the American Mathematical Society Mathjobs is an automated job application system sponsored by the AMS.

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

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

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

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

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

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

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

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

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

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

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