EATCSThe Spring issue of the EATCS Bulletin is now available!
Laurent Feuilloley
chaFinally, we have the preprint of a result I am so proud of:
http://arxiv.org/abs/2501.14899
It is about deciding some stuff about regular languages and logic. More precisely, if a language can be defined with first order formulas with a fixed number of quantifiers alternations.
It settles a problem open since 1971 :) and on which my PhD advisors and their advisors worked on.
The Alternation Hierarchy of First-Order Logic on Words is Decidable
We show that for any $i > 0$, it is decidable, given a regular language, whether it is expressible in the $Σ_i[<]$ fragment of first-order logic FO[<]. This settles a question open since 1971. Our main technical result relies on the notion of polynomial closure of a class of languages $\mathcal{V}$, that is, finite unions of languages of the form $L_0a_1L_1\cdots a_nL_n$ where each $a_i$ is a letter and each $L_i$ a language of $\mathcal{V}$. We show that if a class $\mathcal{V}$ of regular languages with some closure properties (namely, a positive variety) has a decidable separation problem, then so does its polynomial closure Pol($\mathcal{V}$). The resulting algorithm for Pol($\mathcal{V}$) has time complexity that is exponential in the time complexity for $\mathcal{V}$ and we propose a natural conjecture that would lead to a polynomial time blowup instead. Corollaries include the decidability of half levels of the dot-depth hierarchy and the group-based concatenation hierarchy.
Residual Entropy (I'VE MOVED!)
Complexity theory question:
NP-Hard is the set of all problems “at least as hard as the hardest problems in NP”
Is there an analogous “at least as hard as the hardest *decideable* problems”?
Like is there a class “Decideable-Hard”?
[ boosts appreciated :) ]
Sophie Huibertsthe videos for stoc are out. i heartily recommend checking out ian's talk:
https://www.youtube.com/watch?v=pWT4krti5bM
the two of us work in different subfields of cs theory but we spent a long time chatting about ways to make paper talk videos more engaging. i made an attempt at this with my own video last year, but ian takes it to an enviable new level. absolutely knocked it out of the park
STOC24 7 C 2 Tree Evaluation is in Space O(log n log log n)
New position new #introduction
I am Sophie and I prove theorems about algorithms. My workplace is LIMOS in beautiful Clermont-Ferrand 🇫🇷 where I work as a CNRS researcher.
Mathematically speaking, I like convex polyhedra and mixed integer linear programming.
🏳️⚧️
#optimization #cstheory #orms
Sasho Nikolov@benbenbrubaker @rrwilliams @tomgur @boazbaraktcs @joshuagrochow @ccanonne #CSTheory is an alternative to #TCS. No great alternative to #ComputationalComplexity that I can think of. Maybe #AlgoComplexity?
Sebastian ForsterNew manuscript on #arXiv: "Deterministic Incremental APSP with Polylogarithmic Update Time and Stretch". Joint work with Yasamin Nazari and Maximilian Probst Gutenberg
Deterministic Incremental APSP with Polylogarithmic Update Time and Stretch
We provide the first deterministic data structure that given a weighted undirected graph undergoing edge insertions, processes each update with polylogarithmic amortized update time and answers queries for the distance between any pair of vertices in the current graph with a polylogarithmic approximation in $O(\log \log n)$ time. Prior to this work, no data structure was known for partially dynamic graphs, i.e., graphs undergoing either edge insertions or deletions, with less than $n^{o(1)}$ update time except for dense graphs, even when allowing randomization against oblivious adversaries or considering only single-source distances.
#introduction
Hi all! I am a postdoc at Columbia in NYC, doing theoretical computer science #tcs #CStheory and thinking about optimization #orms.
Hi all! I am a postdoc at Columbia in NYC, doing theoretical computer science #tcs #CStheory and thinking about optimization #orms.