{"id":473,"date":"2021-03-30T08:47:30","date_gmt":"2021-03-30T06:47:30","guid":{"rendered":"http:\/\/www.ens-lyon.fr\/LIP\/CASH\/?page_id=473"},"modified":"2026-09-29T15:46:40","modified_gmt":"2026-09-29T13:46:40","slug":"seminar-and-reading-group","status":"publish","type":"page","link":"https:\/\/www.ens-lyon.fr\/LIP\/CASH\/?page_id=473","title":{"rendered":"Seminar and reading group"},"content":{"rendered":"\n

Date: Monday 10:30am Lyon Time (unless explicitly stated otherwise)<\/strong>
Location: Salle de conseil (unless explicitly stated otherwise)<\/strong>
Virtual: <\/p>\n\n\n\n

<\/a>https:\/\/rendez-vous.renater.fr\/CASH_Seminar_977b7f-224e4d-ca9a8e<\/a><\/p>\n\n\n\n

\n

Upcoming<\/h2>\n\n\n\n

2026<\/h3>\n\n\n\n
\n

05\/10 – 10:30 CET <\/strong>Victor Deng<\/h4>\n\n\n\n
\n
\n

On the computational complexity of JavaScript regex matching<\/strong><\/p>\n<\/div>\n\n\n\n

\n
Abstract<\/summary>\n

Despite widespread use, the complexity of the matching problem for modern regular expressions languages remains unclear. Previous work proved that an idealized regular expression language with backreferences and lookarounds had PSPACE-complete matching. We extend this work to a real-world regex language by proving that JavaScript regex matching with expanded lower-bounded quantifiers is PSPACE-complete. We then generalize the result: we show that PSPACE-hardness survives the removal of negative lookarounds, and that removing all lookarounds leads to an OptP-complete parsing problem. Our core arguments are formalized in Rocq.<\/p>\n<\/details>\n<\/div>\n<\/div>\n<\/div><\/div>\n<\/div><\/div>\n\n\n\n

\n

Past<\/h2>\n\n\n\n
\n

2026<\/h3>\n\n\n\n
\n

16\/02 – 14:00 CET <\/strong>(Seminar) Alain Ketterlin <\/h4>\n\n\n\n

(Inria CAMUS team, Strasbourg)<\/p>\n\n\n\n

\n
\n

Affine Loop Nests and Integer Polynomials<\/strong><\/p>\n<\/div>\n\n\n\n

\n
Abstract<\/summary>\n

This talk explores connexions between (mostly affine) static control
loop nests and integer-valued polynomials in integer variables. We
first describe a simple and fast algorithm that counts the number of
instructions executed by a (parameterized) affine loop nest of a
slightly restricted class, and use this algorithm to define the
correspondence between the iteration vector and sequential rank of any
instruction instance. We then proceed to define a loop (or kernel)
interpolation technique that coerces one or more loop nests into a
single perfect loop, and use this technique to recognize loops in raw
program traces, or transform and\/or merge compute kernels. This
introduces integer polynomial loops, where bounds, memory access
functions, and other parts of instructions are polynomials rather than
affine; the last part of the talk shows how such loops can be compiled
to produce efficient code. The three parts of the talk rely on a
somewhat unusual representation for integer polynomials, whose
properties provide simple and efficient integration, interpolation,
and differentiation techniques which lie at the heart of the various
algorithms.<\/p>\n<\/details>\n<\/div>\n<\/div>\n<\/div><\/div>\n\n\n\n

\n

23\/02 – 10:30 – 16:15 CET <\/strong>(Seminar) Proof Assistants (Amphi I, Site Monod)<\/h4>\n\n\n\n
\n
\n

See the program<\/a><\/p>\n\n\n\n