Two associate professor (maître·sse de conférences) positions will soon open at the department of computer science and IRIF (@IRIF) at Université Paris Cité. Applications with a background in theoretical computer science (including both `track A' and `track B') are sought. This is a great scientific environment in Paris, France.

🗓️Important dates:
1. Application deadline: Apr. 3, 2026 (16:00 CEST) on the French `odyssee' application platform
2. Notifications for interviews should be received on May 5. 2026
3. Interviews take place in May 18–19, 2026
4. Positions start on Sept. 1, 2026

🔗 https://www.irif.fr/postes/universite

⚠️ Notes:
* Contact people at the department and at IRIF to prepare your application
* Don't forget to apply to both positions
* Some fluency in French is mandatory for these positions: if hired, you'll be teaching in front of a French-speaking class in September.

#academicJobs #wearehiring #theoreticalComputerScience #campagne #esr #universite

#Mathematics #GroupTheory #Algebra #TheoreticalComputerScience

In my study (a while ago) I learned about Σ Algebras (theoretical computer science).
Then later, I learnt in math there are σ Algebras, which seems sort of the same thing.
Today I'm curious about group theory, and groups are also sort of the same thing.

Can anyone tell me what's the difference? Between Σ Algebras, σ Algebras, and groups?

“Representation shapes what seems possible, even when no one says it out loud. I feel so incredibly lucky to have crossed paths with (...) incredible women.” - Surya Mathialagan

➡️ Find her full story at https://hermathsstory.eu/surya-mathialagan/

#Cryptography #USA #Math #PhD #TheoreticalComputerScience #hermathsstory

I wonder whether "fusion trees with multiple roots" exist

what I know after a quick search

• there is a bonsai technique concerning roots of fusion trees
• there is a minecraft modpack called fusion forest
• there is a company called b-forest
• there is a famous counter strike player named forest
• there is a subfield named forest informatics
• there is a greek thing named b dag

#tcs #theoreticalComputerScience #cs #research

People say it's a misconception that quantum computers can evaluate a function on all its possible inputs in parallel. But actually a lot of quantum algorithms do begin by applying a function to a superposition of all possible inputs. It's just that after that point you need to do some difficult linear algebra and you can't always extract the information you want.

In fact, you can define a lot of important complexity classes in this way. The set of problems solvable in polynomial time with an oracle that evaluates a given circuit on all its possible inputs and tells you …

P: … nothing.
BPP: … a randomly chosen output.
PP: … a majority output.
NP: … if any of the outputs is nonzero.
co-NP: … if all of the outputs are nonzero.
PSPACE: … a fixed point.

#Math #Maths #Mathematics #ComputerScience #TheoreticalComputerScience #Quantum #QuantumComputing

Is there a meaningful way to characterize some "fastest growing function", subject to particular computational limitations? (I answered a question today that asked if all computable functions have polynomial bounds, which they obviously don't.)

We can't ask for the fastest-growing function in FP, because the composition of polynomial runtimes is polynomial. So if f(x) is in FP, so is the faster-growing f(f(x)).

Could we identify the fastest-growing function (using binary) in DTIME(n^2)? It seems like it would be something like "given an n-bit input, write n^2 1's after the input". So if the input was 2^a, we'd get 2^a * 2^(a^2) + (2^(a^2+1) - 1) as output.

But, strictly speaking, there would be a little bit of overhead meaning we couldn't do quite that well. The algorithm above is in DTIME(O(n^2)) but not DTIME(n^2). So it feels like there is a sequence of functions that converges on this one, but there might not be any best possible. And if we permit O(n^2) we're back to not having any fastest-growing function again because we can just slap bigger multiples on our allowed runtime.

So, is there a nontrivial class of computable functions that has an unambiguously fastest-growing member?

#TheoreticalComputerScience