@LaurentFeuilloley The call for papers of the #MFCS2026 conference is now online at https://mfcs2026.irif.fr/#cfp

#cfp #callForPapers #theoreticalComputerScience

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

🎓 Alumni Spotlight: Marco Mondelli
From @EPFL to ISTA, Marco’s journey in Algorithms & Theoretical Computer Science shows the impact of an EDIC PhD. Today, he’s advancing research in algorithms, coding theory, and data science.
"EDIC gave me the mentorship, freedom, and network I needed to pursue research at the highest level."
Are you ready to start your own research journey?
➡️ Discover EDIC PhD
#EDICPhD #PhDlife #AcademicResearch #Algorithms #TheoreticalComputerScience #ResearchOpportunities

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

A plausible breakthrough towards P ⊂ PSPACE
https://www.quantamagazine.org/for-algorithms-a-little-memory-outweighs-a-lot-of-time-20250521/
#TheoreticalComputerScience #ComplexityTheory

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

Just because its turin complete and computable and can define bool/if-else, currying recursion, church numerals and exprs reduce correctly shouldnt mean that it can attribute a computational meaning to an otherwise absurd #math expression
Or should it?
My question is computational meaning even a thing ? If yes , how does that even relate to meaning applied math
I mean the count of 1 , 2, 3 can always be attributed to something g physically measurable
#theoreticalcomputerscience
-- noob

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

P=NP

https://onepolynomial.wordpress.com/2024/10/16/pnp/

#onepolynomial #pnp #pvsnp #pequalnp #cs #computerscience #theoreticalcomputerscience #math #mathematics #proof #new #discovery #result #results #groundbreaking

This Karp Distinguished Lecture at at the Simons Institute by Rocco Servedio on July 10 on "New Directions in Property Testing" looks exciting! Rocco is a fantastic speaker.
https://simons.berkeley.edu/events/new-directions-property-testing-richard-m-karp-distinguished-lecture

The Karp Lectures are public lectures, meant for a broad, general #TheoreticalComputerScience audience. Registration is free, in person or online.

To check your time zone: https://timeanddate.com/worldclock/converter.html?iso=20240710T223000&p1=tz_pt&p2=240&p3=195&p4=179&p5=438&p6=236

Call for papers for the LearnAut (#Learning and #Automata) 2024 workshop co-located with ICALP/LICS/FSCD!

Please consider submitting your work. 😊

"The aim of this workshop is to bring together experts on #FormalLanguageTheory that could benefit from #GrammaticalInference tools, and researchers in grammatical inference who could find new insights for their methods in #TheoreticalComputerScience. [...] We do accept submissions of work recently published, currently under review or work-in-progress."

https://learnaut24.github.io/

📢 Next week (Wed 12/13) on TCS+: at 10am PT/1pm ET, Aaron Bernstein from Rutgers University will speak on "Negative-Weight Single-Source Shortest Paths in Near-linear Time." Join us for the last TCS+ talk of 2023! #Algorithms #TheoreticalComputerScience

Details: https://tcsplus.wordpress.com/2023/12/06/tcs-talk-wednesday-december-13-aaron-bernstein-rutgers-university/

Register (optional): https://docs.google.com/forms/d/e/1FAIpQLSdSrnuZ2jH8KGepSEJ0uz_iCRr7mJtMntIu6ZBsXIhhKovI6A/viewform

In our effort to put courses online, we continue lectures on Algorithmic Lower Bound Course. Now you can watch

Lesson 4-11: Algorithmic Lower Bounds by Mohammad Hajiaghayi - NP-Completeness and Beyond

(FEEL FREE TO SUBSCRIBE TO YOUTUBE @hajiaghayi FOR FUTURE LESSONS Premiering on WEDNESDAYS)

https://youtu.be/VZyffnAb1r0 (Lesson 4: 3-Partition Problem & Proving NP-Hardness)

https://youtu.be/4fCD9_1eQw0 (Lesson 5: Puzzle Problem NP-Hardness & 3-Partition)

https://youtu.be/FIyEj72-UJQ (Lesson 6: 3-SAT Problem & Proving NP-Hardness)

https://youtu.be/tbSJzaKx2pA (Lesson 7: Puzzle Problem NP-Hardness via 3-SAT)

https://youtu.be/voRVebBsh94 (Lesson 8: Fine-grained Subcubic Complexity: Part 1)

https://youtu.be/gRURSM6QARo (Lesson 9: Fine-grained Subcubic Complexity: Part 2)

https://youtu.be/qPw82bTAXkc (Lesson 10: Fine-grained Subquadratic Complexity 1)

https://youtu.be/C6j4avVkI7U (Lesson 11: Fine-grained Subquadratic Complexity 2)

#AlorithmicComplexity,

#3SAT,

#3Partition,

#subquadratic,

#subcubic,

#Finegrained,

#HardnessExploration,

#NP,

#PSPACE,

#NPComplete,

#LogSpace,

#ExponentialComplexity,

#ParallelComputation,

#PvsNP,

#NPSPACE,

#NonDeterministicSpace, hashtag

#SavitchTheorem,

#ComplexityClasses,

#Reductions,

#ImportantProblems,

#CommunicationComplexity, hashtag

#GeometricProblems,

#AlgorithmDesign,

#ComputationalComplexity,

#TheoreticalComputerScience,

#AlgorithmicLowerBounds

For comprehensive handwritten lecture notes on this course, visit the instructor's website:

http://www.cs.umd.edu/~hajiagha/
The course textbook "Computational Intractability: A Guide to Algorithmic Lower Bounds" by Demaine, Gasarch, and Hajiaghayi is available for free at:

https://hardness.mit.edu/

📢 Next week (Wed 9/27) at 10:00am PT, Hanlin Ren from Oxford will give the first TCS+ talk of the season, on "Polynomial-Time Pseudodeterministic Construction of Primes." #TheoreticalComputerScience

Details: https://tcsplus.wordpress.com/2023/09/20/tcs-talk-wednesday-september-27-hanlin-ren-university-of-oxford/

Register (optional): https://docs.google.com/forms/d/e/1FAIpQLScenFfBzn6Kl45Y1reJAB08D1V4Sd_z0eQTgG76XsG4lpPV1w/viewform

Here's a really interesting (long) paper on what a theory of computing based on arbitrary physical substrates might look like: http://arxiv.org/abs/2307.15408

"Toward a formal theory for computing machines made out of whatever physics offers: extended version"

Herbert Jaeger, Beatriz Noheda, Wilfred G. van der Wiel (2023)

@bnoheda

#NewPaper #TheoreticalComputerScience #neuromorphic #CogSci #CognitiveScience #VSA #VectorSymbolicArchitecture #HDC #HyperdimensionalComputing #AnalogComputing

Collective #math / #TheoreticalComputerScience memory question: Sometime in the last couple of months I followed a link from Masto to a blog post about computing (in the most general sense) defined as continuous rather than discrete mathematics. This blog post mentioned (with references) that having *partial* functions was essential for computation.

Now I can't find the blog post or references. Any pointers to works explaining why partial functions are essential to computation (or refutation) would be greatly appreciated.

ChatGPT introduces me a branch of #theoreticalComputerScience called "#gameSemantics" today!

#gameTheory

@Jose_A_Alonso #ComputationalComplexity #theoreticalComputerScience #TCS #phdPosition