iiinova — where your digital self keeps evolving

Reposted by CU Boulder CS Theory

Joshua Grochow @joshuagrochow.bsky.social · 04/10/2026

U Colorado Boulder Computer Science is hiring in #Quantum Computation, including: - Quantum CS Theory - Applications of QC to important or emerging areas Details: jobs.colorado.edu/jobs/JobDeta... Pls help spread the word, and reach out to me if you have questions. #🧮 #AcademicSky #TCSSky

jobs.colorado.edu

Tenure-Track Faculty in Quantum Computation

1149

Reposted by CU Boulder CS Theory

Gülce @gkardesd.bsky.social · 30/09/2026

Also, I learned recently that Or Meir gave a wonderfully accessible talk at Cambridge on a recent work of mine with Ben Rossman on chopping games (arxiv.org/abs/2609.01759), and brought together a few strands of top-down lower bounds.

youtube.com

Prof. Or Meir | On Top-Down Lower Bound Techniques for Constant-Depth Circuits

YouTube video by INI Seminar Room 1

093

Reposted by CU Boulder CS Theory

Women In Logic @womeninlogic.bsky.social · 29/09/2026

🚨NEW TALK ALERT🚨 Proof-Theoretic Semantics Seminar Series Speaker: Maria Osório Costa (University of Lisbon; University College London) Title: "Bilateral Proofs and Refutations" Day/time: Monday, October 26, 12pm (UTC+0) To receive zoom link, subscribe: groups.google.com/g/pts-network/

groups.google.com

PTS Network - Google Groups

032

Reposted by CU Boulder CS Theory

Clément Canonne @ccanonne.github.io · 29/09/2026

If you're in #TheoreticalCS and on the postdoc job market, now or soon: this opportunity to work with Tom Gur (@tomgur.bsky.social) on "cutting-edge research on the interplay of theoretical computer science, mathematics, and quantum mechanics" sounds amazing: www.cam.ac.uk/jobs/researc...

cam.ac.uk

Research Assistant/Associate in Theoretical Computer Science (Fixed Term)

Fixed-term: The funds for this post are available for 1 year.

1226

Reposted by CU Boulder CS Theory

Clément Canonne @ccanonne.github.io · 29/09/2026

