BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Google Inc//Google Calendar 70.9054//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
DESCRIPTION:Séminaire de l'IRIF seminar of IRIF
NAME:Séminaire de l'IRIF
REFRESH-INTERVAL:PT4H
TIMEZONE-ID:Europe/Paris
X-WR-CALDESC:Séminaire de l'IRIF seminar of IRIF
X-WR-CALNAME:Séminaire de l'IRIF
X-WR-TIMEZONE:Europe/Paris
BEGIN:VTIMEZONE
TZID:Europe/Paris
X-LIC-LOCATION:Europe/Paris
BEGIN:DAYLIGHT
DTSTART:19700329T020000
RRULE:FREQ=YEARLY;BYDAY=-1SU;BYMONTH=3
TZNAME:CEST
TZOFFSETFROM:+0100
TZOFFSETTO:+0200
END:DAYLIGHT
BEGIN:STANDARD
DTSTART:19701025T030000
RRULE:FREQ=YEARLY;BYDAY=-1SU;BYMONTH=10
TZNAME:CET
TZOFFSETFROM:+0200
TZOFFSETTO:+0100
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
SUMMARY:Ada and Computation - Nachum Dershowitz\, Tel Aviv University
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20160128T103000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20160128T113000
DTSTAMP;VALUE=DATE-TIME:20201028T140300Z
UID:4
DESCRIPTION:Ada Lovelace (born 200 years ago) wrote presciently about digi
tal numerical calculations. She expressed its features poetically: "We may
say most aptly that [Babbage's] Analytical Engine weaves algebraical patt
erns just as the Jacquard loom weaves flowers and leaves." Ada explained t
he generality of digital computation\, saying that "the engine can arrange
and combine its numerical quantities exactly as if they were letters or a
ny other general symbols." We will discuss some of the expected and unexpe
cted consequences of alternate representations of computational data. On t
he other hand\, Ada wrote that "the engine [is] the material expression of
any indefinite function of any degree of generality and complexity." This
we now know was overstating her case. We will discuss the formalization o
f the notion of effective computation and its consequences vis-a-vis compu
tability and complexity of computation.
LOCATION:Amphi Turing
END:VEVENT
BEGIN:VEVENT
SUMMARY:**IRIF expository talks series**: Preserving Software: challenges
and opportunities for the reproductibility of Science ({{seminaires:irif:s
em_irif_20160916_di-cosmo.pdf |click here for the slides}}) - Roberto Di C
osmo\, IRIF
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20160916T103000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20160916T113000
DTSTAMP;VALUE=DATE-TIME:20201028T140300Z
UID:94
DESCRIPTION:A vast amount of modern scientific and technological knowledge
relies on the\nsoftware that we have been collectively writing: deep know
ledge from\nfields like mathematics\, physics\, chemistry\, biology\, medi
cine\, finance and\nsocial sciences is now inextricably embodied into comp
lex software systems\,\nwhich model it at a level of detail that goes way
beyond that of the usual\nscientific publications.\n\nPreserving this soft
ware is of paramount importance to preserve our knowledge.\n\nIt is is a n
ecessary prerequisite to allow the replication of experiments\, which\nis
the foundation of the scientific method\, as well as to ensure our ability
to\nmodify and correct the software components that are constantly being\
nincorporated into critical systems that need to stay in production for de
cades.\n\nIn this talk\, we will review the challenges and opportunities w
e are facing\, and\ndiscuss the role of Open Source as a key enabler.\n\nT
he slides of the talk can be found {{seminaires:irif:sem_irif_20160916_di-
cosmo.pdf | here}}.
LOCATION:Amphi Turing (Bâtiment Sophie Germain)
END:VEVENT
BEGIN:VEVENT
SUMMARY:**IRIF expository talks series **: Logic in Computer Science and
Computer Engineering - Yuri Gurevich\, Microsoft Research
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20161028T103000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20161028T113000
DTSTAMP;VALUE=DATE-TIME:20201028T140300Z
UID:95
DESCRIPTION:In software industry\, engineers do formal logic day in and da
y out\, even though they may not realize that. As a rule\, they have not s
tudied logic. Instead\, they spent a lot of time studying calculus which t
hey use rarely\, if ever. I'll try to illustrate why logic is so relevant
and why it is hard for software engineers to pick it up.\n\n\n\nIMPORTANT
NOTE: For administrative reasons\, those from outside of IRIF who wish\nto
attend the seminar in "Salle 3052" should email by Wednesday 26/10 their
name to \nIrène Guessarian at ig@liafa.univ-paris-diderot.fr .
LOCATION:Salle 3052\, Bâtiment Sophie Germain (SEE NOTE IN THE ABSTRACT)
END:VEVENT
BEGIN:VEVENT
SUMMARY:**IRIF Distinguished Talks Series**: Principles of Probabilistic P
rogramming ({{seminaires:irif:sem_irif_20170303_katoen.pdf |click here for
the slides}}) - Joost-Pieter Katoen\, RWTH Aachen
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20170303T103000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20170303T113000
DTSTAMP;VALUE=DATE-TIME:20201028T140300Z
UID:122
DESCRIPTION:Probabilistic programming is en vogue. It is used to describe\
ncomplex Bayesian networks\, quantum programs\, security protocols and\nbi
ological systems. Programming languages like C\, C#\, Java\, Prolog\,\nSca
la\, etc. all have their probabilistic version. Key features are\nrandom s
ampling and means to adjust distributions based on obtained\ninformation f
rom measurements and system observations. We show some\nsemantic intricaci
es\, argue that termination is more involved than the\nhalting problem\, a
nd discuss recursion and run-time analysis.
LOCATION:Amphi Turing
END:VEVENT
BEGIN:VEVENT
SUMMARY:**IRIF expository talks series**: Primordial database theory revis
ited: are relational algebra\, calculus\, and basic SQL really equivalent?
- Leonid Libkin\, University of Edinburgh
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20170411T103000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20170411T113000
DTSTAMP;VALUE=DATE-TIME:20201028T140300Z
UID:234
DESCRIPTION:We revisit one of the most basic questions of database theory:
the\nequivalence of first-order logic (FO)\, relational algebra (RA)\, an
d\nthe core of SQL. Despite being at the heart of relational theory\,\nthe
se questions do not have satisfactory answers in the literature.\nThe well
known equivalence of FO and RA\, and existing translations\nfrom SQL to R
A\, work only for simple models that fall short of what\nreal databases us
e. Proving results about real SQL\, rather than a\ntheoretical reconstruct
ion\, is hampered by the lack of formal SQL\nsemantics: the Standard is to
o vague for the purpose\, and previous\nattempts at formalizing SQL's sema
ntics made many simplifying\nassumptions that do not hold in real life. On
the logic side\, SQL\nmixes Boolean and 3-valued logics in a way that has
never been properly\nstudied.\n\nOur goal is to fill these surprising gap
s in basic database theory. We\nprovide a formal semantics of the core of
SQL that captures the real language and accounts for many of its\nidiosync
rasies. To justify it as the correct semantics\, we validate it\nexperimen
tally on a large number of randomly generated\nqueries. With this semantic
s\, we formally prove the equivalence of\ncore SQL and RA\, as well as the
extension of 3-valued FO with an\noperator that accounts for SQL's abilit
y to switch back and forth\nbetween Boolean and 3-valued logics. Then\, so
mewhat surprisingly\, we\nshow that this additional operator does not add
expressiveness\, and -\neven more surprisingly - that 3-valued logic does
not add\nexpressiveness even in the presence of nulls.\n\nBased on joint w
ork with with Paolo Guagliardo.
LOCATION:Amphi Turing
END:VEVENT
BEGIN:VEVENT
SUMMARY:**IRIF Distinguished Talks Series**: Hilbert's tenth problem and s
ome other difficult problems ({{ https://logic.pdmi.ras.ru/~yumat/talks/t
alks.php?istate=state_show_talk&iid=1367 | click here for the slides}}) -
Yuri Matiyasevich\, Steklov Institute of Mathematics\, St. Petersburg
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20171110T103000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20171110T113000
DTSTAMP;VALUE=DATE-TIME:20201028T140300Z
UID:300
DESCRIPTION:The undecidability of Hilbert's tenth problem (H10) about Diop
hantine equations \nturned out to be a powerful tool for establishing the
undecidability of many\nother decision problems. The technique developed f
or proving the undecidability\nof H10 gave the possibility to find unexpec
ted relationships between Diophantine equations \nand some other classical
mathematical problems.
LOCATION:Amphi Turing
END:VEVENT
BEGIN:VEVENT
SUMMARY:**IRIF Distinguished Talks Series**: The state of the art in dynam
ic graph algorithms - Monika Henzinger\, University of Vienna
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20180413T103000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20180413T113000
DTSTAMP;VALUE=DATE-TIME:20201028T140300Z
UID:344
DESCRIPTION:A dynamic graph algorithms is a data structure that maintains
a property of a graph while it is modified by edge insertions and deletion
s. The last few years have seen exciting new developments in dynamic graph
algorithms\, namely strong conditional lower bounds and dynamic algorithm
based on the primal-dual approach.
LOCATION:Amphi Turing
END:VEVENT
BEGIN:VEVENT
SUMMARY:**IRIF Distinguished Talks Series**: A computer scientist thinks a
bout the Brain - Christos Papadimitriou\, Columbia University
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20180713T103000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20180713T113000
DTSTAMP;VALUE=DATE-TIME:20201028T140300Z
UID:621
DESCRIPTION:How does the Brain give rise to the Mind? How do neurons and
synapses\, molecules and genes\, evolution and development\, give ri
se to behavior and cognition\, language and intelligence? Despite lightni
ng progress in recording and molecular technology and a deluge of experime
ntal data\, we do not seem to get closer to an answer. This is a talk abo
ut admiring and appreciating the problem\, and proposing a new approach ba
sed on a recognized but little studied intermediate level of Brain computa
tion carried out by the synchronous firing of large and highly interconnec
ted sets of neurons called assemblies. We show that assemblies give rise
to a novel computational system\, and we speculate that they may instrumen
t higher cognitive functions\, such as language and math.
LOCATION:Amphi Turing
END:VEVENT
BEGIN:VEVENT
SUMMARY:**IRIF Distinguished Talks Series**: Atomic Cross-Chain Swaps - M
aurice Herlihy\, Brown University
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20181116T103000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20181116T113000
DTSTAMP;VALUE=DATE-TIME:20201028T140300Z
UID:630
DESCRIPTION:An atomic cross-chain swap is a distributed coordination task
where multiple parties exchange assets across multiple blockchains\, for e
xample\, trading bitcoin for ether. An atomic swap protocol guarantees (1)
if all parties conform to the protocol\, then all swaps take place\, (2)
if some coalition deviates from the protocol\, then no conforming party en
ds up worse off\, and (3) no coalition has an incentive to deviate from th
e protocol. A cross-chain swap is modeled as a directed graph D\, whose ve
rtexes are parties and whose arcs are proposed asset transfers. For any pa
ir (D\,L)\, where D=(V\,A) is a strongly-connected directed graph and L⊂
V a feedback vertex set for D\, we give an atomic cross-chain swap protoco
l for D\, using a form of hashed timelock contracts\, where the vertexes i
n L generate the hashlocked secrets. We show that no such protocol is poss
ible if D is not strongly connected\, or if D is strongly connected but L
is not a feedback vertex set.
LOCATION:Amphithéâtre Pierre-Gilles de Gennes\, Bât. Condorcet
END:VEVENT
BEGIN:VEVENT
SUMMARY:**IRIF Distinguished Talks Series**: Switching lemmas in the 80ie
s and today - Johan Håstad\, Royal Institute of Technology\, Stockholm
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20190412T103000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20190412T113000
DTSTAMP;VALUE=DATE-TIME:20201028T140300Z
UID:631
DESCRIPTION:The first switching lemmas were proved in 1980ies and gave us
lower bounds for the size of small-depth circuits. In particular they gav
e us optimal lower bounds for the size of circuits computing parity and pr
oved that there are functions that have small circuits of depth d\, but re
quire (sub)-exponential size if the depth is restricted to d-1.\n\nSome qu
estions were left open in the 1980ies but have been resolved more recently
. Two such questions are to establish sharp estimates for the best correla
tion with parity and to prove that the just mentioned hierarchy result can
be established in an average case setting. Both these results used new va
riants of the switching lemma.\n\nWe survey these results and give an indi
cation what modifications were needed to obtain the recent results.\n\nIf
time permits we also discuss how yet other switching lemmas can be used to
prove lower bounds for the length of Frege proofs using small-depth formu
las.
LOCATION:Amphi Turing
END:VEVENT
BEGIN:VEVENT
SUMMARY:**IRIF Distinguished Talks Series**: Concurrent Connected Componen
ts - Robert Tarjan\, Princeton University and Intertrust Technologies
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20190318T170000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20190318T180000
DTSTAMP;VALUE=DATE-TIME:20201028T140300Z
UID:819
DESCRIPTION:Finding the connected components of a graph is one of the most
basic graph problems. Although it is easy to find components sequentially
using graph search or a disjoint set union algorithm\, some important app
lications require finding the components of huge graphs\, making sequentia
l algorithms too slow. We describe recent progress on concurrent algorithm
s for this problem. Some simple algorithms seem surprisingly hard to analy
ze\, and claims made in the literature about some of them are false.\n\n\n
\nThis talk is organized in collaboration with the Collège de France.
LOCATION:Amphithéâtre Guillaume Budé - Marcelin Berthelot - Collège d
e France
END:VEVENT
BEGIN:VEVENT
SUMMARY:**IRIF Distinguished Talks Series**: Approximation Algorithms for
Some Geometric Packing/Covering/Routing Problems - [Cancelled] Joseph Mit
chell\, State University of New York at Stony Brook
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20200320T103000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20200320T113000
DTSTAMP;VALUE=DATE-TIME:20201028T140300Z
UID:918
DESCRIPTION:A fundamental class of combinatorial optimization problems inv
olve packing and covering. Examples include maximum independent set\, domi
nating set\, set cover\, hitting set\, etc. Motivated by applications in s
ensor networks and robotics\, natural instances of such problems arise in
geometric situations\, such as covering points with a small number of disk
s\, viewing "art galleries" with a small number of guards or with a mobile
guard on a short route\, packing disks or other shapes within a bounded d
omain\, etc. Almost all of these problems are NP-hard even in simple two-
dimensional settings. The problems get even harder when we take into accou
nt uncertain data\, time constraints for scheduled coverage\, and routing/
connectivity problems in combination with coverage constraints. We discuss
several of these geometric optimization problems from the perspective of
approximation algorithms and we describe some techniques that have led to
new or improved bounds or running times for selected packing\, covering\,
and routing/coverage problems.
LOCATION:Amphi Turing
END:VEVENT
BEGIN:VEVENT
SUMMARY:**IRIF Distinguished Talks Series**: TBA - [Cancelled] Simon Pey
ton Jones\, Microsoft Research [Cambridge\, England]
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20200612T104500
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20200612T114500
DTSTAMP;VALUE=DATE-TIME:20201028T140300Z
UID:928
DESCRIPTION:
LOCATION:Amphi Turing
END:VEVENT
BEGIN:VEVENT
SUMMARY:**IRIF Distinguished Talks Series**: Symmetry and Similarity - [Ca
ncelled] Martin Grohe\, RWTH Aachen University
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20200124T103000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20200124T113000
DTSTAMP;VALUE=DATE-TIME:20201028T140300Z
UID:1065
DESCRIPTION:Symmetry is a fundamental concept in mathematics\, the science
s\, and beyond. Understanding symme\ntries is often crucial for understand
ing structures. In computer science\, we are mainly interes\nted in the sy
mmetries of combinatorial structures. Computing the symmetries of such a s
tructure\n is essentially the same as deciding whether two structures are
the same ("isomorphic"). Algori\nthmically\, this is a difficult task that
has received a lot of attention since the early days o\nf computing. It i
s a major open problem in theoretical computer science to determine the pr
ecis\ne computational complexity of this "Graph Isomorphism Problem".\\\\\
n\\\\\nOne of the earliest applications of isomorphism testing was in chem
istry\, more precisely chemic\nal information systems. Today\, application
s of isomorphism testing and symmetry detection are u\nbiquitous in comput
ing. Prominent examples appear in optimisation\, malware detection\, and m
achi\nne learning. However\, in many of these applications\, we only need
to decide if two structures a\nre sufficiently similar\, rather than exact
ly the same. It turns out that determining how simila\nr two structures ar
e is an even harder computational problem than deciding whether they are i
so\nmorphic.\\\\\n\\\\\nMy talk will be an introduction to algorithmic asp
ects of symmetry and similarity\, ranging from\n the fundamental complexit
y theoretic "Graph Isomorphism Problem" to applications in optimisati\non
and machine learning.
LOCATION:Amphi Turing
END:VEVENT
END:VCALENDAR