BEGIN:VCALENDAR
VERSION:2.0
PRODID:researchseminars.org
CALSCALE:GREGORIAN
X-WR-CALNAME:researchseminars.org
BEGIN:VEVENT
SUMMARY:Alexander Shen (CNRS - LIRMM)
DTSTART;VALUE=DATE-TIME:20221207T160000Z
DTEND;VALUE=DATE-TIME:20221207T171500Z
DTSTAMP;VALUE=DATE-TIME:20231130T234849Z
UID:AAIT/1
DESCRIPTION:Title: Inf
ormation inequalities: combinatorial interpretation\nby Alexander Shen
(CNRS - LIRMM) as part of Seminar on Algorithmic Aspects of Information T
heory\n\nAbstract: TBA\n
LOCATION:https://researchseminars.org/talk/AAIT/1/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Frederique Oggier (Nanyang Technological University)
DTSTART;VALUE=DATE-TIME:20230104T160000Z
DTEND;VALUE=DATE-TIME:20230104T171500Z
DTSTAMP;VALUE=DATE-TIME:20231130T234849Z
UID:AAIT/2
DESCRIPTION:Title: An
overview of Ingleton's inequality from a group theory point of view.\n
by Frederique Oggier (Nanyang Technological University) as part of Seminar
on Algorithmic Aspects of Information Theory\n\n\nAbstract\nWe will revie
w several works that use group theory to approach Ingleton's inequality an
d entropic vectors.\n
LOCATION:https://researchseminars.org/talk/AAIT/2/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Cheuk Ting LI (Chinese University of Hong Kong)
DTSTART;VALUE=DATE-TIME:20230118T160000Z
DTEND;VALUE=DATE-TIME:20230118T171500Z
DTSTAMP;VALUE=DATE-TIME:20231130T234849Z
UID:AAIT/3
DESCRIPTION:Title: Exi
stential information inequalities\, non-Shannon inequalities\, and automat
ed theorem proving.\nby Cheuk Ting LI (Chinese University of Hong Kong
) as part of Seminar on Algorithmic Aspects of Information Theory\n\n\nAbs
tract\nExistential information inequality is a generalization of linear in
formation inequalities\, where random variables can not only be universall
y quantified\, but also existentially quantified. We study the structure o
f existential information inequalities\, and describe algorithms for autom
ated verification of existential information inequalities\, which are also
useful for proving (non-existential) non-Shannon inequalities. We also de
scribe how a wide range of results in network information theory (e.g. 32
out of 56 theorems in Chapters 1-14 of Network Information Theory by El Ga
mal and Kim) can be proved automatically using the proposed algorithms. Th
e algorithms are implemented in the PSITIP framework ( github.com/cheuktin
gli/psitip ).\n
LOCATION:https://researchseminars.org/talk/AAIT/3/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Alexander Kozachinskiy (Catholic University of Chile)
DTSTART;VALUE=DATE-TIME:20230201T160000Z
DTEND;VALUE=DATE-TIME:20230201T171500Z
DTSTAMP;VALUE=DATE-TIME:20231130T234849Z
UID:AAIT/4
DESCRIPTION:Title: On
the recent progress on Frankl's conjecture.\nby Alexander Kozachinskiy
(Catholic University of Chile) as part of Seminar on Algorithmic Aspects
of Information Theory\n\n\nAbstract\nFrankl's conjecture states that for a
ny non-empty family of non-empty finite sets which is closed under finite
union there exists an element belonging to at least 1/2 of the sets from t
he family. I will present a recent result of Gilmer that this conjecture h
olds for some positive constant.\n
LOCATION:https://researchseminars.org/talk/AAIT/4/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Andrei Romashchenko (CNRS - LIRMM)
DTSTART;VALUE=DATE-TIME:20230215T160000Z
DTEND;VALUE=DATE-TIME:20230215T171500Z
DTSTAMP;VALUE=DATE-TIME:20231130T234849Z
UID:AAIT/5
DESCRIPTION:Title: Qua
si-uniform distributions and the method of random covers.\nby Andrei R
omashchenko (CNRS - LIRMM) as part of Seminar on Algorithmic Aspects of In
formation Theory\n\n\nAbstract\nWe will talk about variations of the clas
sical method of typical sequence and its applications useful in studying i
nformation inequalities. In particular\, we will discuss the Ahlswede-Kör
ner lemma in the form that can be used to prove non-Shannon type inequalit
ies for entropy.\n
LOCATION:https://researchseminars.org/talk/AAIT/5/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Milan Studeny (Institute of Information Theory and Automation\, Pr
ague)
DTSTART;VALUE=DATE-TIME:20230301T160000Z
DTEND;VALUE=DATE-TIME:20230301T171500Z
DTSTAMP;VALUE=DATE-TIME:20231130T234849Z
UID:AAIT/6
DESCRIPTION:Title: On
conditional Ingleton inequalities\nby Milan Studeny (Institute of Info
rmation Theory and Automation\, Prague) as part of Seminar on Algorithmic
Aspects of Information Theory\n\n\nAbstract\nLinear information inequaliti
es valid for entropy functions induced by discrete random variables play a
n important role in the task to characterize discrete conditional independ
ence structures. Specifically\, the so-called conditional Ingleton inequal
ities in the case of 4 random variables are in the center of interest: the
se are valid under conditional independence assumptions on the inducing ra
ndom variables. The four inequalities of this form were earlier revealed:
by Yeung and Zhang (1997)\, by Matúš (1999) and by Kaced and Romashchenk
o (2013). In our recent paper (2021) the fifth inequality of this type was
found. These five information inequalities can be used to characterize al
l conditional independence structures induced by four discrete random vari
ables. One of open problems in that 2021 paper was whether the list of con
ditional Ingleton inequalities over 4 random variables is complete: the an
alysis can be completed by a recent finding of Boege (2022) answering that
question.\n
LOCATION:https://researchseminars.org/talk/AAIT/6/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Vlad Demartsev (Max Planck Institute of Animal Behavior)
DTSTART;VALUE=DATE-TIME:20230315T160000Z
DTEND;VALUE=DATE-TIME:20230315T171500Z
DTSTAMP;VALUE=DATE-TIME:20231130T234849Z
UID:AAIT/7
DESCRIPTION:Title: Eco
nomy of vocal repertoires: Zipf's laws in animal communication\nby Vla
d Demartsev (Max Planck Institute of Animal Behavior) as part of Seminar o
n Algorithmic Aspects of Information Theory\n\n\nAbstract\nZipf's Law of B
revity (negative correlation of words' length with the frequency of their
use) was found across multiple lexicons and text corpora and often claimed
to be one of unifying features of human language. This intriguing linguis
tic regularity could be explained by the Principle of Least Effort — a c
ompromise between the need for transferring information in a detailed and
comprehensive manner and the pressure for minimising the effort (cost) ass
ociated with producing signals. If Zipf's principles are indeed fundamenta
l for communication we should be able to find them in animal systems. Anim
al communication systems are likely to be are constrained by the same fund
amental trade-off between minimizing signalling costs while maintaining in
formational integrity. However\, the pressure towards optimization of sign
alling is not the only force shaping animal vocal repertoires. Factors lik
e\, sexual selection\, social organization and habitat features can genera
te evolutionary forces which might push vocal repertoires further away fro
m Zipfian optimization.\n
LOCATION:https://researchseminars.org/talk/AAIT/7/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Oriol Farràs (Universitat Rovira i Virgili)
DTSTART;VALUE=DATE-TIME:20230322T160000Z
DTEND;VALUE=DATE-TIME:20230322T171500Z
DTSTAMP;VALUE=DATE-TIME:20231130T234849Z
UID:AAIT/8
DESCRIPTION:Title: Int
roduction to Secret Sharing Schemes: Constructions\nby Oriol Farràs (
Universitat Rovira i Virgili) as part of Seminar on Algorithmic Aspects of
Information Theory\n\n\nAbstract\nA secret sharing scheme is a method by
which a dealer distributes shares to parties such that only authorized sub
sets of parties can reconstruct the secret. The family of these authorized
subsets is called the access structure of the scheme. This introductory t
alk is focused on the problem of finding efficient secret sharing schemes
for general access structures. We will see some general constructions as w
ell as their limitations. We will review connections between the problem o
f finding efficient schemes and other problems\, such as finding small mon
otone formulas and monotone span programs for monotone Boolean functions\,
and problems of matroid theory and entropy optimization.\n
LOCATION:https://researchseminars.org/talk/AAIT/8/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Carles Padro (Universitat Politècnica de Catalunya)
DTSTART;VALUE=DATE-TIME:20230329T150000Z
DTEND;VALUE=DATE-TIME:20230329T161500Z
DTSTAMP;VALUE=DATE-TIME:20231130T234849Z
UID:AAIT/9
DESCRIPTION:Title: Low
er Bounds in Secret Sharing from Information Theory.\nby Carles Padro
(Universitat Politècnica de Catalunya) as part of Seminar on Algorithmic
Aspects of Information Theory\n\n\nAbstract\nnformation theory has been us
ed for decades in the search for lower bounds in secret sharing. The main
achievements and limitations of that technique are discussed in this surve
y talk. Among the former\, Csirmaz's general lower bound\, which is still
the best of the known ones\, and the findings of exact optimal information
ratios for several families of access structures. For the latter\, some i
ntuition on the limits of the method and a comparison with the existing lo
wer bounds for linear secret sharing schemes.\n
LOCATION:https://researchseminars.org/talk/AAIT/9/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Tianren Liu (Peking University)
DTSTART;VALUE=DATE-TIME:20230412T150000Z
DTEND;VALUE=DATE-TIME:20230412T161500Z
DTSTAMP;VALUE=DATE-TIME:20231130T234849Z
UID:AAIT/10
DESCRIPTION:Title: Ba
rriers for Secret Sharing.\nby Tianren Liu (Peking University) as part
of Seminar on Algorithmic Aspects of Information Theory\n\nAbstract: TBA\
n
LOCATION:https://researchseminars.org/talk/AAIT/10/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Hung Q. Ngo (relationalAI)
DTSTART;VALUE=DATE-TIME:20230426T150000Z
DTEND;VALUE=DATE-TIME:20230426T161500Z
DTSTAMP;VALUE=DATE-TIME:20231130T234849Z
UID:AAIT/11
DESCRIPTION:Title: An
Information Theoretic Approach to Estimating Query Size Bounds.\nby H
ung Q. Ngo (relationalAI) as part of Seminar on Algorithmic Aspects of Inf
ormation Theory\n\n\nAbstract\nCardinality estimation is one of the most i
mportant problems in database management. One aspect of cardinality estima
tion is to derive a good upper bound on the output size of a query\, given
a statistical profile of the inputs. In recent years\, a promising inform
ation-theoretic approach was devised to address this problem\, leading to
robust cardinality estimators which are used in practice. The information
theoretic approach led to many interesting open questions surrounding opti
mizing a linear function on the almost-entropic or polymatroidal cones. Th
is talk introduces the problem\, the approach\, summarizes some known resu
lts\, and lists open questions.\n
LOCATION:https://researchseminars.org/talk/AAIT/11/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Raymond W. Yeung (The Chinese University of Hong Kong)
DTSTART;VALUE=DATE-TIME:20230510T140000Z
DTEND;VALUE=DATE-TIME:20230510T151500Z
DTSTAMP;VALUE=DATE-TIME:20231130T234849Z
UID:AAIT/12
DESCRIPTION:Title: En
tropy Inequalities: My Personal Journey.\nby Raymond W. Yeung (The Chi
nese University of Hong Kong) as part of Seminar on Algorithmic Aspects of
Information Theory\n\n\nAbstract\nShannon's information measures\, namely
entropy\, mutual information\, and their conditional versions\, where eac
h of them can be expressed as a linear combination of unconditional joint
entropies. These measures are central in information theory\, and constrai
nts on these measures\, in particular in the form of inequalities\, are of
fundamental interest. It is well-known that all Shannon's information mea
sures are nonnegative\, forming a set of inequalities on entropy. However\
, whether these are all the constraints on entropy was unknown\, and the p
roblem had been rather evasive until the introduction of the entropy funct
ion region in the late 1990s.\n\nThis talk consists of two part. The first
part is about how I became interested in this subject in the late 1980s.
It began with my PhD thesis in which I needed to use inequalities on Shann
on's information measures (viz. information inequalities\, or equivalently
entropy inequalities) to prove converse coding theorems. During that time
I was also intrigued by the underlying set-theoretic structure of Shannon
's information measures\, namely their representation by diagrams that res
emble the Venn diagram. In 1991 I introduced the I-Measure to formally est
ablish the one-to-one correspondence between set theory and Shannon's info
rmation measures. In the mid-1990s\, I introduced the entropy function reg
ion Γ* that provides a geometrical interpretation of entropy inequalities
. Shortly after\, Zhen Zhang and I discovered so-called non-Shannon-type i
nequalities which are beyond the nonnegativity of Shannon's information me
asures. Since then this subject has been under active research\n\nA byprod
uct of the entropy function region and the associated geometrical interpre
tation is the machine-proving of entropy inequalities. In the second part
of this talk\, I will discuss the research along this line\, including som
e recent results.\n
LOCATION:https://researchseminars.org/talk/AAIT/12/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Laszlo Csirmaz (Central European University\, Budapest)
DTSTART;VALUE=DATE-TIME:20221012T150000Z
DTEND;VALUE=DATE-TIME:20221012T161500Z
DTSTAMP;VALUE=DATE-TIME:20231130T234849Z
UID:AAIT/13
DESCRIPTION:Title: Ar
ound entropy inequalities.\nby Laszlo Csirmaz (Central European Univer
sity\, Budapest) as part of Seminar on Algorithmic Aspects of Information
Theory\n\nAbstract: TBA\n
LOCATION:https://researchseminars.org/talk/AAIT/13/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Andrei Romashchenko (CNRS LIRMM\, Montpellier)
DTSTART;VALUE=DATE-TIME:20221026T150000Z
DTEND;VALUE=DATE-TIME:20221026T161500Z
DTSTAMP;VALUE=DATE-TIME:20231130T234849Z
UID:AAIT/14
DESCRIPTION:Title: Ba
sic proof techniques for entropic inequalities.\nby Andrei Romashchenk
o (CNRS LIRMM\, Montpellier) as part of Seminar on Algorithmic Aspects of
Information Theory\n\nAbstract: TBA\n
LOCATION:https://researchseminars.org/talk/AAIT/14/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Andrei Romashchenko (CNRS LIRMM\, Montpellier)
DTSTART;VALUE=DATE-TIME:20221109T160000Z
DTEND;VALUE=DATE-TIME:20221109T171500Z
DTSTAMP;VALUE=DATE-TIME:20231130T234849Z
UID:AAIT/15
DESCRIPTION:Title: Th
e Zhang-Yeung inequality: an attempt to explain.\nby Andrei Romashchen
ko (CNRS LIRMM\, Montpellier) as part of Seminar on Algorithmic Aspects of
Information Theory\n\nAbstract: TBA\n
LOCATION:https://researchseminars.org/talk/AAIT/15/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Laszlo Csirmaz (Central European University\, Budapest)
DTSTART;VALUE=DATE-TIME:20221123T160000Z
DTEND;VALUE=DATE-TIME:20221123T171500Z
DTSTAMP;VALUE=DATE-TIME:20231130T234849Z
UID:AAIT/16
DESCRIPTION:Title: Th
e entropy region is not polyhedra.\nby Laszlo Csirmaz (Central Europea
n University\, Budapest) as part of Seminar on Algorithmic Aspects of Info
rmation Theory\n\nAbstract: TBA\n
LOCATION:https://researchseminars.org/talk/AAIT/16/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Mahmoud Abo Khamis (relationalAI)
DTSTART;VALUE=DATE-TIME:20230524T150000Z
DTEND;VALUE=DATE-TIME:20230524T161500Z
DTSTAMP;VALUE=DATE-TIME:20231130T234849Z
UID:AAIT/17
DESCRIPTION:Title: Th
e Polymatroid Bound: Extensions and Applications in Database Query Evaluat
ion.\nby Mahmoud Abo Khamis (relationalAI) as part of Seminar on Algor
ithmic Aspects of Information Theory\n\n\nAbstract\nInformation theory has
been used to compute upper bounds on the output sizes of database queries
as well as to devise matching algorithms that can answer these queries wi
thin these bounds. The polymatroid bound generalizes many of these bounds
and has a matching query evaluation algorithm\, called PANDA [Abo Khamis e
t al\, PODS'17]. In this talk\, we present extensions of the polymatroid b
ound that utilize the query structure to derive new constraints on entropi
es. We state open problems regarding the relationship between these extens
ions and the original bound. On the algorithmic side\, we present the PAND
A algorithm in detail and discuss its shortcomings and related open proble
ms.\n
LOCATION:https://researchseminars.org/talk/AAIT/17/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Mahmoud Abo Khamis (relationalAI)
DTSTART;VALUE=DATE-TIME:20230607T150000Z
DTEND;VALUE=DATE-TIME:20230607T161500Z
DTSTAMP;VALUE=DATE-TIME:20231130T234849Z
UID:AAIT/18
DESCRIPTION:Title: Th
e Polymatroid Bound: Extensions and Applications in Database Query Evaluat
ion (part 2).\nby Mahmoud Abo Khamis (relationalAI) as part of Seminar
on Algorithmic Aspects of Information Theory\n\n\nAbstract\nThis is the s
econd part of the talk\, the first part of which took place on May 24. I c
ontinue our discussion of information-theoretic upper bounds on the output
sizes of database queries. I will recap the polymatroid bound and present
a corresponding query evaluation algorithm\, called PANDA\, whose runtime
matches the polymatroid bound [Abo Khamis et al\, PODS’17]. I will also
discuss this algorithm's shortcomings and related open problems. Acquaint
ance with the first part of the talk is very desirable\, although formally
it is not required.\n
LOCATION:https://researchseminars.org/talk/AAIT/18/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Alexander V. Smal (Technion\, Israel\; PDMI\, Russia)
DTSTART;VALUE=DATE-TIME:20230621T150000Z
DTEND;VALUE=DATE-TIME:20230621T161500Z
DTSTAMP;VALUE=DATE-TIME:20231130T234849Z
UID:AAIT/19
DESCRIPTION:Title: In
formation theoretic approach to Boolean formula complexity.\nby Alexan
der V. Smal (Technion\, Israel\; PDMI\, Russia) as part of Seminar on Algo
rithmic Aspects of Information Theory\n\n\nAbstract\nWe will discuss the i
nformation-theoretic approach to proving lower bounds on the formula compl
exity of Boolean functions. In the late 80s\, Karchmer and Wigderson disco
vered that Boolean formulas could be characterized using the language of c
ommunication complexity. This observation allowed us to apply communicatio
n complexity methods to prove lower and upper bounds on the Boolean formul
a complexity. In particular\, we can use information-theoretic methods fro
m communication complexity to prove formula complexity lower bounds. This
talk is a brief introduction to these techniques\, as well as to some appl
ications.\n
LOCATION:https://researchseminars.org/talk/AAIT/19/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Laszlo Csirmaz (Alfréd Rényi Institute of Mathematics\, Budapest
and UTIA\, Prague)
DTSTART;VALUE=DATE-TIME:20230913T150000Z
DTEND;VALUE=DATE-TIME:20230913T161500Z
DTSTAMP;VALUE=DATE-TIME:20231130T234849Z
UID:AAIT/20
DESCRIPTION:Title: Th
e power of non-Shannon inequalities: a short proof of the Gács-Körner th
eorem.\nby Laszlo Csirmaz (Alfréd Rényi Institute of Mathematics\, B
udapest and UTIA\, Prague) as part of Seminar on Algorithmic Aspects of In
formation Theory\n\n\nAbstract\nWe present a short proof of a celebrated r
esult of Gács and Körner giving sufficient and necessary condition on th
e joint distribution of two discrete random variables X and Y for the case
when their mutual information matches the extractable (in the limit) comm
on information. Our proof is based on the observation that the mere existe
nce of certain random variables jointly distributed with X and Y can impos
e restrictions on all random variables jointly distributed with X and Y.\n
LOCATION:https://researchseminars.org/talk/AAIT/20/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Andrei Romashchenko (LIRMM - CNRS)
DTSTART;VALUE=DATE-TIME:20230927T150000Z
DTEND;VALUE=DATE-TIME:20230927T161500Z
DTSTAMP;VALUE=DATE-TIME:20231130T234849Z
UID:AAIT/21
DESCRIPTION:Title: On
the common information and the Ahlswede-Körner lemma in one-shot setting
s.\nby Andrei Romashchenko (LIRMM - CNRS) as part of Seminar on Algori
thmic Aspects of Information Theory\n\n\nAbstract\nThe Gács-Körner commo
n information\, Wyner's common information\, and other related information
quantities apply by design to long series of independent identically dist
ributed random variables. We will talk about a possible adaptation of thes
e quantities to the one-shot setting\, when the random objects cannot be r
epresented as series of i.i.d. variables\, and the usual technics of typic
al sequences do not apply. We will discuss the connection of information-t
heoretic profiles with combinatorial and spectral properties of graphs.\n
LOCATION:https://researchseminars.org/talk/AAIT/21/
END:VEVENT
BEGIN:VEVENT
SUMMARY:LI Cheuk Ting (Chinese University of Hong Kong)
DTSTART;VALUE=DATE-TIME:20231011T150000Z
DTEND;VALUE=DATE-TIME:20231011T161500Z
DTSTAMP;VALUE=DATE-TIME:20231130T234849Z
UID:AAIT/22
DESCRIPTION:Title: Fu
nctional Representation Lemma and Minimum Entropy Coupling\nby LI Cheu
k Ting (Chinese University of Hong Kong) as part of Seminar on Algorithmic
Aspects of Information Theory\n\n\nAbstract\nThe functional representatio
n lemma states that for two jointly-distributed random variables X\, Y\, i
t is possible to express Y as a function of X and another random variable
Z that is independent of X. There are two interesting extreme points. If w
e minimize H(Y|Z)\, the minimum can be bounded by the "strong functional r
epresentation lemma"\, and has implications in lossy compression and chann
el simulation. If we instead minimize H(Z)\, this is equivalent to the min
imum entropy coupling problem\, which concerns finding the coupling of sev
eral given distributions that gives the smallest joint entropy. In this ta
lk\, we will discuss several recent developments regarding these problems.
\n
LOCATION:https://researchseminars.org/talk/AAIT/22/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Alexander Shen (CNRS - LIRMM\, Montpellier)
DTSTART;VALUE=DATE-TIME:20231025T150000Z
DTEND;VALUE=DATE-TIME:20231025T161500Z
DTSTAMP;VALUE=DATE-TIME:20231130T234849Z
UID:AAIT/23
DESCRIPTION:Title: In
formation theoretic proofs (a survey).\nby Alexander Shen (CNRS - LIRM
M\, Montpellier) as part of Seminar on Algorithmic Aspects of Information
Theory\n\n\nAbstract\nSome theorems that have nothing to do with informati
on theory can be proven using an information-theoretic argument (entropy\,
or Kolmogorov complexity\, or counting via compression). For example\, wh
y are there infinitely many prime numbers? If there were only M prime numb
ers\, then each integer could be encoded by the list of M exponents in its
prime decomposition\, so we could specify each n-bit number by only M×O(
log n) bits\, a contradiction. We will discuss several examples of proofs
of that type\, including other bounds for the distribution of prime number
s\, but not only them.\n
LOCATION:https://researchseminars.org/talk/AAIT/23/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Batya Kenig (Technion)
DTSTART;VALUE=DATE-TIME:20231108T160000Z
DTEND;VALUE=DATE-TIME:20231108T171500Z
DTSTAMP;VALUE=DATE-TIME:20231130T234849Z
UID:AAIT/24
DESCRIPTION:Title: Ap
proximate Implication for Probabilistic Graphical Models.\nby Batya Ke
nig (Technion) as part of Seminar on Algorithmic Aspects of Information Th
eory\n\n\nAbstract\nThe graphical structure of Probabilistic Graphical Mod
els (PGMs) represents the conditional independence (CI) relations that hol
d in the modeled distribution. The premise of all current systems-of-infer
ence for deriving conditional independence relations in PGMs\, is that the
set of CIs used for the construction of the PGM hold exactly. In practice
\, algorithms for extracting the structure of PGMs from data discover appr
oximate CIs that do not hold exactly in the distribution. In this work\, w
e ask how the error in this set propagates to the inferred CIs read off th
e graphical structure. More precisely\, what guarantee can we provide on t
he inferred CI when the set of CIs that entailed it hold only approximatel
y? In this talk\, I will describe new positive and negative results concer
ning this problem. \n\nBased on:\nhttps://lmcs.episciences.org/8943 \;\nht
tps://proceedings.mlr.press/v161/kenig21a.html \;\nhttps://arxiv.org/abs/2
310.13942\n
LOCATION:https://researchseminars.org/talk/AAIT/24/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Mokshay Madiman (University of Delaware)
DTSTART;VALUE=DATE-TIME:20231122T160000Z
DTEND;VALUE=DATE-TIME:20231122T171500Z
DTSTAMP;VALUE=DATE-TIME:20231130T234849Z
UID:AAIT/25
DESCRIPTION:Title: An
alogies between entropy\, volume\, and cardinality inequalities for projec
tions.\nby Mokshay Madiman (University of Delaware) as part of Seminar
on Algorithmic Aspects of Information Theory\n\n\nAbstract\nIt is well kn
own that entropy inequalities are a quick way of obtaining volume inequali
ties for projections of sets in a Euclidean space (or cardinality inequali
ties for projections of subsets of the integer lattice) - for example\, th
e Loomis-Whitney inequality follows easily from the classical Han’s ineq
uality. There is also a well known connection with integral inequalities.
We will review more such analogies\, as well as their limitations. For exa
mple\, we will observe that volume of projections to coordinate subspaces
is not submodular (though entropy is)\, and discuss general dualities betw
een entropy and integral inequalities. We will also discuss some particula
rly useful classes of Shannon-type inequalities that may be new to the AAI
T audience - these also have applications to volume or cardinality. Most o
f this talk will be tutorial - it will be based on the work of many people
in the geometry\, combinatorics\, probability\, and information theory co
mmunities\, rather than just the work of the speaker.\n
LOCATION:https://researchseminars.org/talk/AAIT/25/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Marius Zimand (Towson University)
DTSTART;VALUE=DATE-TIME:20231206T160000Z
DTEND;VALUE=DATE-TIME:20231206T171500Z
DTSTAMP;VALUE=DATE-TIME:20231130T234849Z
UID:AAIT/26
DESCRIPTION:Title: Lo
ssless expanders and Information Reconciliation with no shared randomness.
\nby Marius Zimand (Towson University) as part of Seminar on Algorithm
ic Aspects of Information Theory\n\n\nAbstract\nLossless expanders are bip
artite graphs in which for every sufficiently small set on the left side o
f the bipartition\, most of the outgoing edges lead to distinct vertices.
I will present an application of such graphs in Information Reconciliation
. This is a protocol with 2 parties: Sender and Receiver. Sender has a str
ing x and Receiver has a string y. For instance\, think that x is an updat
ed version of y. Sender sends a message m which allows Receiver to constru
ct x. The goal is to minimize the length of m\, taking into account the co
rrelation of x and y. This correlation can be formalized in different ways
and is only known by Receiver. Standard solutions require Sender and Rece
iver to share randomness. In my talk\, I will explain how lossless expande
rs are used to obtain Information Reconciliation with no shared randomness
.\n\nThe main idea is from the paper B. Bauwens and M. Zimand\, Universal
almost optimal compression and Slepian-Wolf coding in probabilistic polyno
mial time\, Journal of the ACM\, April 2023 (also available at arXiv:1911.
04268)\, but I'll focus on just one particular aspect.\n
LOCATION:https://researchseminars.org/talk/AAIT/26/
END:VEVENT
END:VCALENDAR