"Well, that's just, like, your opinion, man." (remotely attending the Simons Institute's Karp Distinguished Lecture by @booleananalysis.bsky.social) @simonsinstitute.bsky.social

Ryan O'Donnell's (almost) favorite expander graph

2213

Reposted by CU Boulder CS Theory

Gülce @gkardesd.bsky.social · 29/08/2026

New on the low-depth complexity of Group Isomorphism: the first nontrivial circuit lower bounds and quasipoly-size depth-2 1/2 upper bounds -- departing from the generator-enumerator approach underlying prior low-depth work: instead we use composition series, group extensions, & short presentations.

arxiv.org

Group Isomorphism and the Polylogarithmic-Time Hierarchy: Depth-2$\frac{1}{2}$ Circuits and Lower Bounds

In this paper, we investigate the low-depth circuit complexity of Group Isomorphism in the multiplication (Cayley) table model. We prove the first circuit lower bounds for Group Isomorphism: namely, w...

2196

Reposted by CU Boulder CS Theory

Clément Canonne @ccanonne.github.io · 16/07/2026

The list of accepted papers at #FOCS2026 is out! sanjeevkhanna.org/FOCS2026_Acc...

sanjeevkhanna.org

FOCS 2026 – Accepted Papers

12910

Reposted by CU Boulder CS Theory

Women In Logic @womeninlogic.bsky.social · 13/07/2026

10th Women in Logic (WiL’26), 24-25 July 2026, Lisbon, Portugal. Program: womeninlogic.org/workshops/20... Register to participate online: ucl.zoom.us/webinar/regi... WiL'26 Chairs: Huimin Dong huimin@logic.at, Anela Lolic anela@logic.at, and Elaine Pimentel e.pimentel@ucl.ac.uk.

womeninlogic.org

WiL 2026 Programme – Women in Logic

1116

CU Boulder CS Theory @bouldertheory.bsky.social · 13/07/2026

Hybrid CS Theory Seminar today (2026-07-13) Excited to have Jack Stade (U. Copenhagen) presenting "The Boundary-Boundary Art-Gallery Problem is in NP" (which won Best Student Paper at STOC this year) www.colorado.edu/cs-theory/th... #MathSky #TCSSky #algorithms #geometry #ComputationalComplexity

A (non-convex) polygonal region (indicative of a strangely-shaped "art gallery"), vaguely triangular-shaped with big bumps at the corners, and smaller, long thin spiky bumps off of those. Three dots are placed, one near each corner of the triangle, colored red, green, and blue respectively. Dashed arrows from the dots to opposite walls indicate extremal lines of sight, and walls are colored corresponding to which dot can see them. Because of the bumps and spikes, which dot can see which wall is a complicated intermesh of the three colors.

063

CU Boulder CS Theory @bouldertheory.bsky.social · 30/06/2026

Hybrid CS Theory Seminar this Thurs 2026-07-02! Excited to have Evelyn Warton (Oregon State) presenting "Inferring Graph Structures from Resistance Distances" www.evelynw.xyz www.colorado.edu/cs-theory/th... #MathSky #TCSSky #algorithms #combinatorics

Two grids filled with colored squares.

The left grid is mostly full of green squares, with a few random-looking squares colored black.

The right grid is filled "oppositely": the squares that are black in the left are blue in the right, and the squares that are green in the left are black in the right.

Below the squares is the mathematical text {L|subscript-K, R|subscript-U}

152

Reposted by CU Boulder CS Theory

Lance Fortnow @lance.fortnow.com · 29/06/2026

Celebration for Avi Wigderson's retirement together with 30 years of the Computer Science and Discrete Mathematics (CSDM) program at the Institute for Advanced Study next June. www.ias.edu/math/eve...

0176

Reposted by CU Boulder CS Theory

arxiv cs.CC @arxiv-cs-cc.bsky.social · 26/06/2026

Joshua A. Grochow, Jacob Urisman Graph Isomorphism and Representation Theory arxiv.org/abs/2606.26244

0152

Reposted by CU Boulder CS Theory

arXiv cs.DS Data Structures and Algorithms @csds-bot.bsky.social · 18/06/2026

Huck Bennett, Kyle Fridberg: On (Non-)Isomorphism of Self-Dual Lattices and Codes arxiv.org/abs/2606.18662 arxiv.org/pdf/2606.18662 arxiv.org/html/2606.18662

041

Reposted by CU Boulder CS Theory

Nutan Limaye @nutanlimaye.bsky.social · 04/06/2026

Since today Bipartite Perfect Matching is in NC. The proof uses connections between coding theory and Hall's theorem. Presented at WACT 2026. Yay!!!

2498

Reposted by CU Boulder CS Theory

Nutan Limaye @nutanlimaye.bsky.social · 02/06/2026

WACT 2026 in Copenhagen from Jun 2 to Jun 5 (started today!). Webpage: sites.google.com/view/wact202... YouTube channel: www.youtube.com/@WACT2026/pl...

1154

Reposted by CU Boulder CS Theory

Lance Fortnow @lance.fortnow.com · 04/06/2026

The 2026 Gödel Prize is awarded to Ilias Diakonikolas, Gautam Kamath, Daniel Kane, Jerry Li, Ankur Moitra, and Alistair Stewart for Robust Estimators in High Dimensions without the Computational Intractability Paper: doi.org/10.1137/17M1... Citation: www.sigact.org/prize...

doi.org

Robust Estimators in High-Dimensions Without the Computational Intractability | SIAM Journal on Computing

We study high-dimensional distribution learning in an agnostic setting where an adversary is allowed to arbitrarily corrupt an $\varepsilon$-fraction of the samples. Such questions have a rich hist...

0236

Reposted by CU Boulder CS Theory

School of Computer Science, University of Sydney @sydneycompsci.bsky.social · 01/06/2026

We're hiring! As part of the "Women in Engineering" initiative at #USyd, the School of Computer Science is hiring women-identifying academics at Lecturer, Senior Lecturer, and A/Professor levels! (≈Asst, Assoc, and full prof) ⏰ Apply by July 13 (Sydney): usyd.wd105.myworkdayjobs.com/en-US/USYD_E...

usyd.wd105.myworkdayjobs.com

Women in Engineering: Continuing (Tenure-Track) Academic Positions for Women, Faculty of Engineering, The University of Sydney

Join a growing Faculty and be part of a University that places amongst the world’s best teaching and research institutions Located in the heart of Sydney’s bustling inner west quarter, close to beache...

01013

Reposted by CU Boulder CS Theory

Marcel Keller @mkskeller.bsky.social · 05/06/2026

UNSW Sydney is hiring an associate professor and a lecturer in cryptography, and the description explicitly mentions *secure computation*. Didn't you want to live in the sunniest of the most livable cities in the world?

external-careers.jobs.unsw.edu.au

Associate Professor in Cryptography

Join an organisation that is shaping the future direction of cryptography and secure computation in Australia, in a senior academic role that combines research leadership, strategic contribution, and ...

166

Reposted by CU Boulder CS Theory

Adithya Bhaskara @adithyacolorado.bsky.social · 02/05/2026

A great sunrise hike at NCAR to finish off undergrad! Thank you, @bouldertheory.bsky.social, and see you soon, @csail.mit.edu!

051

Reposted by CU Boulder CS Theory

Joshua Grochow @joshuagrochow.bsky.social · 22/04/2026

ICALP 2026 accepted papers list is out! icalppodcspaa2026.cs.rhul.ac.uk/icalp-accept...

icalppodcspaa2026.cs.rhul.ac.uk

ICALP: Accepted Papers

051

CU Boulder CS Theory @bouldertheory.bsky.social · 21/04/2026

Online CS Theory Seminar this Fri 2026-04-24! We're excited to have Bruno Pasqualotto Cavalar (Oxford) presenting "Boolean Circuit Complexity and Two-Dimensional Cover Problems" brunopc.github.io www.colorado.edu/cs-theory/th... #TCSSky #MathSky #Complexity #Combinatorics

Grid with columns labeled R_1,...,R_u,...,R_N,C_1,...,C_v,...,C_N,G_1,...,G_t

Row labeled by (u,v) with 0s and 1s filled in

Each column has an arrow at the bottom going through a box labeled F, outputting (in order) F(R_1),...,F(R_u), ..., ... F(G_t)

The table is labeled overline-G

041

Reposted by CU Boulder CS Theory

Huck Bennett @huckbennett.bsky.social · 19/04/2026

This is very nice recognition of Hal Gabow! Hal spent his whole career as faculty at CU Boulder, and his legacy looms large for us. (Hal retired in 2008, and I unfortunately have never gotten a chance to meet him.)

153

CU Boulder CS Theory @bouldertheory.bsky.social · 12/04/2026

Hybrid CS Theory Seminar this Fri 2026-04-17! We're excited to have CU Boulder's own János Engländer presenting his work on the "Tree builder random walk" sites.google.com/view/england... www.colorado.edu/cs-theory/th... #MathSky #TCSSky #ComplexNetworks

A graph (a.k.a. network) that is a tree (connected, no cycles), with one vertex in the middle colored red.

0103

CU Boulder CS Theory @bouldertheory.bsky.social · 09/04/2026

Online CS Theory Seminar this Fri 2026-04-10! We're excited to have Martin Kreuzer (Uni. Passau) presenting "From Code Equivalence to Polynomial Isomorphism" www.digital.uni-passau.de/en/profiles/... www.colorado.edu/cs-theory/th... #MathSky #TCSSky #complexity #AlgebraicGeometry

Photograph portrait of Martin Kreuzer. He is smiling, dressed formally with a bowtie, on a concrete walkway with metal railing, with a metallic-looking building in the background, and vibrant green trees in between.

0103

Reposted by CU Boulder CS Theory

Huck Bennett @huckbennett.bsky.social · 03/04/2026

Congratulations to fantastic @bouldertheory.bsky.social undergraduate @adithyacolorado.bsky.social! I've had the pleasure of getting to work with Adithya during his time at CU, and am very excited to hear about his work going forward.

191

CU Boulder CS Theory @bouldertheory.bsky.social · 26/03/2026

Online CS Theory Seminar this Fri 2026-03-27! We're excited to have Eric Samperton (Purdue Uni.) presenting "Complexity of Algebraic Problems in Low-Dimensional Topology" www.math.purdue.edu/~esampert/ www.colorado.edu/cs-theory/th... #MathSky #TCSSky #complexity #topology

A diagram with several parts linked by arrows and the statement of a theorem.

Theorem: The trivial sublink problem is NP-hard.

Diagram:
A of a graph (network) on 5 vertices with 5 distinct colors, along with its 5x5 adjacency matrix (0s and 1s)
With an arrow that says "Build braid word" to a 5-strand braid, where each of the five strands has a color corresponding to one of the 5 vertices.
An arrow from the braid that say s"Take trace closure of braid (and simplify greedily)"
Pointing to a 5-component link, where each component has a color corresponding to the color of one of the strands.

0174

CU Boulder CS Theory @bouldertheory.bsky.social · 17/02/2026

Hybrid CS Theory Seminar this Fri 2026-02-20! We're excited to have Udi Wieder (Apple) presenting "Uncertainty Quantification Beyond Calibration" udiwieder.wordpress.com www.colorado.edu/cs-theory/th...

Stick figure drawing saying holding up an X-ray of a hand saying "What does that mean? How much error should I expect? Where does the uncertainty come from?" with an arrow pointing to the right. (Arrow may not be relevant to the image.)

073

CU Boulder CS Theory @bouldertheory.bsky.social · 23/11/2025

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

080

CU Boulder CS Theory @bouldertheory.bsky.social · 28/10/2025

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.

083

Reposted by CU Boulder CS Theory

FOCS 2026 @focs2026.bsky.social · 27/10/2025

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

013

Reposted by CU Boulder CS Theory

Sophie Huiberts @sophie.huiberts.me · 27/10/2025

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.

1201

Reposted by CU Boulder CS Theory

Clément Canonne @ccanonne.github.io · 27/10/2025

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

usyd.wd105.myworkdayjobs.com

Multiple Continuing (Tenure-Track) Academic Positions, School of Computer Science, Faculty of Engineering, The University of Sydney

Join a thriving Faculty of Engineering at a University ranked amongst the world’s best teaching and research institutions Located in the heart of Sydney’s bustling inner west quarter, close to beaches...

1134

CU Boulder CS Theory @bouldertheory.bsky.social · 17/10/2025

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

072

Reposted by CU Boulder CS Theory

arxiv math.AC @arxiv-math-ac.bsky.social · 14/10/2025

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

0102

Reposted by CU Boulder CS Theory

Sophie Huiberts @sophie.huiberts.me · 15/10/2025

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

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.

0111

Reposted by CU Boulder CS Theory

School of Computer Science, University of Sydney @sydneycompsci.bsky.social · 01/10/2025

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

0118

Reposted by CU Boulder CS Theory

Clément Canonne @ccanonne.github.io · 15/11/2024

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]

