BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Google Inc//Google Calendar 70.9054//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
DESCRIPTION:Algorithmes et complexité seminar of IRIF
NAME:Algorithmes et complexité
REFRESH-INTERVAL:PT4H
TIMEZONE-ID:Europe/Paris
X-WR-CALDESC:Algorithmes et complexité seminar of IRIF
X-WR-CALNAME:Algorithmes et complexité
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:Rényi Information Complexity and an Information Theoretic Charac
terization of the Partition Bound - Manoj Prabhakaran\, University of Illi
nois\, Urbana-Champaign
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20160330T140000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20160330T150000
DTSTAMP;VALUE=DATE-TIME:20191207T100300Z
UID:39
DESCRIPTION:We introduce a new information-theoretic complexity measure IC
∞ for\n2-party functions which is a lower-bound on communication complex
ity\,\nand has the two leading lower-bounds on communication complexity as
\nits natural relaxations: (external) information complexity (IC) and\nlog
arithm of partition complexity (prt). These two lower-bounds had so\nfar a
ppeared conceptually quite different from each other\, but we show\nthat t
hey are both obtained from IC∞ using two different\, but natural\nrelaxa
tions:\n\n * IC∞ is similar to information complexity IC\, except that
it uses Rényi mutual information of order ∞ instead of Shannon's mutual
information (which is Rényi mutual information of order 1). Hence\, the
relaxation of IC∞ that yields IC is to change the order of Rényi mutual
information used in its definition from ∞ to 1.\n\n * The relaxation t
hat connects IC∞ with partition complexity is to replace protocol transc
ripts used in the definition of IC∞ with what we term "pseudotranscripts
\," which omits the interactive nature of a protocol\, but only requires t
hat the probability of any transcript given inputs x and y to the two part
ies\, factorizes into two terms which depend on x and y separately. While
this relaxation yields an apparently different definition than (log of) pa
rtition function\, we show that the two are in fact identical. This gives
us a surprising characterization of the partition bound in terms of an inf
ormation-theoretic quantity.\n\nFurther understanding IC∞ might have con
sequences for important\ndirect-sum problems in communication complexity\,
as it lies between\ncommunication complexity and information complexity.\
n\nWe also show that if both the above relaxations are simultaneously\napp
lied to IC∞\, we obtain a complexity measure that is lower-bounded\nby t
he (log of) relaxed partition complexity\, a complexity measure\nintroduce
d by Kerenidis et al. (FOCS 2012). We obtain a similar (but\nincomparable)
connection between (external) information complexity and\nrelaxed partiti
on complexity as Kerenidis et al.\, using an arguably\nmore direct proof.\
n\nThis is joint work with Vinod Prabhakaran.
LOCATION:Salle 3058
END:VEVENT
BEGIN:VEVENT
SUMMARY:Is there such a thing as private classical information? - Charles
Bennett
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20160419T110000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20160419T120000
DTSTAMP;VALUE=DATE-TIME:20191207T100300Z
UID:52
DESCRIPTION:Classical secret information lies on a slippery slope between
public information and quantum information. Even leaving aside fanciful at
tacks like neutrino tomography\, a typical classical secret---say a paper
document locked in a safe---quickly decoheres and becomes recoverable in p
rinciple from the environment outside the safe. On the other hand\, if a s
ystem is so well insulated from its environment that it does not decohere\
, it can be used as a quantum memory\, capable of existing in a superposit
ion of classical states and of being entangled with other other quantum me
mories. We discuss the practical and theoretical difficulty of recovering
a classical secret from its decohered environment\, and of protecting a cl
assical secret by arranging that some information required to recover it e
scapes into parts of the environment inaccessible to the eavesdropper.
LOCATION:Salle 1007
END:VEVENT
BEGIN:VEVENT
SUMMARY:Undirected Graph Exploration with Θ(log log n) Pebbles - Jan Hack
feld\, TU Berlin
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20160426T110000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20160426T120000
DTSTAMP;VALUE=DATE-TIME:20191207T100300Z
UID:55
DESCRIPTION:We consider the fundamental problem of exploring an undirected
and initially unknown graph by an agent with little memory. The vertices
of the graph are unlabeled\, and the edges incident to a vertex have local
ly distinct labels. In this setting\, it is known that Θ(log n) bits of m
emory are necessary and sufficient to explore any graph with at most n ver
tices. We show that this memory requirement can be decreased significantly
by making a part of the memory distributable in the form of pebbles. A pe
bble is a device that can be dropped to mark a vertex and can be collected
when the agent returns to the vertex. We show that for an agent O(log log
n) distinguishable pebbles and bits of memory are sufficient to explore a
ny bounded-degree graph with at most n vertices. We match this result with
a lower bound exhibiting that for any agent with sub-logarithmic memory\,
Ω(log log n) distinguishable pebbles are necessary for exploration.\n\n
This talk is based on joint work with Yann Disser and Max Klimm (SODA'16).
LOCATION:Salle 4033
END:VEVENT
BEGIN:VEVENT
SUMMARY:Pseudotelepathy games with graph states\, contextuality and multip
artiteness width. - Mehdi Mhalla\, LIG Grenoble
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20160503T110000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20160503T120000
DTSTAMP;VALUE=DATE-TIME:20191207T100300Z
UID:57
DESCRIPTION:Analyzing pseudotelepathy graph games\, we propose a way to bu
ild contextuality scenarios exhibiting the quantum supremacy using graph s
tates. We consider the combinatorial structures generating equivalent scen
arios. We investigate which scenarios are more multipartite and show that
there exists graphs generating scenarios with a linear multipartiteness w
idth.\n\nThis is based on a joint work with Peter Hoyer and Simon Perdrix.
LOCATION:Salle 1007
END:VEVENT
BEGIN:VEVENT
SUMMARY:Solving k-SUM using few linear queries - Jean Cardinal
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20160510T110000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20160510T120000
DTSTAMP;VALUE=DATE-TIME:20191207T100300Z
UID:58
DESCRIPTION:The k-SUM problem is given n input real numbers to determine w
hether any k of them sum to zero. The problem is of tremendous importance
in the emerging field of complexity theory within P\, and it is in particu
lar open whether it admits an algorithm of complexity O(n^c) with c<⌈k/2
⌉. Inspired by an algorithm due to Meiser (1993)\, we show that there ex
ist linear decision trees and algebraic computation trees of depth O(n^3 l
og^3(n)) solving k-SUM. Furthermore\, we show that there exists a randomiz
ed algorithm that runs in Õ (n^{⌈k/2⌉+8}) time\, and performs O(n^3
log^3(n)) linear queries on the input. Thus\, we show that it is possible
to have an algorithm with a runtime almost identical (up to the +8) to the
best known algorithm but for the first time also with the number of queri
es on the input a polynomial that is independent of k. The O(n^3 log^3(n))
bound on the number of linear queries is also a tighter bound than any kn
own algorithm solving k-SUM\, even allowing unlimited total time outside o
f the queries. By simultaneously achieving few queries to the input withou
t significantly sacrificing runtime vis-à-vis known algorithms\, we deepe
n the understanding of this canonical problem which is a cornerstone of co
mplexity-within-P.\nWe also consider a range of tradeoffs between the numb
er of terms involved in the queries and the depth of the decision tree. In
particular\, we prove that there exist o(n)-linear decision trees of dept
h o(n^4). \n\nJoint work with John Iacono and Aurélien Ooms
LOCATION:Salle 1007
END:VEVENT
BEGIN:VEVENT
SUMMARY:Solving optimization problems on noisy planar graphs - Nikhil Bans
al\, Eindhoven University of Technology
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20160517T110000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20160517T120000
DTSTAMP;VALUE=DATE-TIME:20191207T100300Z
UID:59
DESCRIPTION:Many graph problems that are hard to approximate on general gr
aphs become much more tractable on\nplanar graphs. In particular\, planar
graphs can be decomposed into small pieces or into bounded\ntreewidth grap
hs\, leading to PTASes for these problems. But little is known about the n
oisy setting\nwhere the graphs are only nearly planar\, i.e. deleting few
edges makes them planar. \nOne obstacle is that current planar decompositi
on techniques fail completely with noise. \nAnother obstacle is that the k
nown guarantees for the planarization problem are too weak for our purpose
.\n\nWe show that using linear programming methods such as configuration L
Ps and spreading metrics\, one can get \naround these barriers and obtain
PTASes for many problems on noisy planar graphs. \nThis resolves an open q
uestion of Magen and Moharrami\, that was recently popularized by Claire M
athieu.
LOCATION:Salle 1007
END:VEVENT
BEGIN:VEVENT
SUMMARY:Streaming Algorithms for Partitioning Sequences and Trees - Christ
ian Konrad\, Reykjavik University
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20160311T110000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20160311T120000
DTSTAMP;VALUE=DATE-TIME:20191207T100300Z
UID:62
DESCRIPTION:Partitioning sequences and trees are classical load balancing
problems that received considerable attention in the 80ies and 90ies. For
both problems exact algorithms with different characteristics exist. Howev
er\, in the context of massive data sets\, these algorithms fail since the
y assume random access to the input\, an assumption that can hardly be gra
nted. The key motivation of this work is the partitioning of current XML d
atabases\, some of which reach many terrabytes in size. In an XML database
\, data is organized in a tree structure.\n\nIn this talk\, I will present
streaming algorithms for both problems. The presented algorithms require
a random access memory whose size is only logarithmic in the size of the i
nput\, which makes them good candidates for performing well in practice. T
his work will be presented next week at ICDT 2016\, the 19th International
Conference on Database Theory.
LOCATION:Salle 1007
END:VEVENT
BEGIN:VEVENT
SUMMARY:Sampling quantum states - Ashwin Nayak\, University of Waterloo
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20160223T110000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20160223T120000
DTSTAMP;VALUE=DATE-TIME:20191207T100300Z
UID:63
DESCRIPTION:A classic result in information theory\, the source coding the
orem\, shows how we may compress a sample from a random variable X\, into
essentially H(X) bits on average\, without any loss. (Here H(X) denotes th
e Shannon entropy of X.) We revisit the analogous problem in quantum commu
nication\, in the presence of shared entanglement. No characterization of
the communication needed for lossless compression is known in this scenari
o. We study a natural protocol for such compression\, quantum rejection sa
mpling\, and give bounds on its complexity. Eventhough we do not have a pr
ecise characterization of the complexity\, we show how it may be used to d
erive some consequences of lossless compression.\n\nJoint work with Ala Sh
ayeghi.
LOCATION:Salle 1007
END:VEVENT
BEGIN:VEVENT
SUMMARY:Constraint Satisfaction Problems\, LP relaxations and Polymorphism
s - Johan Thapper\, Université Paris-Est\, Marne-la-Vallée\, LIGM
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20160216T110000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20160216T120000
DTSTAMP;VALUE=DATE-TIME:20191207T100300Z
UID:64
DESCRIPTION:An instance of the Constraint Satisfaction Problem (CSP) is gi
ven by a set of constraints over a set of variables. The variables take va
lues from a (finite) domain and the constraints are specified by relations
over the domain that need to hold between various subsets of variables. I
n the late 90s\, it was realised that the complexity of the CSP restricted
to some fixed set of relations is captured by an associated set of operat
ions called polymorphisms. This connection has lead to a great influx of i
deas and tools (as well as researchers) from universal algebra\, a field o
f mathematics that in particular studies algebras of such operations.\n\nA
quite general optimisation version of the CSP is obtained by replacing th
e relations by arbitrary functions from tuples of domain values to the rat
ionals extended with positive infinity. The goal of this problem\, called
the Valued Constraint Satisfaction Problem (VCSP)\, is to minimise a sum o
f such functions over all assignments. The complexity classification proje
ct of the VCSP has taken some great strides over the last four years and h
as recently been reduced to its more famous decision problem counterpart:
the dichotomy conjecture for the CSP.\n\nI will talk about how polymorphis
ms appear in the study of the CSP and some of what universal algebra has t
aught us. I will then show how these results can be used for characterisin
g the efficacy of Sherali-Adams linear programming relaxations of the VCSP
.\n\nThis is based on joint work with Standa Zivny\, University of Oxford
(UK).
LOCATION:Salle 1007
END:VEVENT
BEGIN:VEVENT
SUMMARY:Compression of communication protocols - Balthazar Bauer
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20160202T110000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20160202T120000
DTSTAMP;VALUE=DATE-TIME:20191207T100300Z
UID:65
DESCRIPTION:In communication theory\, there are two big characteristics fo
r a protocol: its communication complexity and its information complexity.
There is a huge activity in the research community to find interesting re
lations between these two characteristics. An idea is to try to compress a
protocol and to see the efficiency of the compression for a protocol with
a known communication and information. Here we will see some recent schem
es of compression. It will be also a good occasion to discover some common
tricks and algorithms in communication and information theory.
LOCATION:Salle 1007
END:VEVENT
BEGIN:VEVENT
SUMMARY:Exact and Approximation Algorithms for Weighted Matroid Intersecti
on - Chien-Chung Huang\, Chalmers University of Technology and Göteborg U
niversity
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20160126T110000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20160126T120000
DTSTAMP;VALUE=DATE-TIME:20191207T100300Z
UID:66
DESCRIPTION:We propose new exact and approximation algorithms for the weig
hted matroid intersection problem. Our exact algorithm is faster than prev
ious algorithms when the largest weight is relatively small. Our approxima
tion algorithm delivers a $(1-\\epsilon)$-approximate solution with a runn
ing time significantly faster than most known exact algorithms.\n\nThe cor
e of our algorithms is a decomposition technique: we decompose an instance
of the weighted matroid intersection problem into a set of instances of t
he unweighted matroid intersection problem. The computational advantage of
this approach is that we can make use of fast unweighted matroid intersec
tion algorithms as a black box for designing algorithms. Precisely speakin
g\, we prove that we can solve the weighted matroid intersection problem v
ia solving $W$ instances of the unweighted matroid intersection problem\,
where $W$ is the largest given weight.\nFurthermore\, we can find a $(1-\\
epsilon)$-approximate solution via solving $O(\\epsilon^{-1} \\log r)$\nin
stances of the unweighted matroid intersection problem\, where $r$ is the
smallest rank of the given two matroids.
LOCATION:Salle 1007
END:VEVENT
BEGIN:VEVENT
SUMMARY:Monotone Properties of k-Uniform Hypergraphs are Weakly Evasive. -
Tim Black\, University of Chicago
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20160524T110000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20160524T120000
DTSTAMP;VALUE=DATE-TIME:20191207T100300Z
UID:67
DESCRIPTION:The decision-tree complexity of a Boolean function is the numb
er of input bits that must be queried (adaptively) in the worst case to de
termine the value of the function. A Boolean function in n variables is we
akly evasive if its decision-tree complexity is Omega(n). By k-graphs we
mean k-uniform hypergraphs. A k-graph property on v vertices is a Boolean
function on n = \\binom{v}{k} variables corresponding to the k-subsets of
a v-set that is invariant under the v! permutations of the v-set (isomorp
hisms of k-graphs).\n \nRivest and Vuillemin (1976) proved that all non-co
nstant monotone graph properties (k=2) are weakly evasive\, confirming a c
onjecture of Aanderaa and Rosenberg (1973). Kulkarni\, Qiao\, and Sun (20
13) proved the analogous result for 3-graphs. We extend these results to
k-graphs for every fixed k. From this\, we show that monotone Boolean func
tions invariant under the action of a large primitive group are weakly eva
sive.\n \nWhile KQS (2013) employ the powerful topological approach of Kah
n\, Saks\, and Sturtevant (1984) combined with heavy number theory\, our a
rgument is elementary and self-contained (modulo some basic group theory).
Inspired by the outline of the KQS approach\, we formalize the general f
ramework of "orbit augmentation sequences" of sets with group actions. We
show that a parameter of such sequences\, called the "spacing\," is a low
er bound on the decision-tree complexity for any nontrivial monotone prope
rty that is G-invariant for all groups G involved in the orbit augmentatio
n sequence\, assuming all those groups are p-groups. We develop operations
on such sequences such as composition and direct product which will provi
de helpful machinery for our applications. We apply this general technique
to k-graphs via certain liftings of k-graphs with wreath product action o
f p-groups.
LOCATION:Salle 1007
END:VEVENT
BEGIN:VEVENT
SUMMARY:Span Programs\, NAND-Trees\, and Graph Connectivity - Stacey Jeffe
ry\, Institute for Quantum Information and Matter\, Caltech
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20160531T110000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20160531T120000
DTSTAMP;VALUE=DATE-TIME:20191207T100300Z
UID:71
DESCRIPTION:We show a connection between NAND-tree evaluation and st-conne
ctivity problems on certain graphs to generalize a superpolynomial quantum
speedup of Zhan et al. for a promise version of NAND-tree formula evaluat
ion. In particular\, we show that the quantum query complexity of evaluati
ng NAND-tree instances with average choice complexity at most W is O(W)\,
where average choice complexity is a measure of the difficulty of winning
the associated two-player game. Our results follow from relating average
choice complexity to the effective resistance of these graphs\, which itse
lf corresponds to the span program witness size. These connections suggest
an interesting relationship between st-connectivity problems and span pro
gram algorithms\, that we hope may have further applications.\n\nThis is j
oint work with Shelby Kimmel.
LOCATION:Salle 1007
END:VEVENT
BEGIN:VEVENT
SUMMARY:Alternating Communication Complexity\, with Applications to Online
Space Complexity - Nathanaël Fijalkow
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20160621T110000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20160621T120000
DTSTAMP;VALUE=DATE-TIME:20191207T100300Z
UID:77
DESCRIPTION:We study the model of alternating communication complexity int
roduced by Babai\, Frankl and Simon in 1986. We extend the rank lower boun
d to this setting. We show some applications of this technique for online
space complexity\, as defined by Karp in the 60s. This measure of complexi
ty quantifies the amount of space used by a Turing machine whose input tap
e can read each symbol only once\, from left to right.\nIn particular\, we
obtain logarithmic lower bounds on the alternating online space complexit
y of the set of prime numbers written in binary\, which is an exponential
improvement over the previous result due to Hartmanis and Shank in 1968.
LOCATION:Salle 1007
END:VEVENT
BEGIN:VEVENT
SUMMARY:Towards Constructing Expanders via Lifts: Hopes and Limitations. -
Alexandra Kolla\, University of Illinois at Urbana-Champaign
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20160705T110000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20160705T120000
DTSTAMP;VALUE=DATE-TIME:20191207T100300Z
UID:85
DESCRIPTION:In this talk\, I will examine the spectrum of random k-lifts o
f d-regular\ngraphs. We show that\, for random shift k-lifts (which includ
es 2-lifts)\, if all the nontrivial eigenvalues of the base graph G are at
most \\lambda in absolute value\, then with high probability depending on
ly on the number n of nodes of G (and not on k)\, if k is *small enough*\,
the absolute value of every nontrivial eigenvalue of the lift is at most
O(\\lambda).\nWhile previous results on random lifts were asymptotically t
rue with high probability in the degree of the lift k\, our result is the
first upperbound on spectra of lifts for bounded k. In particular\, it imp
lies that a\ntypical small lift of a Ramanujan graph is almost Ramanujan.
I will present a quasi-polynomial time algorithm for constructing almost-R
amanujan expanders through such lifts. I will also discuss some impossibil
ity results for large k\, which\, as one consequence\, imply that there is
no hope of constructing large Ramanujan graphs from large abelian k-lifts
.\n\nBased on joint work with Naman Agarwal Karthik Chandrasekaran and Vi
vek Madan.
LOCATION:Salle 1007
END:VEVENT
BEGIN:VEVENT
SUMMARY:Improving and extending testing of distributions for shape restric
tions. - Eldar Fischer\, Faculty of CS\, Technion - Israel Institue of Tec
hnology
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20160920T110000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20160920T120000
DTSTAMP;VALUE=DATE-TIME:20191207T100300Z
UID:96
DESCRIPTION:Distribution property testing deals with what information can
be deduced\nabout an unknown distribution over {1\,...\,n}\, where we are
only allowed\nto obtain a relatively small number of independent samples f
rom the\ndistribution. In the basic model the algorithm may only base its\
ndecision on receiving a sequence of samples from the distribution\, while
\nin the conditional model the algorithm may also request samples out of\n
the conditional distribution over subsets of {1\,...\,n}.\n\nA test has to
distinguish a distribution satisfying a given property\nfrom a distributi
on that is far in the variation distance from\nsatisfying it. A range of p
roperties such as monotonicity and\nlog-concavity has been unified under t
he banner of L-decomposable\nproperties. Here we improve upon the basic mo
del test for all such\nproperties\, as well as provide a new test under th
e conditional model\nwhose number of queries does not directly depend on n
. We also provide a\nconditional model test for a wider range of propertie
s\, that in\nparticular yields tolerant testing for all L-decomposable pro
perties.\nFor tolerant testing conditional samples are essential\, as an e
fficient\ntest in the basic model is known not to exist.\n\nOur main mecha
nism is a way of efficiently producing a partition of\n{1\,...\,n} into in
tervals satisfying a small-weight requirement with\nrespect to the unknown
distribution. Also\, we show that investigating\njust one such partition
is sufficient for solving the testing question\,\nas opposed to prior work
s where a search for the "correct" partition was\nperformed.\n\nJoint work
with Oded Lachish and Yadu Vasudev.
LOCATION:Salle 1007
END:VEVENT
BEGIN:VEVENT
SUMMARY:On the Single-Pass Streaming Complexity of the Set Cover Problem -
Sanjeev Khanna\, University of Pennsylvania
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20160829T110000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20160829T120000
DTSTAMP;VALUE=DATE-TIME:20191207T100300Z
UID:97
DESCRIPTION:In the set cover problem\, we are given a collection of $m$ su
bsets over a universe of $n$ elements\, and the goal is to find a sub-coll
ection of sets whose union covers the universe. The set cover problem is a
fundamental optimization problem with many applications in computer scien
ce and related disciplines. In this talk\, we investigate the set cover pr
oblem in the streaming model of computation whereby the sets are presented
one by one in a stream\, and the goal is to solve the set cover problem u
sing a space-efficient algorithm. \n\nWe show that to compute an $\\alpha$
-approximate set cover (for any $\\alpha= o(\\sqrt{n})$) via a single-pass
streaming algorithm\, $\\Theta(mn/\\alpha)$ space is both necessary and s
ufficient (up to an $O(\\log{n})$ factor). We further study the problem of
estimating the size of a minimum set cover (as opposed to finding the act
ual sets)\, and show that this turns out to be a distinctly easier problem
. Specifically\, we prove that $\\Theta(mn/\\alpha^2)$ space is both suffi
cient and necessary (up to logarithmic factors) for estimating the size of
a minimum set cover to within a factor of $\\alpha$. Our algorithm in fac
t works for the more general problem of estimating the optimal value of a
covering integer program. These results provide a tight resolution of the
space-approximation tradeoff for single-pass streaming algorithms for the
set cover problem.\n\nThis is joint work with my students Sepehr Assadi an
d Yang Li.
LOCATION:Room 2002
END:VEVENT
BEGIN:VEVENT
SUMMARY:Streaming and communication complexity of Hamming distance - Tatia
na Starikovskaya\, IRIF\, Université Paris Diderot
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20160913T110000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20160913T120000
DTSTAMP;VALUE=DATE-TIME:20191207T100300Z
UID:103
DESCRIPTION:We will discuss the complexity of one of the most basic proble
ms in pattern matching\, that of approximating the Hamming distance. Given
a pattern P of length n the task is to output an approximation of the Ham
ming distance (that is\, the number of mismatches) between P and every n-l
ength substring of a longer text. We provide the first efficient one-way r
andomised communication protocols as well as a new\, fast and space effici
ent streaming algorithm for this problem.
LOCATION:Salle 1007
END:VEVENT
BEGIN:VEVENT
SUMMARY:Deterministic Isolation for Space-Bounded Computation - Dieter van
Melkebeek\, University of Wisconsin\, Madison
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20161011T110000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20161011T120000
DTSTAMP;VALUE=DATE-TIME:20191207T100300Z
UID:105
DESCRIPTION:Isolation is the process of singling out a solution to a probl
em that may have many solutions. It plays an important role in the design
of efficient parallel algorithms as it ensures that the various parallel p
rocesses all work towards a single global solution rather than towards ind
ividual solutions that may not be compatible with one another. For example
\, the best parallel algorithms for finding perfect matchings in graphs hi
nge on isolation for this reason. Isolation is also an ingredient in some
efficient sequential algorithms. For example\, the best running times for
certain NP-hard problems like finding hamiltonian paths in graphs are achi
eved via isolation. \n\n \n All of these algorithms are randomized\, and t
he only reason is the use of the Isolation Lemma -- that for any set syste
m over a finite universe\, a random assignment of small integer weights to
the elements of the universe has a high probability of yielding a unique
set of minimum weight in the system. For each of the underlying problems i
t is open whether deterministic algorithms of similar efficiency exist.\n\
n This talk is about the possibility of deterministic isolation in the spa
ce-bounded setting. The question is: Can one always make the accepting com
putation paths of nondeterministic space-bounded machines unique without c
hanging the underlying language and without blowing up the space by more t
han a constant factor? Or equivalently\, does there exist a deterministic
logarithmic space mapping reduction from directed st-connectivity to itsel
f that transforms positive instances into ones where there is a unique pat
h from s to t?\n\n I will present some recent results towards a resolution
of this question\, obtained jointly with Gautam Prakriya. Our approach to
wards a positive resolution can be viewed as derandomizing the Isolation L
emma in the context of space-bounded computation.
LOCATION:Salle 1007
END:VEVENT
BEGIN:VEVENT
SUMMARY:Provable Performance Gains via Dynamic Parameter Choices in Heuris
tic Optimization - Carola Doerr
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20161018T110000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20161018T120000
DTSTAMP;VALUE=DATE-TIME:20191207T100300Z
UID:115
DESCRIPTION:In many optimization heuristics there are a number of paramete
rs to be chosen. These\nparameters typically have a crucial impact on the
performance of the algorithm. It is\ntherefore of great interest to set th
ese parameters wisely. Unfortunately\, determining the\noptimal parameter
choices for a randomized search heuristic via mathematical means is a\nrat
her difficult task. Even worse\, for many problems the optimal parameter
choices seem to\nchange during the optimization process. While this seems
quite intuitive\, little theoretical\nevidence exist to support this claim
. \nIn a series of recent works we have proposed two very simple success-b
ased update rules\nfor the parameter settings of some standard search heur
istics. For both these rules we can\nprove that they yield a better perfor
mance than any static parameter choice. \nBased on joint work with Benjami
n Doerr (Ecole Polytechnique)\, Timo Koetzing (HPI\nPotsdam\, Germany)\, a
nd Jing Yang (Ecole Polytechnique).
LOCATION:Salle 1007
END:VEVENT
BEGIN:VEVENT
SUMMARY:Clustering on k-edge-colored graphs. - Eric Angel\, Université d'
Évry Val d'Essonne IBISC
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20161025T110000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20161025T120000
DTSTAMP;VALUE=DATE-TIME:20191207T100300Z
UID:116
DESCRIPTION:We study the Max k-colored clustering problem\, where\, given
an edge-colored graph with k colors\, we seek to color the vertices of the
graph so as to find a clustering of the vertices maximizing the number (o
r the weight) of matched edges\, i.e. the edges having the same color\nas
their extremities. We show that the cardinality problem is NP-hard even fo
r edge-colored bipartite graphs with a chromatic degree equal to two and k
≥ 3. Our main result is a constant approximation algorithm for the weig
hted version of the Max k-colored clustering problem which is based on a r
ounding of a natural linear programming relaxation. For graphs with chroma
tic degree equal to two\, we improve this ratio by exploiting the relation
of our problem with the Max 2-and problem. We also present a reduction to
the maximum-weight independent set (IS) problem in bipartite graphs which
leads to a polynomial time algorithm for the case of two colors.
LOCATION:Salle 1007
END:VEVENT
BEGIN:VEVENT
SUMMARY:Polynomial Identity Testing of Sum of ROABPs - Arpita Korwar
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20161108T110000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20161108T120000
DTSTAMP;VALUE=DATE-TIME:20191207T100300Z
UID:121
DESCRIPTION:Polynomials are fundamental objects studied in mathematics. Th
ough univariate polynomials are fairly well-understood\, multivariate poly
nomials are not. Arithmetic circuits are the primary tool used to study po
lynomials in computer science. They allow for the classification of polyno
mials according to their complexity.\n\n\nPolynomial identity testing (PIT
) asks if a polynomial\, input in the form of an arithmetic circuit\, is i
dentically zero.\n\nOne special kind of arithmetic circuits are read-once
arithmetic branching programs (ROABPs)\, which can be written as a product
of univariate polynomial matrices over distinct variables. We will be stu
dying the characterization of an ROABP. In the process\, we can give a pol
ynomial\ntime PIT for the sum of constantly many ROABPs.
LOCATION:Salle 1007
END:VEVENT
BEGIN:VEVENT
SUMMARY:On the (In)security of SNARKs in the Presence of Oracles - Anca Ni
tulescu\, ENS Paris
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20161122T110000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20161122T120000
DTSTAMP;VALUE=DATE-TIME:20191207T100300Z
UID:125
DESCRIPTION:In this work we study the feasibility of knowledge extraction
for succinct non-interactive arguments of knowledge (SNARKs) in a scenario
that\, to the best of our knowledge\, has not been analyzed before. While
prior work focuses on the case of adversarial provers that may receive (s
tatically generated) {\\em auxiliary information}\, here we consider the s
cenario where adversarial provers are given {\\em access to an oracle}. Fo
r this setting we study if and under what assumptions such provers can adm
it an extractor. Our contribution is mainly threefold.\n\nFirst\, we forma
lize the question of extraction in the presence of oracles by proposing a
suitable\nproof of knowledge definition for this setting. We call SNARKs s
atisfying this definition O\nSNARKs. Second\, we show how to use O-SNARKs
to obtain formal and intuitive security proofs\nfor three applications (ho
momorphic signatures\, succinct functional signatures\, and SNARKs on\naut
henticated data) where we recognize an issue while doing the proof under t
he standard\nproof of knowledge definition of SNARKs. Third\, we study whe
ther O-SNARKs exist\, providing\nboth negative and positive results. On th
e negative side\, we show that\, assuming one way\nfunctions\, there do no
t exist O-SNARKs in the standard model for every signing oracle family\n(a
nd thus for general oracle families as well). On the positive side\, we sh
ow that when\nconsidering signature schemes with appropriate restrictions
on the message length O-SNARKs for the corresponding signing oracles exist
\, based on classical SNARKs and assuming\nextraction with respect to spec
ific distributions of auxiliary input.
LOCATION:Salle 1007
END:VEVENT
BEGIN:VEVENT
SUMMARY:Dynamic Complexity of Parity Games with Bounded Tree-Width - Vince
nt Jugé\, LSV\, CNRS & ENS Cachan\, Univ. Paris-Saclay
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20170110T110000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20170110T120000
DTSTAMP;VALUE=DATE-TIME:20191207T100300Z
UID:129
DESCRIPTION:Dynamic complexity is concerned with the complexity of updatin
g a solution to a problem when its input changes. A typical example is as
follows: given an directed graph G and two pointed vertices s and t\, you
wish to know whether there exists a path from s to t in G. After your comp
utation is complete\, the graph is modified (e.g. by adding or deleting an
edge): how should you proceed to update your answer at the least cost? Co
mputing and storing auxiliary data\, such as maintaining a covering forest
\, might be helpful in that regard.\n\nIn this talk\, we will consider a s
pecific class for dynamic complexity\, called DynFO. A dynamic problem bel
ongs to this class if updates can be performed by applying first-order for
mulas. We will show that a dynamic variant of Courcelle's theorem belongs
to DynFO\, and we will apply this result to computing optimal strategies i
n 2-player reachability or parity games.\n\nThis talk is based on joint a
work with Patricia Bouyer-Decitre and\nNicolas Markey.
LOCATION:Salle 1007
END:VEVENT
BEGIN:VEVENT
SUMMARY:Determinism and Computational Power of Real Measurement-based Qua
ntum Computation - Luc Sanselme
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20161202T110000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20161202T120000
DTSTAMP;VALUE=DATE-TIME:20191207T100300Z
UID:139
DESCRIPTION:Measurement-based quantum computing (MBQC) is a universal mode
l for quantum computation. The combinatorial characterisation of determini
sm in this model\, powered by measurements\, and hence\, fundamentally pro
babilistic\, is the cornerstone of most of the breakthrough results in thi
s field. The most general known sufficient condition for a deterministic M
BQC to be driven is that the underlying graph of the computation has a par
ticular kind of flow called Pauli flow. The necessity of the Pauli flow wa
s an open question. We show that the Pauli flow is necessary for real-MBQC
\, and not in general providing counter-examples for (complex) MBQC.\n\nWe
explore the consequences of this result for real MBQC and its application
s. Real MBQC and more generally real quantum computing is known to be univ
ersal for quantum computing. Real MBQC has been used for interactive proof
s by McKague. The two-prover case corresponds to real-MBQC on bipartite gr
aphs. While (complex) MBQC on bipartite graphs are universal\, the univers
ality of real MBQC on bipartite graphs was an open question. We show that
real bipartite MBQC is not universal proving that all measurements of real
bipartite MBQC can be parallelised leading to constant depth computations
. As a consequence\, McKague techniques cannot lead to two-prover interact
ive proofs.\n\nJoint work with Simon Perdrix.
LOCATION:Salle 1007
END:VEVENT
BEGIN:VEVENT
SUMMARY:Algorithmic aspects of optimal channel coding - Omar Fawzi
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20161206T110000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20161206T120000
DTSTAMP;VALUE=DATE-TIME:20191207T100300Z
UID:143
DESCRIPTION:We study the problem of finding the maximum success probabilit
y for transmitting messages over a noisy channel from an algorithmic point
of view. In particular\, we show that a simple greedy polynomial-time alg
orithm computes a code achieving a (1-1/e)-approximation of the maximum su
ccess probability and that it is NP-hard to obtain an approximation ratio
strictly better than (1-1/e). Moreover\, the natural linear programming re
laxation of this problem corresponds to the Polyanskiy-Poor-Verdú bound\,
which we also show has a value of at most\n1/(1-1/e) times the maximum su
ccess probability. \n\nBased on joint work with Siddharth Barman.\narXiv:1
508.04095
LOCATION:Salle 1007
END:VEVENT
BEGIN:VEVENT
SUMMARY:From Ants to Query Complexity - Amos Korman\, CNRS\, IRIF
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20161213T110000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20161213T120000
DTSTAMP;VALUE=DATE-TIME:20191207T100300Z
UID:146
DESCRIPTION:I will talk about my recent adventures with ants. Together wit
h biologists we study P. longicornis ants as they collaboratively transpor
t a large food item to their nest. This collective navigation process is g
uided by pheromones which are laid by individual ants. Using a new methodo
logy to detect scent marks\, we identify a new kind of ant trail character
ized by very short and dynamic pheromone markings and highly stochastic na
vigation response to them. We argue that such a trail can be highly benefi
cial in conditions in which knowledge of individual ants regarding the und
erlying topological structure is unreliable. This gives rise to a new theo
retical search model under unreliable guiding instructions\, which is of i
ndependent computational interest. To illustrate the model\, imagine drivi
ng a car in an unknown country\nthat is in the aftermath of a major hurric
ane which has randomly flipped a certain small fraction\nof the road-signs
. Under such conditions of unreliability\, how can you still reach your\nd
estination fast? I will discuss the limits of unreliability that allow for
efficient navigation. In trees\, for example\, there is a phase transitio
n phenomenon that occurs roughly around\n1/sqrt{D}. That is\, if noise is
above this threshold then any algorithm cannot avoid finding the target in
exponential time (in the original distance)\, while below the threshold w
e identify an optimal\, almost linear\, walking algorithm. Finally\, I wil
l discuss algorithms that under such a noisy model aim to minimize the num
ber of queries to find a target (rather than the number of moves).\n\nThis
talk is based on joint works with biologists: Ofer Feinerman\, Udi Fonio\
, Yael Heyman and Aviram Gelblum\, and CS co-authors: Lucas Boczkowski\, A
drian Kosowski and Yoav Rodeh.
LOCATION:Salle 1007
END:VEVENT
BEGIN:VEVENT
SUMMARY:Streaming and circuit complexity - Charles Paperman
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20170207T110000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20170207T120000
DTSTAMP;VALUE=DATE-TIME:20191207T100300Z
UID:161
DESCRIPTION:In this talk\, I will present a connection between the streami
ng complexity and the circuit complexity of regular languages through a no
tion of streaming by block. This result provides tight constructions of bo
olean circuits computing an automaton\, thanks to some classical and recen
t results on the circuit complexity of regular languages.
LOCATION:Salle 1007
END:VEVENT
BEGIN:VEVENT
SUMMARY:Popularity\, Mixed Matchings\, and Self-duality - Chien-Chung Huan
g\, CNRS\, ENS Paris
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20170131T110000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20170131T120000
DTSTAMP;VALUE=DATE-TIME:20191207T100300Z
UID:179
DESCRIPTION:We consider the problem of matching applicants to jobs under t
wo-sided preferences in a popular and utility-optimal manner. Our\ninput i
nstance is a bipartite graph G = (A \\cup B\,E) with a utility function w:
E \\rightarrow Q where each vertex u \\in A \\cup B has a preference list
ranking its neighbors in a strict order of preference. For any two matchi
ngs M and T in G\, let \\phi(M\,T) be the number of vertices that prefer M
to T. A matching M is popular if \\phi(M\,T) \\geg \\phi(T\,M) for all ma
tchings T in G. A mixed matching is defined as \\Pi = \\{(M_0\,p_0)\,\\ldo
ts\,(M_k\,p_k)\\} for some matchings M_0\,\\ldots\,M_k and \\sum_{i=0}^kp_
i = 1\, p_i \\geq 0 for all i. The function \\phi(\\cdot\,\\cdot$ easily e
xtends to mixed matchings\; a mixed matching \\Pi is popular if \\phi(\\Pi
\,\\Lambda) \\geq \\phi(\\Lambda\,\\Pi) for all mixed matchings \\Lambda i
n G.\n\nMotivated by the fact that a popular mixed matching could have a m
uch higher utility than all popular matchings\, we study the popular fract
ional matching polytope {\\cal P}_G.\nOur main result is that this polytop
e is half-integral (and in the special case where\na stable matching is a
perfect matching\, this polytope is integral)\, implying that there is alw
ays a max-utility popular mixed matching \\Pi such that \\Pi = {(M_0\,\\fr
ac{1}{2})\,(M_1\,\\frac{1}{2})} and \\Pi can be computed in polynomial tim
e. An immediate consequence is that in order to implement a max-utility po
pular mixed matching in $G$\, we need just one single random bit.\n\nWe an
alyze {\\cal P}_G whose description may have exponentially many constraint
s via an extended formulation in m+n dimensions with O(m+n) constraints. T
he linear program that gives rise to this formulation has an unusual prope
rty: self-duality. In other words\, this linear program is exactly identic
al to its dual program. This is a rare case where an LP of a natural probl
em has such a property. The self-duality of the LP plays a crucial role in
our proof of the half-integrality of {\\cal P}_G.\n\nWe also show that ou
r result carries over to the roommates problem\, where the given graph G m
ay not be bipartite. The polytope of popular fractional matchings is still
half-integral here and thus we can compute a max-utility popular half-int
egral matching in G in polynomial time. To complement this result\, we als
o show that the problem of computing a max-utility popular (integral) matc
hing in a roommates instance G is NP-hard.
LOCATION:Salle 1007
END:VEVENT
BEGIN:VEVENT
SUMMARY:Literature Networks and Time in Social Networks. - Zvi Lotker
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20170221T110000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20170221T120000
DTSTAMP;VALUE=DATE-TIME:20191207T100300Z
UID:190
DESCRIPTION:In this talk I will describe the connection between social net
works and theater plays. I will show how algorithms can analyze plays usin
g social networks\, and how plays can reveal an interesting algorithmic pr
oblem.
LOCATION:Salle 1007
END:VEVENT
BEGIN:VEVENT
SUMMARY:Protocols for Detecting a Signal - Adrian Kosowski\, Inria\, IRIF
Université Paris 7
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20170418T110000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20170418T120000
DTSTAMP;VALUE=DATE-TIME:20191207T100300Z
UID:199
DESCRIPTION:We consider the following interaction scenario: a population o
f agents is required to perpetually detect whether or not the population c
ontains at least one agent in a distinguished state X. This problem may be
viewed as a variant of rumor-spreading\, in which a "true" rumor should s
pread and persist in the population for as long as its primary rumor sourc
e X is present\, and a "false" rumor without a source should be actively s
uppressed. Investigations into the problem are also directly motivated by
the question of detecting and amplifying trace concentrations of a chemica
l substance X\, e.g.\, in a framework of DNA computing with chemical react
ion networks (CRN-s). \n\nWe describe two population protocols which solve
the considered problem efficiently\, converging to a correct output state
on a (1-epsilon)-fraction of a population of n agents within a polylogari
thmic number of steps\, starting from any initial configuration of the sys
tem\, w.h.p. under a fair uniformly random scheduler. One of the proposed
protocols requires O(log n) states and has certain desirable robustness pr
operties\, while the other uses only a constant number of states.
LOCATION:Salle 1007
END:VEVENT
BEGIN:VEVENT
SUMMARY:Optimal rates for Least-Squares Regression through stochastic grad
ient descent. - Nicolas Flammarion\, DI/ENS
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20170425T110000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20170425T120000
DTSTAMP;VALUE=DATE-TIME:20191207T100300Z
UID:213
DESCRIPTION:At a broad level\, stochastic optimization is concerned with o
ptimizing a function in the presence of noise. In this context\, we consid
er the optimization of a quadratic objective function whose gradients are
only accessible through a stochastic oracle that returns the gradient at a
ny given point plus a zero-mean finite variance random error. We present t
he first algorithm that achieves the optimal prediction error rates for le
ast-squares regression\, both in terms of forgetting of initial conditions
in O(1/n^2)\, and in terms of dependence on the noise and dimension d of
the problem\, as O(d/n). Our new algorithm is based on averaged accelerate
d regularized gradient descent\, and may also be analyzed through finer as
sumptions on initial conditions and the Hessian matrix\, leading to dimens
ion-free quantities that may still be small while the "optimal" terms abov
e are large.
LOCATION:Salle 1007
END:VEVENT
BEGIN:VEVENT
SUMMARY:Friend or Foe? Population Protocols can perform Community Detectio
n - Emanuele Natale
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20170321T110000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20170321T120000
DTSTAMP;VALUE=DATE-TIME:20191207T100300Z
UID:214
DESCRIPTION:We present a simple distributed algorithm that\, given a regul
ar graph consisting of two communities (or clusters)\, each inducing a goo
d expander and such that the cut between them has sparsity $1/\\mbox{polyl
og}(n)$\, recovers the two communities.\n \nMore precisely\, upon running
the protocol\, every node assigns itself a binary label of $m = \\Theta(\
\log n)$ bits\, so that with high probability\, for all but a small number
of outliers\, nodes within the same community are assigned labels with Ha
mming distance $o(m)$\, while nodes belonging to different communities rec
eive labels with Hamming distance at least $m/2 - o(m)$. We refer to such
an outcome as a "community sensitive labeling" of the graph.\n \nOur algo
rithm uses $\\Theta(\\log^2 n)$ local memory and computes the community se
nsitive labeling after each node performs $\\Theta(\\log^2 n)$ steps of lo
cal work. Our algorithm and its analysis work in the "(random) population
protocol" model\, in which anonymous nodes do not share any global clock (
the model is asynchronous) and communication occurs over one single (rando
m) edge per round. We believe\, this is the first provably-effective proto
col for community detection that works in this model.\n\nJoint work with L
uca Becchetti\, Andrea Clementi\, Francesco Pasquale\, Prasad Raghavendra\
, and Luca Trevisan.\n\nLink to the arxiv version: https://arxiv.org/abs/1
703.05045
LOCATION:Salle 1007
END:VEVENT
BEGIN:VEVENT
SUMMARY:All-Pairs 2-reachability in O(n^ω log n) Time - Przemyslaw Uznans
ki\, ETH Zürich\, Switzerland
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20170413T140000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20170413T150000
DTSTAMP;VALUE=DATE-TIME:20191207T100300Z
UID:228
DESCRIPTION:In the 2-reachability problem we are given a directed graph G
and we wish to determine if there are two (edge or vertex) disjoint paths
from u to v\, for given pair of vertices u and v. We present an algorithm
that computes 2-reachability information for all pairs of vertices in O(n^
ω logn) time. Hence\, we show that the running time of all-pairs 2-reacha
bility is within a log factor of transitive closure.\n\nMoreover\, our alg
orithm produces a witness (i.e.\, a separating edge or a separating vertex
) for all pair of vertices where 2-reachability does not hold. By processi
ng these witnesses\, we can compute all the edge- and vertex-dominator tre
es of G in O(n^2) additional time\, which in turn enables us to answer var
ious connectivity queries in O(1) time. For instance\, we can test in cons
tant time if there is a path from u to v avoiding an edge e\, for any pair
of query vertices u and v\, and any query edge e\, or if there is a path
from u to v avoiding a vertex w\, for any query vertices u\, v\, and w.\n\
nThis is a joint work with Loukas Georgiadis (University of Ioannina)\, Da
niel Graf (ETH Zurich)\, Giuseppe Italiano and Nikos Parotsidis (Universit
y of Rome\, Tor Vergata).\n\nLink to the paper: https://arxiv.org/abs/1612
.08075
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:Tree decompositions for probabilistic data management - Pierre Sen
ellart\, DI/ENS
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20170502T110000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20170502T120000
DTSTAMP;VALUE=DATE-TIME:20191207T100300Z
UID:245
DESCRIPTION:Joint work with Antoine Amarilli\, Pierre Bourhis\, Mikaël Mo
net\, Silviu Maniu.\n\n\nIn this talk\, we review recent work on the probl
em of efficiently querying probabilistic databases\, i.e.\, compact repres
entations of probability distributions over databases\, by exploiting the
structure of the data. In the deterministic setting\, a celebrated result
by Courcelle shows that any monadic second-order query can be evaluated in
linear-time\non instances of bounded treewidth. We show that this result
generalizes to probabilistic instances through the use of provenance. In t
he probabilistic setting\, we show that a bound on the treewidth is necess
ary for query evaluation to be tractable\, in sharp contrast with the dete
rministic setting. This leads us to studying which real-world databases ac
tually have low treewidth\, and to propose practical algorithms for query
evaluation in databases that can be partially decomposed in a low-treewidt
h part and a high-treewidth core.\n\nPierre Senellart is a Professor in th
e Computer Science Department at the École normale supérieure in Paris\,
France\, and the head of the Valda team of Inria Paris. He is an alumnus
of ENS and obtained his M.Sc. (2003) and Ph.D. (2007) in computer science
from Université Paris-Sud\, studying under the supervision of Serge Abite
boul. He was awarded an Habilitation à diriger les recherches in 2012 fro
m Université Pierre et Marie Curie. Before joining ENS\, he was an Associ
ate Professor (2008–2013) then a Professor (2013–2016) at Télécom Pa
risTech. He also held secondary appointments as Lecturer at the University
of Hong Kong in 2012–2013\, and as Senior Research Fellow at the Nation
al University of Singapore from 2014 to 2016. His research interests focus
around practical and theoretical aspects of Web data management\, includi
ng Web crawling and archiving\, Web information extraction\, uncertainty m
anagement\, Web mining\, and intensional data management.
LOCATION:Salle 1007
END:VEVENT
BEGIN:VEVENT
SUMMARY:Beyond Adjacency Maximization: Scaffold Filling for New String Dis
tances - Laurent Bulteau\, CNRS\, Laboratoire d'Informatique Gaspard Monge
\, Marne-la-Vallée\, France.
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20170620T110000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20170620T120000
DTSTAMP;VALUE=DATE-TIME:20191207T100300Z
UID:267
DESCRIPTION:In Genomic Scaffold Filling\, one aims at polishing in silico
a draft genome\, called scaffold. The scaffold is given in the form of an
ordered set of gene sequences\, called contigs. This is done by confrontin
g the scaffold to an already complete reference genome from a close specie
s. More precisely\, given a scaffold S\, a reference genome G (represented
as a string) and a score function f() between two genomes\, the aim is to
complete S by adding the missing genes from G so that the obtained comple
te genome S* optimizes f(S*\,G). In this talk\, we will consider two alter
native score functions: the first aims at maximizing the number of common
k-mers between S* and G (k-Mer Scaffold Filling)\, the second aims at mini
mizing the number of string breakpoints between S* and G (Min-Breakpoint S
caffold Filling). We study these problems from the parameterized complexi
ty point of view\, providing fixed-parameter (FPT) algorithms for both pro
blems. In particular\, we show that k-Mer Scaffold Filling is FPT wrt. the
number of additional k-mers realized by the completion of S. We also show
that Min-Breakpoint Scaffold Filling is FPT wrt. a parameter combining th
e number of missing genes\, the number of gene repetitions and the target
distance.
LOCATION:Salle 1007
END:VEVENT
BEGIN:VEVENT
SUMMARY:Entanglement Tests from Group Representations. - Thomas Vidick\, C
alifornia Institute of Technology
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20170606T160000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20170606T170000
DTSTAMP;VALUE=DATE-TIME:20191207T100300Z
UID:269
DESCRIPTION:I will present a novel perspective on entanglement tests\, suc
h as the CHSH inequality and extensions thereof\, pioneered by Slofstra an
d (unknowingly) Gowers-Hatami\, that is based on the theory of (approximat
e) representations of non-abelian groups. We will see how this theory lead
s to a simple analysis of:\n\n(i) The first family of self-tests (or\, two
-player entangled games) for arbitrarily high-dimensional entanglement tha
t is robust to a constant fraction of noise. (Joint work with Natarajan\,
arXiv:1610.03574.)\n\n(ii) The first finite self-test such that for any ep
s>0\, entangled states of dimension poly(1/eps) are both necessary and suf
ficient to achieve success probability 1-eps. (Joint work with Slofstra\,
in preparation.)
LOCATION:3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:The Optimality of Projections for Quantum State Exclusion - Abel M
olina
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20170613T110000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20170613T120000
DTSTAMP;VALUE=DATE-TIME:20191207T100300Z
UID:270
DESCRIPTION:We will first motivate the problem of quantum state exclusion
of pure states\, through its connections with the PBR game and with compat
ibility conditions for quantum state assignments. Then\, we will discuss o
ur recent result regarding the optimality of projections for perfect state
exclusion of 3 pure states in 3 dimensions (arXiv:1702.06449). We will de
scribe our techniques to prove this result\, which are based on arguments
involving convexity\, rank and symmetry properties. Finally\, we will disc
uss other related results\, as well as possible avenues for extending our
results.
LOCATION:Salle 1007
END:VEVENT
BEGIN:VEVENT
SUMMARY:Inner Rank and Lower Bounds for Matrix Multiplication - Joel Fried
man\, University of British Columbia
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20170706T110000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20170706T120000
DTSTAMP;VALUE=DATE-TIME:20191207T100300Z
UID:280
DESCRIPTION:We give a short proof of the optimality of Strassen's classica
l algorithm for 2 x 2 matrix multiplication\, and more generally give a 2n
^2 - n + 1 lower bound for n x n matrix multiplcation\, in terms of the bo
rder rank (and\, hence\, also rank) of the associated tensor\, over an arb
itrary field.\n\n\nWe call the tool we use "inner rank\," which seems to h
ave gone unnoticed in the literature (at least in the way we use it). Whi
le our bounds are not competitive with the best bounds to date over the co
mplex numubers\, we argue that "inner rank" may lead to improved results a
nd merits further study.
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:A Reverse Minkowski Theorem - Oded Regev\, Courant Institute of Ma
thematical Sciences\, NYU
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20170711T110000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20170711T120000
DTSTAMP;VALUE=DATE-TIME:20191207T100300Z
UID:282
DESCRIPTION:Informally\, Minkowski's first theorem states that lattices th
at are\nglobally dense (have small determinant) are also locally dense (ha
ve\nlots of points in a small ball around the origin). This fundamental\nr
esult dates back to 1891 and has a very wide range of applications.\n\nI w
ill present a proof of a reverse form of Minkowski's theorem\,\nconjecture
d by Daniel Dadush in 2012\, showing that locally dense\nlattices are also
globally dense (in the appropriate sense).\n\nThe talk will be self conta
ined and I will not assume any familiarity\nwith lattices.\n\nBased on joi
nt papers with Daniel Dadush and Noah Stephens-Davidowitz.
LOCATION:Salle 1007
END:VEVENT
BEGIN:VEVENT
SUMMARY:Hierarchical Clustering: Objective Functions and Algorithms - Vinc
ent Viallat Cohen-Addad
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20170919T110000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20170919T120000
DTSTAMP;VALUE=DATE-TIME:20191207T100300Z
UID:286
DESCRIPTION:Hierarchical clustering is a recursive partitioning of a datas
et into clusters at an increasingly finer granularity. Motivated by the fa
ct that most work on hierarchical clustering was based on providing algori
thms\, rather than optimizing a specific objective\, Dasgupta framed simil
arity-based hierarchical clustering as a combinatorial optimization proble
m\, where a `good' hierarchical clustering is one that minimizes some cost
function. He showed that this cost function has certain desirable propert
ies. \n\nWe take an axiomatic approach to defining `good' objective functi
ons for both similarity and dissimilarity-based hierarchical clustering. W
e characterize a set of "admissible" objective functions (that includes Da
sgupta's one) that have the property that when the input admits a `natural
' hierarchical clustering\, it has an optimal value. \n\nEquipped with a s
uitable objective function\, we analyze the performance of practical algor
ithms\, as well as develop better algorithms. For similarity-based hierarc
hical clustering\, Dasgupta showed that the divisive sparsest-cut approach
achieves an O(log^{3/2} n)-approximation. We give a refined analysis of t
he algorithm and show that it in fact achieves an O(\\sqrt{log n})-approx.
(Charikar and Chatziafratis independently proved that it is a O(\\sqrt{lo
g n})-approx.). This improves upon the LP-based O(logn)-approx. of Roy and
Pokutta. For dissimilarity-based hierarchical clustering\, we show that t
he classic average-linkage algorithm gives a factor 2 approx.\, and provid
e a simple and better algorithm that gives a factor 3/2 approx.. \n\nFinal
ly\, we consider `beyond-worst-case' scenario through a generalisation of
the stochastic block model for hierarchical clustering. We show that Dasgu
pta's cost function has desirable properties for these inputs and we provi
de a simple 1 + o(1)-approximation in this setting.\n\nJoint work with Var
un Kanade\, Frederik Mallmann-Trenn\, and Claire Mathieu.
LOCATION:Salle 1007
END:VEVENT
BEGIN:VEVENT
SUMMARY:Online Search Problems - Vianney Perchet\, CMLA\, Ens Paris-Saclay
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20170926T110000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20170926T120000
DTSTAMP;VALUE=DATE-TIME:20191207T100300Z
UID:291
DESCRIPTION:In traditional "search problems"\, an agent aims at exploring
a graph in order to find a hidden object as fast as possible. We consider
here the Bayesian repeated scenario with several iid instance of the same
basic search problem. The objective is\, within a given amount of time\, t
o find as many objects as possible with the possibility to leave an instan
ce for the next one at any moment.\n\nWe also consider the non-bayesian ca
se with a variant of regret minimization. We provide and analyze several a
lgorithms with fast rates of convergence and/or guaranteed efficiency.
LOCATION:Salle 1007
END:VEVENT
BEGIN:VEVENT
SUMMARY:Decremental Single-Source Reachability and Strongly Connected Comp
onents in O(m \\sqrt{n log n}) Total Update Time - Giuseppe Italiano\, Uni
versita di Roma Tor Vergata
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20171003T110000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20171003T120000
DTSTAMP;VALUE=DATE-TIME:20191207T100300Z
UID:294
DESCRIPTION:We present randomized algorithms with a total update time of O
(m \\sqrt{n} log n) for the problems of decremental single-source reachab
ility and decremental strongly connected components on directed graphs. T
his improves sharply recent breakthrough results of Henzinger\, Krinninger
and Nanongkai [STOC 14\, ICALP 15]. In addition\, our algorithms are argu
ably simpler. In this talk\, we first review the Las Vegas algorithm by Ro
ditty and Zwick [SICOMP 08] and the deterministic algorithm by Łącki [T
ALG 13]\, both with a total update time O(mn) (expected time in the case
of the algorithm by Roditty and Zwick). Our algorithms carefully combine
these two results\, along with new structural properties\, including a sep
aration lemma in the case of graphs with a large diameter.\n\nJoint work w
ith Shiri Chechik\, Thomas Dueholm Hansen\, Jakub Łącki and\nNikos Parot
sidis.
LOCATION:Salle 1007
END:VEVENT
BEGIN:VEVENT
SUMMARY:How Large is Your Graph? - Victor Verdugo\, ENS - Universidad de C
hile
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20171010T110000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20171010T120000
DTSTAMP;VALUE=DATE-TIME:20191207T100300Z
UID:295
DESCRIPTION:We consider the problem of estimating the graph size\, where o
ne is given only local access to the graph. We formally define a query mod
el in which one starts with a \\emph{seed} node and is allowed to make que
ries about neighbours of nodes that have already been seen. In the case of
undirected graphs\, an estimator of Katzir et al. (2014) based on a sampl
e from the stationary distribution π uses O(1/‖π‖_2+davg) queries\,
we prove that this is tight. In addition\, we establish this as a lower bo
und even when the algorithm is allowed to crawl the graph arbitrarily\, th
e results of Katzir et al. give an upper bound that is worse by a multipli
cative factor tmix⋅log(n). The picture becomes significantly different i
n the case of directed graphs. We show that without strong assumptions on
the graph structure\, the number of nodes cannot be predicted to within a
constant multiplicative factor without using a number of queries that are
at least linear in the number of nodes\, in particular\, rapid mixing and
small diameter\, properties that most real-world networks exhibit\, do not
suffice. The question of interest is whether any algorithm can beat bread
th-first search. We introduce a new parameter\, generalising the well-stud
ied conductance\, such that if a suitable bound on it exists and is known
to the algorithm\, the number of queries required is\nsublinear in the num
ber of edges\, we show that this is tight.
LOCATION:Salle 1007
END:VEVENT
BEGIN:VEVENT
SUMMARY:Online k-compaction - Claire Mathieu\, DI - ENS
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20171017T140000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20171017T150000
DTSTAMP;VALUE=DATE-TIME:20191207T100300Z
UID:296
DESCRIPTION:Given\, at each time t = 1\, 2\, …\, n\, a new file of lengt
h l(t) and a read rate r(t)\, an\nonline k-compaction algorithm must maint
ain a collection of at most k files\, choosing (at each time t\, without k
nowing future inputs) some of the files to merge into one\, thereby incurr
ing a merge cost equal to the total length of the merged files and a read
cost equal to the read rate r(t) times the number of files present at time
t. The goal is to minimize the total cost over time. K-compaction algorit
hms are a key component of log-structured merge trees\, the file-based dat
a structure underlying NoSQL databases such as Accumulo\, Bigtable\, Cassa
ndra\, HBase\,and others. We initiate the theoretical study of k-compactio
n algorithms. We formalize the problem\, consider worst-case\, average-cas
e and competitive analysis (per-instance optimality)\, and propose new alg
orithms that are optimal according to these metrics. \n\nThis is joint wor
k with Carl Staelin\, Neal E. Young\, and Arman Yousefi.
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:A (2+\\epsilon)-Approximation for Maximum Weight Matching in the S
emi-Streaming Model - Ami Paz\, IRIF
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20171031T110000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20171031T120000
DTSTAMP;VALUE=DATE-TIME:20191207T100300Z
UID:319
DESCRIPTION:In this talk I will present our new (2+\\epsilon)-approximatio
n\nalgorithm for the maximum weight matching problem in the\nsemi-streamin
g model\, that was presented in SODA 2017.\n\nWe will start by discussing
the local-ratio technique\, a simple\,\nsequential approximation paradigm
we use in our algorithm. Then\, we\nwill consider the variations needed in
order to adjust this\ntechnique to the semi-streaming model.\n\nBased on
a joint work with Gregory Schwartzman.
LOCATION:Salle 1007
END:VEVENT
BEGIN:VEVENT
SUMMARY:Connections between the Dihedral Coset Problem and LWE - Elena Kir
shanova\, ENS Lyon
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20171116T140000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20171116T150000
DTSTAMP;VALUE=DATE-TIME:20191207T100300Z
UID:330
DESCRIPTION:In this talk\, I explain that under quantum polynomial time re
ductions\, LWE is equivalent to a relaxed version of the dihedral coset pr
oblem (DCP)\, called extrapolated DCP (eDCP). The extent of extrapolation
varies with the LWE noise rate. By considering different extents of extrap
olation\, the result generalizes Regev’s famous proof that if DCP is in
BQP (quantum poly-time) then so is LWE (FOCS 02). We'll also discuss a con
nection between eDCP and Childs and Van Dam’s algorithm for generalized
hidden shift problems (SODA 07). The result implies that a BQP solution fo
r LWE might not require the full power of solving DCP\, but rather only a
solution for its relaxed version\, eDCP\, which could be easier.
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:Mixing and quantum sampling with quantum walks: some results and q
uestions - Simon Apers\, Ghent University
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20171110T150000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20171110T160000
DTSTAMP;VALUE=DATE-TIME:20191207T100300Z
UID:333
DESCRIPTION:Quantum walks have been shown to quadratically speed up search
problems on graphs. We discuss their usage towards mixing and quantum sam
pling on graphs\, problems that are in a sense dual to the search problem.
Quantum sampling\, or quantum state generation\, roughly amounts to creat
ing a superposition over the elements of a set\, where this set may be imp
licitly defined. It is known that if this task can be solved efficiently\,
then the complexity class called "statistical zero knowledge" is in BQP.
We discuss a folklore approach to this problem called "inverted search"\,
where a quantum search algorithm is essentially inverted to yield a quantu
m sampling algorithm. We also show how this approach solves the search pro
blem when starting from a single element of the graph\, rather than a supe
rposition. The easier task of mixing on graphs asks for a classical sample
of the set\, rather than a superposition. It has long been conjectured th
at quantum walks can quadratically speed up this task when compared to sim
ple random walks. We show how a quantum sampling approach confirms this co
njecture for a limited set of graphs. For more general graphs however\, it
is conceivable that the quantum sampling problem cannot be solved efficie
ntly\, such that a different approach towards mixing is needed. We discuss
ideas in this direction.
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:A tight security reduction in the quantum random oracle model for
code-based signature schemes - André Chailloux\, INRIA Paris
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20171121T110000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20171121T120000
DTSTAMP;VALUE=DATE-TIME:20191207T100300Z
UID:334
DESCRIPTION:Quantum secure signature schemes have a lot of attention recen
tly\, in particular because of the NIST call to standardize quantum safe c
ryptography. However\, only few signature schemes can have concrete quantu
m security because of technical difficulties associated with the Quantum R
andom Oracle Model (QROM). In this paper\, we show that code-based signatu
re schemes based on the full domain hash paradigm can behave very well in
the QROM i.e. that we can have tight security reductions. We also study qu
antum algorithms related to the underlying code-based assumption. Finally\
, we apply our reduction to a concrete example: the SURF signature scheme.
We provide parameters for 128 bits of quantum security in the QROM and sh
ow that the obtained parameters are competitive compared to other similar
quantum secure signature schemes. \n\nJoint work with Thomas Debris-Alazar
d
LOCATION:Salle 1007
END:VEVENT
BEGIN:VEVENT
SUMMARY:Rapid Mixing of Local Graph Dynamics - Laurent Massoulié\, MSR-In
ria
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20171114T140000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20171114T150000
DTSTAMP;VALUE=DATE-TIME:20191207T100300Z
UID:336
DESCRIPTION:Graph dynamics arise naturally in many contexts. For instance
in peer-to-peer networks\, a participating peer may replace an existing co
nnection with one neighbour by a new connection with a neighbour's neighbo
ur. Several such local rewiring rules have been proposed to ensure that pe
er-to-peer networks achieve good connectivity properties (e.g. high expans
ion) in equilibrium. However it has remained an open question whether ther
e existed such rules that also led to fast convergence to equilibrium. In
this work we provide an affirmative answer: We exhibit a local rewiring ru
le that converges to equilibrium after each participating node has undergo
ne only a number of rewirings that is poly-logarithmic in the system size.
The proof involves consideration of the whole isoperimetric profile of th
e graph\, and may be of independent interest.\n\nThis is joint work with R
émi Varloot.
LOCATION:3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:On Distributed Algorithms - Claire Mathieu - Pierre Fraigniaud\, D
I ENS\, IRIF - IRIF\, CNRS
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20171128T100000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20171128T110000
DTSTAMP;VALUE=DATE-TIME:20191207T100300Z
UID:403
DESCRIPTION:First lecture from Claire Mathieu at Collège de France on Alg
orithms (at 10am)\, followed by a talk from Pierre Fraigniaud on Distribut
ed Algorithms (at 11am).\n\nAdditional information: http://www.college-de-
france.fr/site/claire-mathieu/course-2017-11-28-10h00.htm
LOCATION:Collège de France\, Amphithéâtre Maurice Halbwachs - Marcelin
Berthelot
END:VEVENT
BEGIN:VEVENT
SUMMARY:Community Detection - Claire Mathieu - Laurent Massoulié\, DI ENS
\, IRIF - INRIA
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20171205T100000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20171205T110000
DTSTAMP;VALUE=DATE-TIME:20191207T100300Z
UID:404
DESCRIPTION:Second lecture from Claire Mathieu at Collège de France on Al
gorithms (at 10am)\, followed by a talk from Laurent Massoulié on Communi
ty Detection (at 11am).\n\nAdditional information: http://www.college-de-f
rance.fr/site/claire-mathieu/course-2017-12-05-10h00.htm
LOCATION:Collège de France\, Amphithéâtre Maurice Halbwachs - Marcelin
Berthelot
END:VEVENT
BEGIN:VEVENT
SUMMARY:On Static and Dynamic Pricing - Claire Mathieu - Amos Fiat\, DI EN
S\, IRIF - University of Tel-Aviv
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20171212T100000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20171212T110000
DTSTAMP;VALUE=DATE-TIME:20191207T100300Z
UID:405
DESCRIPTION:Third lecture from Claire Mathieu at Collège de France on Alg
orithms (at 10am)\, followed by a talk from Amos Fiat on Static and Dynami
c Pricing (at 11am).\n\nAdditional information: http://www.college-de-fran
ce.fr/site/claire-mathieu/course-2017-12-12-10h00.htm
LOCATION:Collège de France\, Amphithéâtre Maurice Halbwachs - Marcelin
Berthelot
END:VEVENT
BEGIN:VEVENT
SUMMARY:On Analytic Combinatorics - Claire Mathieu - Bruno Salvy\, DI ENS\
, IRIF - INRIA
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20171219T100000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20171219T110000
DTSTAMP;VALUE=DATE-TIME:20191207T100300Z
UID:406
DESCRIPTION:Fourth lecture from Claire Mathieu at Collège de France on Al
gorithms (at 10am)\, followed by a talk from Bruno Salvy on Analytic Combi
natorics (at 11am).\n\nAdditional information: http://www.college-de-franc
e.fr/site/claire-mathieu/course-2017-12-19-10h00.htm
LOCATION:Collège de France\, Amphithéâtre Maurice Halbwachs - Marcelin
Berthelot
END:VEVENT
BEGIN:VEVENT
SUMMARY:On Sampling and Approximate Counting - Claire Mathieu - Mark Jerru
m\, DI ENS\, IRIF - Queen Mary\, University of London
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20180109T100000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20180109T110000
DTSTAMP;VALUE=DATE-TIME:20191207T100300Z
UID:407
DESCRIPTION:Fifth lecture from Claire Mathieu at Collège de France on Alg
orithms (at 10am)\, followed by a talk from Mark Jerrum on Sampling and Ap
proximate Counting (at 11am).\n\nAdditional information: http://www.colleg
e-de-france.fr/site/claire-mathieu/course-2018-01-09-10h00.htm
LOCATION:Collège de France\, Amphithéâtre Maurice Halbwachs - Marcelin
Berthelot
END:VEVENT
BEGIN:VEVENT
SUMMARY:On Algorithms and Fairness - Claire Mathieu - Jon Kleinberg\, DI E
NS\, IRIF - Cornell University
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20180116T100000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20180116T110000
DTSTAMP;VALUE=DATE-TIME:20191207T100300Z
UID:408
DESCRIPTION:Sixth lecture from Claire Mathieu at Collège de France on Alg
orithms (at 10am)\, followed by a talk from Jon Kleinberg on Algorithms an
d Fairness (at 11am).\n\nAdditional information: http://www.college-de-fra
nce.fr/site/claire-mathieu/course-2018-01-16-10h00.htm
LOCATION:Collège de France\, Amphithéâtre Maurice Halbwachs - Marcelin
Berthelot
END:VEVENT
BEGIN:VEVENT
SUMMARY:On Game Theory Through the Computational Lens - Claire Mathieu - T
im Roughgarden\, DI ENS\, IRIF - Stanford University
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20180123T100000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20180123T110000
DTSTAMP;VALUE=DATE-TIME:20191207T100300Z
UID:409
DESCRIPTION:Seventh lecture from Claire Mathieu at Collège de France on A
lgorithms (at 10am)\, followed by a talk from Tim Roughgarden on Game Theo
ry Through the Computational Lens (at 11am).\n\nAdditional information: ht
tp://www.college-de-france.fr/site/claire-mathieu/course-2018-01-23-10h00.
htm
LOCATION:Collège de France\, Amphithéâtre Maurice Halbwachs - Marcelin
Berthelot
END:VEVENT
BEGIN:VEVENT
SUMMARY:On Algorithms Operating in Adversarial Conditions - Claire Mathieu
- Allison Bishop\, DI ENS\, IRIF - IEX and Columbia University
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20180130T100000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20180130T110000
DTSTAMP;VALUE=DATE-TIME:20191207T100300Z
UID:410
DESCRIPTION:Eighth lecture from Claire Mathieu at Collège de France on Al
gorithms (at 10am)\, followed by a talk from Allison Bishop on Algorithms
Operating in Adversarial Conditions (at 11am).\n\nAdditional information:
http://www.college-de-france.fr/site/claire-mathieu/course-2018-01-30-10h0
0.htm
LOCATION:Collège de France\, Amphithéâtre Maurice Halbwachs - Marcelin
Berthelot
END:VEVENT
BEGIN:VEVENT
SUMMARY:Incremental Update for Graph Rewriting - Jean Krivine\, IRIF
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20171212T140000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20171212T150000
DTSTAMP;VALUE=DATE-TIME:20191207T100300Z
UID:416
DESCRIPTION:Graph rewriting formalisms are well-established models for the
representation of biological systems such as protein-protein interaction
networks. The combinatorial complexity of these models usually prevents an
y explicit representation of the variables of the system\, and one has to
rely on stochastic simulations in order to sample the possible trajectorie
s of the underlying Markov chain. The bottleneck of stochastic simulation
algorithms is the update of the propensity function that describes the pro
bability that a given rule is to be applied next. In this talk we present
an algorithm based on a data structure\, called extension basis\, that can
be used to update the counts of predefined graph observables after a rule
of the model has been applied. \n\nReference: Boutillier P.\, Ehrhard T.\
, Krivine J. (2017) Incremental Update for Graph Rewriting. In: Yang H. (e
ds) Programming Languages and Systems. ESOP 2017. Lecture Notes in Compute
r Science\, vol 10201. Springer\, Berlin\, Heidelberg
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:Computing through Dynamics: Principles for Distributed Coordinatio
n - Emanuele Natale\, Max Planck Institute for Informatics
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20171214T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20171214T153000
DTSTAMP;VALUE=DATE-TIME:20191207T100300Z
UID:422
DESCRIPTION:We present analytical results regarding some simple randomized
protocols\, called dynamics\, for solving fundamental distributed consens
us problems\, together with examples on how to use them to build lightweig
ht algorithms for other important distributed problems. More specifically\
, we provide an overview of the theory regarding several dynamics such as
the 3 Majority\, the Averaging and the Undecided-State ones\, and we show
how to use them to solve plurality consensus\, distributed clustering\, cl
ock synchronization and information spreading. \n Motivated by application
s to systems whose complexity is in-between biological and human-made ones
\, we focus mainly on unstructured and random interaction models\, and we
also deal with scenarios in which the communication is affected by noise o
r when a self-stabilizing protocol is required.
LOCATION:Salle 1016
END:VEVENT
BEGIN:VEVENT
SUMMARY:The Infinite Server Problem - Philip Lazos\, Oxford
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20180117T110000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20180117T120000
DTSTAMP;VALUE=DATE-TIME:20191207T100300Z
UID:429
DESCRIPTION:We study a variant of the k-server problem\, the infinite serv
er problem\, in which infinitely many servers reside initially at a partic
ular point of the metric space and serve a sequence of requests. In the fr
amework of competitive analysis\, we show a surprisingly tight connection
between this problem and the (h\,k)-server problem\, in which an online al
gorithm with k servers competes against an offline algorithm with h server
s. Specifically\, we show that the infinite server problem has bounded com
petitive ratio if and only if the (h\,k)-server problem has bounded compet
itive ratio for some k=O(h). We give a lower bound of 3.146 for the compet
itive ratio of the infinite server problem\, which implies the same lower
bound for the (h\,k)-server problem even when k/h→∞ and holds also for
the line metric\; the previous known bounds were 2.4 for general metric s
paces and 2 for the line. For weighted trees and layered graphs we obtain
upper bounds\, although they depend on the depth. Of particular interest i
s the infinite server problem on the line\, which we show to be equivalent
to the seemingly easier case in which all requests are in a fixed bounded
interval away from the original position of the servers. This is a specia
l case of a more general reduction from arbitrary metric spaces to bounded
subspaces. Unfortunately\, classical approaches (double coverage and gene
ralizations\, work function algorithm\, balancing algorithms) fail even fo
r this special case.
LOCATION:Salle 2015
END:VEVENT
BEGIN:VEVENT
SUMMARY:Computing huge subspaces of diagonal harmonic polynomials: symmetr
ies to the rescue! - Nicolas Thiery\, Université Paris Sud
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20180116T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20180116T153000
DTSTAMP;VALUE=DATE-TIME:20191207T100300Z
UID:433
DESCRIPTION:Last spring\, I visited François Bergeron and we worked on hi
s favorite objects: the spaces H(n\,k) of diagonal harmonic polynomials in
k sets of n variables. Those spaces connect to many areas of algebraic co
mbinatorics\, representation theory and beyond\, and the case H(n\,2) beca
me famous a decade ago with the n! conjecture and its proof by Haiman.\n\n
To fuel his ongoing studies François needed to compute the structure of H
(5\,6). This is a space of dimension 6.10^5 made of polynomials in 30 vari
ables of degree up to 15\, each having thousands of terms.\n\nIn this talk
\, I'll explain how the calculation can now be completed in 45 minutes wit
h a dozen cores and ~15Go of memory. This exploits a combination of strate
gies (symmetries\, representation theory of the symmetric and general line
ar group\, ...)\, each of which reduces the complexity in time and memory
by one or two orders of magnitude.\n\nThere will be little prerequisites a
nd it's my hope that some strategies (and maybe the code!) could be used i
n other contexts.
LOCATION:Salle 3014
END:VEVENT
BEGIN:VEVENT
SUMMARY:Online Maximum Matching with Recourse - Shendan Jin\, LIP6
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20180206T110000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20180206T120000
DTSTAMP;VALUE=DATE-TIME:20191207T100300Z
UID:438
DESCRIPTION:We study the online maximum matching problem with recourse in
a model in which the edges are associated with a known recourse parameter
k. An online algorithm for this problem has to maintain a valid matching w
hile edges of the underlying graph are presented one after the other. At a
ny moment the algorithm can decide to include an edge into the matching or
to exclude it\, under the restriction that at most k actions per edge tak
e place\, where k is typically a small constant. This problem was introduc
ed and studied in the context of general online packing problems with reco
urse by [Avitabile\, Mathieu\, Parkinson\, 2013]\, whereas the special cas
e k=2 has been studied by [Boyar et al.\, 2017].\n\nIn the first part of t
his paper\, we consider the edge arrival model\, in which an arriving edge
never disappears from the graph. Here\, we first show an improved analysi
s on the performance of the algorithm given in [AMP\, 2013]\, by exploitin
g the structure of the specific problem. In addition\, we extend the resul
t of [Boyar et al.\, 2017] and show that the greedy algorithm has ratio 3/
2 for every even positive k and ratio 2 for every odd k. Moreover\, we pre
sent and analyze L-Greedy --- an improvement of the greedy algorithm --- w
hich for small values of k outperforms the algorithm of [AMP\, 2013]. In t
erms of lower bounds\, we show that no deterministic algorithm better than
1+1/(k−1) exists\, improving upon the lower bound of 1+1/k shown in [AM
P\, 2013].\n\nThe second part of the paper is devoted to the edge arrival/
departure model\, which is the fully dynamic variant of the online matchin
g problem with recourse. The analysis of L-Greedy carries through in this
model\; moreover we show a general lower bound of (k2−3k+3)/(k2−4k+5)
for all even k≥4 and provide the stronger bound of 10/7 for k=4. For k
∈{2\,3}\, the competitive ratio is 3/2.\n\nJoint work with Spyros Angelo
poulos and Christoph Dürr.
LOCATION:Salle 1007
END:VEVENT
BEGIN:VEVENT
SUMMARY:Efficient decoding of random errors for quantum expander codes - A
ntoine Grospellier\, INRIA
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20180213T110000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20180213T120000
DTSTAMP;VALUE=DATE-TIME:20191207T100300Z
UID:503
DESCRIPTION:We show that quantum expander codes\, a constant-rate family o
f quantum LDPC codes\, with the quasi-linear time decoding algorithm of Le
verrier\, Tillich and Zémor can correct a constant fraction of random err
ors with very high probability. This is the first construction\nof a const
ant-rate quantum LDPC code with an efficient decoding algorithm that can c
orrect a linear number of random errors with a negligible failure probabil
ity. Finding codes with these properties is also motivated by Gottesman’
s construction of fault tolerant schemes with constant space overhead. In
order to obtain this result\, we study a notion of α-percolation: for a r
andom subset E of vertices of a given graph\, we consider the size of the
largest connected α-subset of E\, where X is an α-subset of E if |X ∩
E| ≥ α|X|.
LOCATION:Salle 1007
END:VEVENT
BEGIN:VEVENT
SUMMARY:Do-It-Yourself randomness over Device-Independent randomness - Cha
rles Bennett
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20180205T140000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20180205T150000
DTSTAMP;VALUE=DATE-TIME:20191207T100300Z
UID:520
DESCRIPTION:
LOCATION:Salle 2018
END:VEVENT
BEGIN:VEVENT
SUMMARY:Local Search for Geometric Optimization Problems. - Nabil Mustafa\
, ESIEE
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20180212T140000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20180212T150000
DTSTAMP;VALUE=DATE-TIME:20191207T100300Z
UID:531
DESCRIPTION:Local-search is an intuitive approach towards solving combinat
orial optimization problems: start with any feasible solution\, and try to
improve it by local improvements. Like other greedy approaches\, it can f
ail to find the global optimum by getting stuck on a locally optimal solut
ion. In this talk I will present the ideas and techniques behind the use o
f local-search in the design of provably good approximation algorithms for
some combinatorial problems\, such as independent sets\, vertex cover\, d
ominating sets in geometric intersection graphs. The key unifying theme is
the analysis of local expansion in planar graphs. Joint work with Norbert
Bus\, Shashwat Garg\, Bruno Jartoux and Saurabh Ray.
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:Quantum online algorithms with restricted memory - Kamil Khadiev\,
University of Latvia
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20180327T110000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20180327T120000
DTSTAMP;VALUE=DATE-TIME:20191207T100300Z
UID:552
DESCRIPTION:An online algorithm is a well-known computational model for so
lving optimization problems. The defining property of this model is follow
ing. An algorithm reads an input piece by piece and should return output v
ariables after some of the input variables immediately\, even if the answe
r depends on the whole input. An online algorithm should return output for
minimizing an objective function. \n\nWe consider streaming algorithms an
d two-way automata as models for online algorithms. We compare quantum and
classical models in case of logarithmic memory and sublogarithmic memory.
\n\nWe get the following results for online streaming algorithms:\n- a qua
ntum online streaming algorithm with 1 qubit of memory and 1 advice bit ca
n be better than a classical online streaming algorithm with $o(\\log n)$
bits of memory and $o(\\log n)$ advice bits.\n- Quantum online streaming a
lgorithm with a constant size of memory and $t$ advice bits can be better
than deterministic online streaming algorithms with $t$ advice bits and un
limited computational power.\n- In a case of a polylogarithmic size of mem
ory\, quantum online streaming algorithms can be better than classical one
s even if they have advice bits.\n\nWe get the following results for two w
ay automata as an online algorithm for solving online minimization problem
s:\n- a two way automata with quantum and classical states for online mini
mization problems with a constant size of memory can be better than classi
cal ones even if they have advice bits.
LOCATION:Salle 1007
END:VEVENT
BEGIN:VEVENT
SUMMARY:Distributed coloring of graphs with fewer colors - Pierre Aboulker
\, Université Grenoble-Alpes\, Labo G-SCOP
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20180410T110000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20180410T120000
DTSTAMP;VALUE=DATE-TIME:20191207T100300Z
UID:560
DESCRIPTION:We give an efficient (polylog(n) rounds) algorithm that colors
a graph with few colors in the distributed setting (LOCAL model). Among
other things\, we will see that this algorithm 6-colors planar graphs (usi
ng 1 less color than the previous best algorithm of Goldberg\, Plotkin\, a
nd Shannon) and will show that one cannot 4-color planar graph in o(n) rou
nds. \n\nThis is a joint work with Bousquet\, Bonamy\, and Esperet.
LOCATION:Salle 1007
END:VEVENT
BEGIN:VEVENT
SUMMARY:On the complexity of defective coloring. - Valia Mitsou\, IRIF
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20180320T110000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20180320T120000
DTSTAMP;VALUE=DATE-TIME:20191207T100300Z
UID:563
DESCRIPTION:In defective coloring\, we are given a graph G and two integer
s c\, ∆* and are asked if we can c-color G so that the maximum\ndegree i
nduced by any color class is at most ∆*. This problem is a generalizatio
n of proper coloring\, for which Δ* = 0.\n\nDefective coloring\, like pro
per coloring\, has many applications\, for example in scheduling (assign j
obs to machines which can work on up to Δ* jobs in parallel)\, or in radi
o networks (assign frequencies to antennas with some slack\, that is\, an
antenna can be assigned the same frequency with up to Δ* other antennas w
ithin its range without a signal conflict).\n\nWe will present some algori
thmic and complexity results on this problem in classes of graphs where pr
oper coloring is easy: on the one hand\, we will consider subclasses of pe
rfect graphs\, namely cographs and chordal graphs\; on the other hand we w
ill talk about structural parameterizations\, such as treewidth and feedba
ck vertex set.\n\nJoint work with Rémy Belmonte (University of Electro-Co
mmunications\, Tokyo) and Michael Lampis (Lamsade\, Université Paris Daup
hine) that appeared in WG '17 and in STACS '18.
LOCATION:Salle 1007
END:VEVENT
BEGIN:VEVENT
SUMMARY:The Feynman-Kitaev computer's clock: bias\, gaps\, idling and puls
e tuning - Libor Caha\, RCQI Bratislava
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20180411T140000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20180411T150000
DTSTAMP;VALUE=DATE-TIME:20191207T100300Z
UID:581
DESCRIPTION:We present a collection of results about the clock in Feynman'
s computer construction and Kitaev's Local Hamiltonian problem. First\, by
analyzing the spectra of quantum walks on a line with varying endpoint te
rms\, we find a better lower bound on the gap of the Feynman Hamiltonian\,
which translates into a less strict promise gap requirement for the QMA-c
omplete Local Hamiltonian problem. We also translate this result into the
language of adiabatic quantum computation. Second\, introducing an idling
clock construction with a large state space but fast Cesaro mixing\, we pr
ovide a way for achieving an arbitrarily high success probability of compu
tation with Feynman's computer with only a logarithmic increase in the num
ber of clock qubits. Finally\, we tune and thus improve the costs (localit
y\, gap scaling) of implementing a (pulse) clock with a single excitation.
\n\n\nJoint work with Zeph Landau and Daniel Nagaj
LOCATION:Salle 1007
END:VEVENT
BEGIN:VEVENT
SUMMARY:Shortest Paths in Networks with Unreliable Directions - Steve Alpe
rn\, University of Wariwick\, UK
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20180529T110000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20180529T120000
DTSTAMP;VALUE=DATE-TIME:20191207T100300Z
UID:588
DESCRIPTION:The work of Korman and others\, based on investigations of nav
igational techniques of ‘crazy ants’\, leads to the following problem:
Let Q be a network with given arc lengths\, and let H be a ‘home’ no
de. At each node a permanent direction is given (one of the adjacent arcs)
which leads to a shortest path path from that node to H with probability
p less than one. Starting from a node S\, a searcher chooses the given
direction at each reached node with probability q\; otherwise he chooses
randomly. He arrives home at node H in expected time T=T(S\,H\,p\,q).
How should q be chosen to minimize T? Perhaps when reaching a node the se
archer sees its degree k so chooses the given direction with probability
q(k). Related problems have been studied for tree from a graph theoretical
perspective.
LOCATION:Salle 1007
END:VEVENT
BEGIN:VEVENT
SUMMARY:Improved quantum linear system solvers and applications to machine
learning - Anupam Prakash\, IRIF
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20180522T110000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20180522T120000
DTSTAMP;VALUE=DATE-TIME:20191207T100300Z
UID:596
DESCRIPTION:I will describe recent results in the QRAM model that improve
the sparsity dependance for quantum linear system solvers to \\mu(A) = \\m
in (||A||_F\, ||A||_1) where ||A||_1 is the maximum l-1 norm of the rows a
nd columns of A and ||A||_F is the Frobenius norm. These results achieve a
worst case quadratic speedup over the HHL algorithm and its improvements
and exponential speedups for some cases. I will also present some applicat
ions of the improved linear system solvers to quantum machine learning.
LOCATION:Salle 1007
END:VEVENT
BEGIN:VEVENT
SUMMARY:Learnability and quantum computation - Andrea Rocchetto\, Oxford -
UCL
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20180605T110000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20180605T120000
DTSTAMP;VALUE=DATE-TIME:20191207T100300Z
UID:605
DESCRIPTION:Computational learning theory provides a mathematical framewor
k for rigorously formulating learning problems from both a statistical and
computational perspective. During this talk I will present two independen
t results at the interplay of learning theory and quantum computation. Fir
st\, I will address the problem: “can we learn faster with a quantum com
puter?”. In particular\, I will discuss the learnability of the class of
boolean functions that can be expressed as polynomial size formulae in di
sjunctive normal form (DNF) and show that this is efficiently quantum PAC
learnable under product distributions. The learnability of DNFs is a centr
al problem in learning theory and the best known classical algorithm (usin
g standard ways to access the function) runs in superpolynomial time. Seco
nd\, I will discuss the problem “what it means to learn a quantum state
and can we do that efficiently?”. Here\, building on a model developed b
y Aaronson in 2007\, I will present a class of states\, namely stabiliser
states\, that can be learned using only a linear number of measurements an
d polynomial - classical - computation. Part of the results are joint work
with Varun Kanade and Simone Severini.
LOCATION:Salle 1007
END:VEVENT
BEGIN:VEVENT
SUMMARY:Sketching as tool for faster quantum simulation - Leonard Wossnig\
, University College London
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20180619T110000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20180619T120000
DTSTAMP;VALUE=DATE-TIME:20191207T100300Z
UID:606
DESCRIPTION:Following the works of Drineas et al. (2004)\, Randomised Nume
rical Linear Algebra (RNLA) applications have enjoyed a increasing surge o
f interest in the classical algorithms community. Following their success
we recently demonstrated a classical algorithm based on the Nystroem metho
d which allows us to efficiently simulate dynamics of quantum system with
specific structural conditions. We briefly introduce the most basic RNLA a
lgorithm by Drineas et al. to give an overview of the topic and then outli
ne our own recent work. We follow with a discussion of potential applicati
on of related methods\, including spectral sparsification\, in quantum alg
orithms for Hamiltonian Simulation and quantum linear systems\; We finish
with a short description of own current work related to spectral sparsific
ation (Spielmann & Teng 2011) for Hamiltonian simulation.
LOCATION:Salle 1007
END:VEVENT
BEGIN:VEVENT
SUMMARY:Popular Matchings: A Tale of Two Classes - Kavitha Telikepalli\, T
ata Institute of Fundamental Research
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20180904T110000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20180904T120000
DTSTAMP;VALUE=DATE-TIME:20191207T100300Z
UID:635
DESCRIPTION:We consider popular matching problems in a stable marriage ins
tance G. A matching M is popular if it does not lose a head-to-head electi
on against any matching\, where each vertex casts a vote for the matching
where it gets a better assignment. Popular matchings always exist in G sin
ce every stable matching is popular. Algorithmic questions for several pop
ular matching problems have been studied in the last few years: these incl
ude finding a max-size popular matching\, finding a popular matching with
our favorite edge(s) in it\, finding a max-weight popular (mixed) matching
when there are edge weights. We will see efficient algorithms for some of
these problems.\n\nInterestingly\, all tractability results in popular ma
tchings seem to reduce the popular matching problem to an appropriate ques
tion in either stable matchings or dominant matchings. Dominant matchings
always exist in G and form a subclass of max-size popular matchings while
stable matchings form a subclass of min-size popular matchings. We recentl
y showed that deciding if G admits a popular matching that is neither stab
le nor dominant is NP-hard. This implies a tight 1/2-factor approximation
for the max-weight popular matching problem in G and the hardness of findi
ng a popular matching in a non-bipartite graph.\n\n[Joint work with Agnes
Cseh\, Yuri Faenza\, Chien-Chung Huang\, Vladlena Powers\, and Xingyu Zhan
g.]
LOCATION:Salle 1007
END:VEVENT
BEGIN:VEVENT
SUMMARY:A Quadratic Size-Hierarchy Theorem for Small-Depth Multilinear For
mulas - Suryajith Chillara\, IIT Bombay
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20181016T113000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20181016T123000
DTSTAMP;VALUE=DATE-TIME:20191207T100300Z
UID:664
DESCRIPTION:It is a fundamental problem in the study of computational comp
lexity to understand if access to more resources would mean strictly more
computational power. In classical complexity\, we have seen such examples
in terms of Time Hierarchy and Space Hierarchy theorems. Here\, time and s
pace are the resources. It is natural to ask such a question in the settin
g of algebraic complexity setting. Here\, access to more resources transla
tes to allowing the model to perform more number of operations which in tu
rn is allowing the "algebraic formulas" to have larger size.\n\n\nArithmet
ic formulas are directed trees where the leaves are labelled by variables
and elements of the field\, and internal vertices are labelled by + or x.
Every internal vertex computes a polynomial by operating on its inputs. It
is easy to see that they are a natural model of computation of polynomial
s\, syntactically (symbolically). The size of the arithmetic formulas refe
rs to the number of + and x operations needed to compute the polynomial.\n
\nRephrasing the question in the algebraic setting we ask the following: f
or any s\, \\varepsilon >0\, are there polynomial computations that can be
efficiently computed by arithmetic formulas of size s but not by any arit
hmetic formula of size s^{1-\\varepsilon}?\n\nIn this talk\, we will restr
ict ourselves to arithmetic formulas where computation at every vertex is
a multilinear polynomial and here we show explicit separations between the
expressive powers of multilinear formulas of small-depth and all polynomi
al sizes. The multilinear restriction is a reasonable one since most polyn
omials of interest are indeed multilinear.\n\nFormally\, we will show that
for any s = poly(n) and \\delta > 0\, we show that there are explicit pol
ynomial families that have multilinear formulas of size at most s but no '
small'-depth multilinear formulas of size less than s^{0.5 - \\delta}. Our
proof can be viewed as a derandomization of a lower bound technique of Ra
z (JACM 2009) using \\epsilon-biased spaces.\n\n(Joint work with Nutan Lim
aye and Srikanth Srinivasan. Appeared in the proceedings of ICALP 2018.)
LOCATION:Salle 1007
END:VEVENT
BEGIN:VEVENT
SUMMARY:Lifting theorems for Equality - Sagnik Mukhopadhyay\, Computer Sci
ence Institute of Charles University
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20181127T110000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20181127T120000
DTSTAMP;VALUE=DATE-TIME:20191207T100300Z
UID:709
DESCRIPTION:We show a deterministic simulation (or lifting) theorem for co
mposed problems $f \\circ \\EQ_n$ where the inner function (the gadget) is
Equality on $n$ bits. When $f$ is a total function on $p$ bits\, it is ea
sy to show via a rank argument that the communication complexity of $f\\ci
rc \\EQ_n$ is $\\Omega(\\deg(f) \\cdot n)$. However\, there is a surprisin
g counter-example of a partial function $f$ on $p$ bits\, such that any co
mpletion $f'$ of $f$ has $\\deg(f') = \\Omega(p)$\, and yet $f \\circ \\EQ
_n$ has communication complexity $O(n)$. Nonetheless\, we are able to show
that the communication complexity of $f \\circ \\EQ_n$ is at least $D(f)
\\cdot n$ for a complexity measure $D(f)$ which is closely related to the
$\\AND$-query complexity of $f$ and is lower-bounded by the logarithm of t
he leaf complexity of $f$. As a corollary\, we also obtain lifting theorem
s for the set-disjointness gadget\, and a lifting theorem in the context o
f parity decision-trees\, for the $\nOR$ gadget. \n \nIn this talk\, I wil
l talk about simulations or lifting theorems in general from a previous wo
rk of Chattopadhyay et al.\, and lifting theorem for Equality in particula
r---especially why the general recipe of Chattopadhyay et al. does not wor
k for Equality. I will also mention an application of this technique to pr
ove tight communication lower bound for Gap-Equality problem. This is a jo
int work with Bruno Loff.
LOCATION:Salle 1007
END:VEVENT
BEGIN:VEVENT
SUMMARY:Compressing Vector OLE - Geoffroy Couteau\, KIT
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20181204T110000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20181204T120000
DTSTAMP;VALUE=DATE-TIME:20191207T100300Z
UID:710
DESCRIPTION:In this talk\, I will discuss recent results on the problem of
compressing correlated (pseudo) random strings.\n\nOblivious linear-funct
ion evaluation (OLE) is a secure two-party protocol allowing a receiver to
learn any linear combination of a pair of field elements held by a sender
. OLE serves as a common building block for secure computation of arithmet
ic circuits\, analogously to the role of oblivious transfer (OT) for boole
an circuits. A useful extension of OLE is vector OLE (VOLE)\, allowing the
receiver to learn any linear combination of two vectors held by the sende
r. In several applications of OLE\, one can replace a large number of inst
ances of OLE by a smaller number of long instances of VOLE. This motivates
the goal of amortizing the cost of generating long instances of VOLE.\n\n
I will present a new approach for generating pseudo-random instances of VO
LE via a deterministic local expansion of a pair of short correlated seeds
and no interaction. This provides the first example of compressing a non-
trivial and cryptographically useful correlation with good concrete effici
ency. This result enjoys several applications\; I will discuss in particul
ar an application to the construction of non-interactive zero-knowledge pr
oofs with reusable preprocessing.\n\nOur VOLE generators are based on a no
vel combination of function secret sharing (FSS) for multi-point functions
and linear codes in which decoding is intractable. Their security can be
based on variants of the learning parity with noise (LPN) assumption over
large fields that resist known attacks. I will also discuss recent excitin
g developments toward the 'dream goal' of compressing arbitrary pseudorand
om bilinear correlations.
LOCATION:Salle 1007
END:VEVENT
BEGIN:VEVENT
SUMMARY:An application of communication complexity to cryptography - Balth
azar Bauer\, ENS
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20190129T110000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20190129T120000
DTSTAMP;VALUE=DATE-TIME:20191207T100300Z
UID:711
DESCRIPTION:The hash function are very important primitives in cryptology.
To use it\, we need to trust the designer. To solve this problem\, we can
combine several hash functions independently built. But we have to suppos
e that the designers could communicate. That's why we can reduce the secur
ity properties to communication complexity problems. After a presentation
of these reductions\, we will look in details the communication problems l
inked to these properties\, our knowledge\, new results about them. And at
the end the open problems that challenge us will be presented.
LOCATION:Salle 1007
END:VEVENT
BEGIN:VEVENT
SUMMARY:Distributed PCP Theorems for Hardness of Approximation in P - Avia
d Rubinstein\, Stanford
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20181122T140000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20181122T150000
DTSTAMP;VALUE=DATE-TIME:20191207T100300Z
UID:724
DESCRIPTION:We present a new model of probabilistically checkable proof (P
CP)\, which we call "Distributed PCP":\nA satisfying assignment (x in {0\,
1}^n) to a SAT instance is shared between two parties (Alice knows x_1\, .
.. x_{n/2}\, and Bob knows x_{n/2+1}\,...\,x_n).\nTheir goal is to jointly
write a PCP for x\, while exchanging little or no information.\n\nUsing o
ur new framework\, we obtain\, for the first time\, PCP-like hardness of a
pproximation results for problems in P.\n\nBased on joint works with Amir
Abboud\, Lijie Chen\, Shafi Goldwasser\, Kaifeng Lyu\, Guy Rothblum\, and
Ryan Williams.
LOCATION:Salle 1007
END:VEVENT
BEGIN:VEVENT
SUMMARY:Distributed Shortest Paths\, Exactly - Danupon Nanongkai\, KTH
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20190219T110000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20190219T120000
DTSTAMP;VALUE=DATE-TIME:20191207T100300Z
UID:772
DESCRIPTION:This talk concerns the problem of quickly computing distances
and shortest paths on distributed networks (the CONGEST model). There have
been many developments for this problem in the last few year\, resulting
in tight approximation schemes. This left open whether exact algorithms ca
n perform equally well. In this talk\, we will discuss some recent progres
s in answering this question. \nMost recent works that this talk is base
d on are with Sebastian Krinninger (FOCS 2018) and Aaron Bernstein (ArXiv
2018).
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:Faster k-SAT algorithms using biased-PPSZ - Uri Zwick\, Tel Aviv U
niversity
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20190226T110000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20190226T120000
DTSTAMP;VALUE=DATE-TIME:20191207T100300Z
UID:788
DESCRIPTION:The PPSZ algorithm\, due to Paturi\, Pudlak\, Saks and Zane\,
is currently the fastest known algorithm for the k-SAT problem\, for every
k>3. For 3-SAT\, a tiny improvement over PPSZ was obtained by Hertli. We
introduce a biased version of the PPSZ algorithm using which we obtain an
improvement over PPSZ for every k>=3. For k=3 we also improve on Herli's r
esult and get a much more noticeable improvement over PPSZ\, though still
relatively small. In particular\, for Unique 3-SAT\, we improve the curren
t bound from 1.308^n to 1.307^n.\n\nJoint work with Thomas Dueholm Hansen\
, Haim Kaplan and Or Zamir
LOCATION:Salle 1007
END:VEVENT
BEGIN:VEVENT
SUMMARY:Limitations of treewidth for problems beyond NP - Valia Mitsou\, I
RIF
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20190305T110000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20190305T120000
DTSTAMP;VALUE=DATE-TIME:20191207T100300Z
UID:796
DESCRIPTION:In this seminar\, we take a closer look at the parameterized c
omplexity of problems belonging in Σ^p_2 and Π^p_2\, the second level of
the polynomial hierarchy. We provide tight fine-grained bounds on their c
omplexity with respect to the most important structural graph parameter\,
the treewidth. We observe that these problems exhibit similar behavior: we
show that a variety of problems including Choosability\, ∃∀SAT\, alon
g with several problems from AI such as Abduction\, Abstract Argumentation
and others\, while they admit a $2^{2^{O(tw)}}$ algorithm\, they cannot b
e solved in time $2^{2^{o(tw)}}$ under the Exponential Time Hypothesis.
LOCATION:Salle 1007
END:VEVENT
BEGIN:VEVENT
SUMMARY:Quantum Fast-Forwarding: Markov Chains and Graph Property Testing
- Simon Apers\, INRIA
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20190528T110000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20190528T120000
DTSTAMP;VALUE=DATE-TIME:20191207T100300Z
UID:797
DESCRIPTION:I will introduce a new tool for quantum algorithms called quan
tum fast-forwarding (QFF). The tool uses quantum walks as a means to quadr
atically fast-forward a reversible Markov chain. In a number of quantum wa
lk steps that scales as the square root of the classical runtime\, and inv
ersely proportional to the 2-norm of the classical distribution\, it retri
eves a quantum superposition that encodes the classical distribution. This
shows that quantum walks can accelerate the transient dynamics of Markov
chains\, thereby complementing the line of results that proves the acceler
ation of their limit behavior.\n\nThis tool leads to speedups on random wa
lk algorithms in a very natural way. Specifically I will consider random w
alk algorithms for testing the graph expansion and clusterability\, and sh
ow that QFF allows to quadratically improve the dependency of the classica
l property testers on the random walk runtime. Moreover\, this new quantum
algorithm exponentially improves the space complexity of the classical te
ster to logarithmic. As a subroutine of independent interest\, I use QFF t
o determine whether a given pair of nodes lies in the same cluster or in s
eparate clusters. This solves a robust version of s-t connectivity\, relev
ant in a learning context for classifying objects among a set of examples.
The different algorithms crucially rely on the quantum speedup of the tra
nsient behavior of random walks.
LOCATION:Salle 1007
END:VEVENT
BEGIN:VEVENT
SUMMARY:Facilitating Student Information Acquisition in Matching Markets -
Jacob Leshno\, Chicago Booth
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20190301T150000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20190301T160000
DTSTAMP;VALUE=DATE-TIME:20191207T100300Z
UID:800
DESCRIPTION:We develop a tractable model for a matching market where stude
nts form preferences through costly information acquisition. As the market
outcome consists of both an assignment as well as the acquired informatio
n\, we study how the marketplace can direct both the allocation and the in
formation acquisition process. We define regret-free stable outcomes\, whe
re the matching is stable under the partial preferences and each student h
as acquired information optimally\, as if she were last to market\; regret
-free stable outcomes are optimal in settings where students make decentra
lized decisions about how to acquire information and can wait for more inf
ormation.\nWe show that regret-free stable outcomes always exist and can b
e characterized by cutoffs. However\, we also show that regret-free stable
outcomes cannot be discovered under practical restrictions – any discov
ery process can reach deadlocks where every student would like to wait for
additional market information before acquiring information. Instead\, his
torical information can facilitate the implementation of approximate regre
t-free stable outcomes\, suggesting that an important role of matching mar
kets is to aggregate information from multiple years. We also provide a me
thod for bootstrapping information acquisition when historical information
is not available.
LOCATION:Salle 1007
END:VEVENT
BEGIN:VEVENT
SUMMARY:On proof systems based on branching programs - Alexander Knop\, UC
San Diego
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20190326T110000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20190326T120000
DTSTAMP;VALUE=DATE-TIME:20191207T100300Z
UID:807
DESCRIPTION:It is well known that there is a connection between resolution
complexity of a formula and complexity of (very weak) branching programs
for the corresponding search problem. In the talk\, we will discuss proof
systems that allow to generalize this statement and explain the lower bou
nds for these proof systems. In order to achieve this lower bounds\, we sh
ow how to transform functions with a high fixed-partition communication co
mplexity into functions with a high best-partition communication complexit
y and as a result\, we translate the landscape of fixed-partition communic
ation complexity classes into the landscape of best-partition communicatio
n complexity classes.
LOCATION:Salle 1007
END:VEVENT
BEGIN:VEVENT
SUMMARY:Pre- and post-quantum Diffie-Hellman from groups\, actions\, and i
sogenies - Benjamin Smith\, INRIA\, LIX
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20190507T110000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20190507T120000
DTSTAMP;VALUE=DATE-TIME:20191207T100300Z
UID:831
DESCRIPTION:Diffie-Hellman key exchange is at the foundations of public-ke
y cryptography\, but conventional group-based Diffie-Hellman is vulnerable
to Shor's quantum algorithm. A range of 'post-quantum Diffie-Hellman' pro
tocols have been proposed to mitigate this threat\, including the Couveign
es\, Rostovtsev-Stolbunov\, SIDH\, and CSIDH schemes\, all based on the co
mbinatorial and number-theoretic structures formed by isogenies of ellipti
c curves. Pre-and post-quantum Diffie-Hellman schemes resemble each other
at the highest level\, but the further down we dive\, the more differences
emerge-differences that are critical when we use Diffie-Hellman as a basi
c component in more complicated constructions. In this survey we compare a
nd contrast pre-and post-quantum Diffie-Hellman algorithms\, highlighting
some important subtleties.
LOCATION:Salle 1007
END:VEVENT
BEGIN:VEVENT
SUMMARY:Statistical Inference Under Local Information Constraints - Cléme
nt Canonne\, Stanford University
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20190416T110000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20190416T120000
DTSTAMP;VALUE=DATE-TIME:20191207T100300Z
UID:857
DESCRIPTION:Independent samples from an unknown probability distribution p
on a domain of size k are distributed across n players\, with each player
holding one sample. Each player can send a message to a central referee i
n a simultaneous message passing (SMP) model of communication\, whose goal
is to solve a pre-specified inference problem on p. The catch\, however\,
is that each player cannot simply send their own sample to the referee\;
instead\, the message they send must obey some (local) information constra
int. For instance\, each player may be limited to communicating only L bit
s\, where L << log k\; or they may seek to reveal as little information as
possible\, and preserve local differential privacy.\n\nWe propose a gener
al formulation for inference problems in this distributed setting\, and in
stantiate it to two fundamental inference questions\, learning and uniform
ity testing. We study the role of randomness for those questions\, and obt
ain striking separations between public- and private-coin protocols for th
e latter\, while showing the two settings are equally powerful for the for
mer. (Put differently\, sharing with your neighbors does help a lot for th
e test\, but not really for the learning.)\n\nBased on joint works with Ja
yadev Acharya (Cornell University)\, Cody Freitag (Cornell University)\, a
nd Himanshu Tyagi (IISc Bangalore).
LOCATION:Salle 1007
END:VEVENT
BEGIN:VEVENT
SUMMARY:Discrete logarithm and Diffie-Hellman problems in identity black-b
ox groups - Miklos Santha\, IRIF\, CQT
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20190521T110000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20190521T120000
DTSTAMP;VALUE=DATE-TIME:20191207T100300Z
UID:876
DESCRIPTION:We investigate the computational complexity of the discrete lo
garithm\, the computational Diffie-Hellman and the decisional Diffie-Hellm
an problems in some identity black-box groups G_{p\,t}\, where p is a prim
e number and t is a positive integer. These are defined as quotient groups
of vector space Z_p^{t+1} by a hyperplane H given through an identity ora
cle. While in general black-box groups with unique encoding these computat
ional problems are classically all hard and quantumly all easy\, we find t
hat in the groups G_{p\,t} the situation is more contrasted. We prove that
while there is a polynomial time probabilistic algorithm to solve the dec
isional Diffie-Hellman problem in G_{p\,1}\, the probabilistic query compl
exity of all the other problems is Omega(p) and their quantum query comple
xity is Omega(\\sqrt{p}). Our results therefore provide a new example of a
group where the computational and the decisional Diffie-Hellman problems
have widely different complexity. \n\nJoint work with Gabor Ivanyos and An
toine Joux.
LOCATION:Salle 1007
END:VEVENT
BEGIN:VEVENT
SUMMARY:Constrained Submodular Maximization via Greedy Local Search - Baru
ch Schieber\, NJIT
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20190606T140000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20190606T150000
DTSTAMP;VALUE=DATE-TIME:20191207T100300Z
UID:886
DESCRIPTION:We present a simple combinatorial 1/2(1-1/e^2)-approximation a
lgorithm for maximizing a monotone submodular function subject to a knapsa
ck and a matroid constraint. This classic problem is known to be hard to a
pproximate within factor better than 1-1/e. We extend the algorithm to yie
ld 1/(k+1)(1-1/e^(k+1)) approximation for submodular maximization subject
to a single knapsack and k matroid constraints\, for any fixed k > 1. Our
algorithms\, which combine the greedy algorithm of [Khuller\, Moss and Na
or\, 1999] and [Sviridenko\, 2004] with local search\, show the power of t
his natural framework in submodular maximization with combined constraints
.\n\nThis is joint work with Kanthi Sarpatwar and Hadas Shachnai
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:Evolutionary Algorithms -- From Theory to Practice and Back - Caro
la Doerr\, CNRS\, LIP6 Sorbonne University
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20190624T110000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20190624T120000
DTSTAMP;VALUE=DATE-TIME:20191207T100300Z
UID:894
DESCRIPTION:Most real-world optimization problems do not have an explicit
problem formulation\, but only allow to compute the quality of selected so
lution candidates. Solving such black-box optimization problems requires i
terative procedures which use the feedback gained from previous evaluation
s to determine the strategy by which the next solution candidates are gene
rated. Many black-box optimization algorithms\, such as Simulated Annealin
g\, Evolutionary Algorithms\, Swarm Intelligence Algorithms\, are randomiz
ed -- making it very difficult to analyze their performances mathematicall
y.\n\nIn the last 15 years\, the theory of randomized black-box optimizati
on has advanced considerably\, and has contributed to efficient optimizati
on by providing insights into the working principles of black-box optimiza
tion which are hard or impossible to obtain by empirical means. On the oth
er hand\, empirically-guided benchmarking has opened up new research direc
tions for theoretical investigations.\n\nIn this presentation we will disc
uss the state of the art in the theory of randomized black-box optimizatio
n algorithms. As part of this critical survey we will also mention a numbe
r of open questions and connections to other fields of Computer Science.
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:An Operational Characterization of Mutual Information in Algorithm
ic Information Theory - Andrei Romashchenko\, LIRMM
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20190702T110000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20190702T120000
DTSTAMP;VALUE=DATE-TIME:20191207T100300Z
UID:911
DESCRIPTION:We show that for every pair of strings (x\,y) the mutual infor
mation between x and y in the sense of Kolmogorov complexity is equal (wit
hin logarithmic precision) to the length of the longest shared secret key
that two parties\, one having x and the other one having y\, can establish
via a probabilistic protocol with interaction on a public channel. We ext
end this result to the setting of L>2 parties holding mutually correlated
strings x_1 ... x_L. [Joint work with Marius Zimand]
LOCATION:Salle 1007
END:VEVENT
BEGIN:VEVENT
SUMMARY:Fast Approximation Schemes for Clustering in Doubling Metrics - Da
vid Saulpic\, ENS
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20190910T110000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20190910T120000
DTSTAMP;VALUE=DATE-TIME:20191207T100300Z
UID:920
DESCRIPTION:We consider classical clustering problems such as k-Median or
k-Means in metric spaces that generalize Euclidean space\, namely doubling
metrics. We give a surprisingly simple framework that yields nearly linea
r-time approximation schemes for each problem\, making a significant impro
vement over the state-of-the-art algorithms which run in time n^(d/\\eps)^
O(d)\, for metric of doubling dimension d. Moreover\, we show how to exten
d the techniques used to get the first efficient approximation schemes for
the problems of prize-collecting $k$-Medians and $k$-Means\, and efficien
t bicriteria approximation schemes for k-Medians with outliers\, k-Means w
ith outliers and k-Center.
LOCATION:Salle 1007
END:VEVENT
BEGIN:VEVENT
SUMMARY:Variation on preferential-attachment - Zvi Lotker\, Ben Gurion Uni
versity
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20191015T110000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20191015T120000
DTSTAMP;VALUE=DATE-TIME:20191207T100300Z
UID:957
DESCRIPTION:In this talk\, I will describe how preferential attachment ari
ses from the first principle using game theory. Next\, I will extend the m
odel of preferential attachment into a general model\, which allows for th
e incorporation of Homophily ties in the network. This talk is based on jo
int works with Prof. Chen Avin\, Avi Cohen\, Yinon Nahum\, Prof. Pierre Fr
aigniaud\, and Prof. David Peleg.
LOCATION:Salle 1007
END:VEVENT
BEGIN:VEVENT
SUMMARY:Unpaired Kidney Exchange: Overcoming Double Coincidence of Wants w
ithout Money - Olivier Tercieux\, Paris School of Economics
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20200114T110000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20200114T120000
DTSTAMP;VALUE=DATE-TIME:20191207T100300Z
UID:1001
DESCRIPTION:TBA
LOCATION:Salle 1007
END:VEVENT
BEGIN:VEVENT
SUMMARY:Submodular Maximization with Matroid and Packing Constraints in Pa
rallel - Adrian Vladu\, Boston University
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20191127T140000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20191127T150000
DTSTAMP;VALUE=DATE-TIME:20191207T100300Z
UID:1002
DESCRIPTION:We study the adaptive complexity of maximizing the multilinear
extension of a submodular function\, subject to a matroid constraint\, or
multiple packing constraints. The goal is to match the best approximation
guarantees known in the classical sequential setting while performing onl
y few adaptive rounds\, each of which consists of a polynomially bounded n
umber of queries to an evaluation oracle.\n\nOur results are as follows:\n
\n * For a matroid constraint\, in O(log^2 n/ε^3) adaptive rounds\, we ob
tain a 1−1/e−ε approximation for monotone functions\, and a 1/e−ε
approximation for non-monotone functions. This offers an exponential speed
up over the previously existing algorithms.\n\n * For m packing constraint
s\, up to polylogarithmic factors in n\, m and 1/ε\, we require Õ(1/ε^2
) adaptive rounds to obtain a 1/e−ε approximation for non-monotone func
tions\, and 1-1/e-ε approximation for monotone functions. This matches t
he iteration complexity of the fastest currently known parallel algorithm
for solving packing linear programs [Young ’01\, Mahoney et al\, ’16].
\n\nOur results apply more generally to the problem of maximizing a dimini
shing returns submodular (DR-submodular) function.
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:Sliding window property testing for regular languages - Tatiana St
arikovskaya\, ENS
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20200121T110000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20200121T120000
DTSTAMP;VALUE=DATE-TIME:20191207T100300Z
UID:1005
DESCRIPTION:TBA
LOCATION:Salle 1007
END:VEVENT
BEGIN:VEVENT
SUMMARY:Uniformity Testing for High-Dimensional Distributions: Subcube Con
ditioning\, Random Restrictions\, and Mean Testing - Clément Cannone\, IB
M Research
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20191217T110000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20191217T120000
DTSTAMP;VALUE=DATE-TIME:20191207T100300Z
UID:1007
DESCRIPTION:Given a distribution p on {-1\,1}^d\, we want to t
est whether p is uniform. If p is assumed to be a product distributi
on\, this can be done with Theta(sqrt{d}) samples\; without this assumptio
n\, then things get exponentially worse and Theta(sqrt{2^d}) are necessary
and sufficient. Assume however we can condition on arbitrary bits: does t
he problem become easier? If so\, how much?\n\nThis is the "subcube condit
ional sampling model"\, first considered in Bhattacharyya and Chakraborty
(2018). We provide a nearly optimal ~O(sqrt{d})-algorithm for testing unif
ormity in this model. The key component of our proof is a natural notion o
f random restriction for distributions on {-1\,1}^d\, and a quantitative a
nalysis of how such a restriction affects the mean vector of the distribut
ion. Along the way\, we provide a /very/ nearly tight upper bound on the (
standard) sample complexity of a natural problem\, "mean testing."\n\nJoin
t work with Xi Chen\, Gautam Kamath\, Amit Levi\, and Erik Waingarten.
LOCATION:Salle 1007
END:VEVENT
BEGIN:VEVENT
SUMMARY:Algorithms for top-k Lists and Social Networks - Shahrzad Haddadan
\, Max Planck
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20191203T110000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20191203T120000
DTSTAMP;VALUE=DATE-TIME:20191207T100300Z
UID:1019
DESCRIPTION:Today’s massive and dynamic data sets have motivated many co
mputer scientists and mathematicians to study classical problems in combin
atorics and graph theory in various settings. In certain settings the algo
rithms’ access to\nthe data is restricted while in others the resources
are limited. In this talk we\nexplore such settings in three directions: r
anking of objects\, property testing in\nsocial networks and finding commu
nities in dynamic graphs.\n\nIn the first part\, we discuss algorithms on
permutations as well as prefixes of\npermutations also known as top-k list
s. The study of later particularly arises\nin big data scenarios when anal
ysis of the entire permutation is costly or not\ninteresting. We start by
discussing random walks on the set of full rankings or\npermutations of n
objects\, a set whose size is n!. Since 1990s to today\, various\nversions
of this problem have been studied\, each for different motivation.\n\nThe
second part of the talk is devoted to property testing in social networks
:\ngiven a graph\, an algorithm seeks to approximate several parameters of
a graph\njust by accessing the graph by means of oracles and while queryi
ng these oracles as few times as possible. We introduce a new oracle acces
s model which is applicable to social networks\, and assess the complexity
of estimating parameters such as number of users (vertices) in this model
.\n\nIn the third part of the talk\, we introduce a new dynamic graph mode
l which\nis based on triadic closure: a friendship is more likely to be fo
rmed between a\npair of users with a larger number of mutual friends. We f
ind upper bounds\nfor the rate of graph evolution in this model and using
such bounds we devise\nalgorithms discovering communities. I will finish t
his talk by proposing new\ndirections and presenting related open problems
.
LOCATION:Salle 1007
END:VEVENT
END:VCALENDAR