3859

Reposted by CU Boulder CS Theory

Quanta Magazine @quantamagazine.org · 16/10/2025

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

06213

Reposted by CU Boulder CS Theory

ePrint Updates @eprint.ing.bot · 17/10/2025

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.

021

Reposted by CU Boulder CS Theory

ePrint Updates @eprint.ing.bot · 17/10/2025

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.

031

Reposted by CU Boulder CS Theory

ePrint Updates @eprint.ing.bot · 17/10/2025

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.

021

Reposted by CU Boulder CS Theory

ACM FAccT @facct.bsky.social · 17/10/2025

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 →

facctconference.org

ACM FAccT - 2026 CFP

12117

Reposted by CU Boulder CS Theory

Joshua Grochow @joshuagrochow.bsky.social · 12/10/2025

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

MathJobs from the the American Mathematical Society

Mathjobs is an automated job application system sponsored by the AMS.

1104

Reposted by CU Boulder CS Theory

Joshua Grochow @joshuagrochow.bsky.social · 03/10/2025

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

jobs.colorado.edu

Tenure-Track Faculty in Quantum Computing

092

Reposted by CU Boulder CS Theory

Sophie Huiberts @sophie.huiberts.me · 03/10/2025

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

arxiv.org

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

1152

Reposted by CU Boulder CS Theory

Huck Bennett @huckbennett.bsky.social · 02/10/2025

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!

jobs.colorado.edu

Tenure-Track Faculty in Quantum Computing

0158

CU Boulder CS Theory @bouldertheory.bsky.social · 29/09/2025

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

bcamath.org

Danillo Barros de Souza | BCAM - Basque Center for Applied Mathematics

Postdoctoral Fellow at BCAM.

153

Reposted by CU Boulder CS Theory

TCS+ @tcsplus.bsky.social · 27/09/2025

📢 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

forms.gle

TCS+ RSVP: Janani Sundaresan (2025/10/08)

Title: Distributed Triangle Detection is Hard in Few Rounds

165

CU Boulder CS Theory @bouldertheory.bsky.social · 15/07/2025

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

021