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:20240624T064119Z
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:20240624T064119Z
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:20240624T064119Z
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:20240624T064119Z
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:20240624T064119Z
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:20240624T064119Z
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:20240624T064119Z
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:20240624T064119Z
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:20240624T064119Z
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:20240624T064119Z
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:20240624T064119Z
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:20240624T064119Z
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:20240624T064119Z
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:20240624T064119Z
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:20240624T064119Z
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:20240624T064119Z
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:20240624T064119Z
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:20240624T064119Z
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:20240624T064119Z
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:20240624T064119Z
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:20240624T064119Z
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:20240624T064119Z
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:20240624T064119Z
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:20240624T064119Z
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:20240624T064119Z
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:20240624T064119Z
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
BEGIN:VEVENT
SUMMARY:Amin Gohari (Chinese University of Hong Kong)
DTSTART;VALUE=DATE-TIME:20240124T100000Z
DTEND;VALUE=DATE-TIME:20240124T111500Z
DTSTAMP;VALUE=DATE-TIME:20240624T064119Z
UID:AAIT/27
DESCRIPTION:Title: Se
cret Key Generation from Dependent Source\, part 1\nby Amin Gohari (Ch
inese University of Hong Kong) as part of Seminar on Algorithmic Aspects o
f Information Theory\n\n\nAbstract\nWe consider the problem of extracting
a secret key from dependent sources. In this problem\, the legitimate term
inals observe iid repetition of correlated random variables and wish to cr
eate a shared secret key that is secure from a passive eavesdropper using
a noiseless public communication channel. Finding the maximum achievable k
ey rate is a fundamental open problem in information-theoretic security. W
e review the history and the state-of-the-art results for this problem\, w
ith an emphasis on the speaker's prior work on this problem. Certain exten
sions of the problem will also be discussed.\n
LOCATION:https://researchseminars.org/talk/AAIT/27/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Amin Gohari (Chinese University of Hong Kong)
DTSTART;VALUE=DATE-TIME:20240131T100000Z
DTEND;VALUE=DATE-TIME:20240131T111500Z
DTSTAMP;VALUE=DATE-TIME:20240624T064119Z
UID:AAIT/28
DESCRIPTION:Title: Se
cret Key Generation from Dependent Source\, part 2\nby Amin Gohari (Ch
inese University of Hong Kong) as part of Seminar on Algorithmic Aspects o
f Information Theory\n\n\nAbstract\nWe consider the problem of extracting
a secret key from dependent sources. In this problem\, the legitimate term
inals observe iid repetition of correlated random variables and wish to cr
eate a shared secret key that is secure from a passive eavesdropper using
a noiseless public communication channel. Finding the maximum achievable k
ey rate is a fundamental open problem in information-theoretic security. W
e review the history and the state-of-the-art results for this problem\, w
ith an emphasis on the speaker's prior work on this problem. Certain exten
sions of the problem will also be discussed.\n
LOCATION:https://researchseminars.org/talk/AAIT/28/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Chao Tian (Texas A&M University)
DTSTART;VALUE=DATE-TIME:20240228T160000Z
DTEND;VALUE=DATE-TIME:20240228T171500Z
DTSTAMP;VALUE=DATE-TIME:20240624T064119Z
UID:AAIT/29
DESCRIPTION:Title: Co
mputer-Aided Investigation of Information-Theoretic Limits: An Overview.\nby Chao Tian (Texas A&M University) as part of Seminar on Algorithmic
Aspects of Information Theory\n\n\nAbstract\nThe linear programming (LP) f
ormulation of information measures provides a solid mathematical framework
to identify the fundamental limits of information systems computationally
. A critical issue of this approach is however its high computational comp
lexity. To reduce the computation burden of this approach\, we can utilize
the symmetry structure in such systems. The strength of the symmetry-redu
ced approach is illustrated in several well-known difficult problems\, suc
h as regenerating codes\, coded caching\, and private information retrieva
l\, which provides new and non-trivial outer bounds. In addition to rate b
ounds\, more in-depth studies can be conducted on the joint entropy struct
ure of these computed bounds\, which often lead to reverse-engineered nove
l code constructions and further allow disproving linear code achievabilit
y. Finally\, we discuss two new directions: the first is to allow the util
ization of non-Shannon-type inequalities in the computational approach\, a
nd the second is to convert the original LP into a sequence of smaller LPs
\, both of which appear to be awaiting certain suitable machine-learning t
echniques.\n
LOCATION:https://researchseminars.org/talk/AAIT/29/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Chao Tian (exas A&M University)
DTSTART;VALUE=DATE-TIME:20240313T160000Z
DTEND;VALUE=DATE-TIME:20240313T171500Z
DTSTAMP;VALUE=DATE-TIME:20240624T064119Z
UID:AAIT/30
DESCRIPTION:Title: Co
mputer-Aided Investigation of Information-Theoretic Limits: An Overview. (
2nd part)\nby Chao Tian (exas A&M University) as part of Seminar on Al
gorithmic Aspects of Information Theory\n\n\nAbstract\nThe linear programm
ing (LP) formulation of information measures provides a solid mathematical
framework to identify the fundamental limits of information systems compu
tationally. A critical issue of this approach is however its high computat
ional complexity. To reduce the computation burden of this approach\, we c
an utilize the symmetry structure in such systems. The strength of the sym
metry-reduced approach is illustrated in several well-known difficult prob
lems\, such as regenerating codes\, coded caching\, and private informatio
n retrieval\, which provides new and non-trivial outer bounds. In addition
to rate bounds\, more in-depth studies can be conducted on the joint entr
opy structure of these computed bounds\, which often lead to reverse-engin
eered novel code constructions and further allow disproving linear code ac
hievability. Finally\, we discuss two new directions: the first is to allo
w the utilization of non-Shannon-type inequalities in the computational ap
proach\, and the second is to convert the original LP into a sequence of s
maller LPs\, both of which appear to be awaiting certain suitable machine-
learning techniques.\n
LOCATION:https://researchseminars.org/talk/AAIT/30/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Alexander Kozachinskiy (Catholic University of Chile)
DTSTART;VALUE=DATE-TIME:20240410T150000Z
DTEND;VALUE=DATE-TIME:20240410T161500Z
DTSTAMP;VALUE=DATE-TIME:20240624T064119Z
UID:AAIT/32
DESCRIPTION:Title: In
formation-theoretic methods in communication complexity.\nby Alexander
Kozachinskiy (Catholic University of Chile) as part of Seminar on Algorit
hmic Aspects of Information Theory\n\n\nAbstract\nImagine that Alice and B
ob both hold a binary string of length n\, and they want to know if there
is a position\, where both their strings have 1. This problem is called Di
sjointness. A fundamental result in communication complexity states that e
ven if Alice and Bob have access to randomness and are allowed to error wi
th small probability\, they need to send each other Omega(n) bits to solve
Disjointness. \n\nIn the talk\, I will present an information complexity
proof technique that was developed by different authors in the 2000s and b
y now has become classical. This method\, in the nutshell\, uses the chain
rule for mutual information to formalize an intuition that we cannot do b
etter in solving Disjointness than checking individually all n positions.\
n
LOCATION:https://researchseminars.org/talk/AAIT/32/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Esther Galbrun (University of Eastern Finland\, Kuopio)
DTSTART;VALUE=DATE-TIME:20240424T140000Z
DTEND;VALUE=DATE-TIME:20240424T151500Z
DTSTAMP;VALUE=DATE-TIME:20240624T064119Z
UID:AAIT/33
DESCRIPTION:Title: Th
e minimum description length principle for pattern mining (MDL4PM).\nb
y Esther Galbrun (University of Eastern Finland\, Kuopio) as part of Semin
ar on Algorithmic Aspects of Information Theory\n\n\nAbstract\nConsidering
that patterns express the repeated presence in the data of particular ite
ms\, attribute values or other discrete properties\, mining patterns is a
core task in data analysis. Beyond issues of efficient enumeration\, the s
election of patterns constitutes a major challenge. The MDL principle\, a
model selection method grounded in information theory\, has been applied t
o pattern mining with the aim to obtain compact high-quality sets of patte
rns. After introducing some necessary concepts to formalise the pattern mi
ning task\, we will review MDL-based methods for mining various types of d
ata and patterns and try to highlight their common characteristics and dif
ferences. Finally\, we will discuss some of the issues regarding these met
hods\, and highlight currently active related data analysis problems.\n
LOCATION:https://researchseminars.org/talk/AAIT/33/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Lasse Harboe Wolff (University of Copenhagen)
DTSTART;VALUE=DATE-TIME:20240515T150000Z
DTEND;VALUE=DATE-TIME:20240515T161500Z
DTSTAMP;VALUE=DATE-TIME:20240624T064119Z
UID:AAIT/34
DESCRIPTION:by Lasse Harboe Wolff (University of Copenhagen) as part of Se
minar on Algorithmic Aspects of Information Theory\n\nAbstract: TBA\n
LOCATION:https://researchseminars.org/talk/AAIT/34/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Tiago Pimentel (ETH Zurich)
DTSTART;VALUE=DATE-TIME:20240529T150000Z
DTEND;VALUE=DATE-TIME:20240529T161500Z
DTSTAMP;VALUE=DATE-TIME:20240624T064119Z
UID:AAIT/35
DESCRIPTION:Title: Re
visiting the optimality of word lengths.\nby Tiago Pimentel (ETH Zuric
h) as part of Seminar on Algorithmic Aspects of Information Theory\n\n\nAb
stract\nZipf posited that wordforms are optimized to minimize utterances'
communicative costs. He supported this claim by showing that words' length
s are inversely correlated with their frequencies. This correlation\, howe
ver\, is only expected if one assumes that a words' communicative cost is
given by its length. In this talk\, we will explore this assumption\, comp
aring the predictive power over word lengths we get when assuming differen
t operationalisations of communicative cost.\n
LOCATION:https://researchseminars.org/talk/AAIT/35/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Dan Suciu (University of Washington)
DTSTART;VALUE=DATE-TIME:20240605T150000Z
DTEND;VALUE=DATE-TIME:20240605T161500Z
DTSTAMP;VALUE=DATE-TIME:20240624T064119Z
UID:AAIT/36
DESCRIPTION:Title: Ti
ght upper bounds on the number of homomorphic images of a hypergraph in an
other.\nby Dan Suciu (University of Washington) as part of Seminar on
Algorithmic Aspects of Information Theory\n\n\nAbstract\nGiven two hypergr
aphs $H$\, $G$\, we are interested in the number of homomorphisms $H \\to
G$. The hyperedges are typed\, and homomorphisms need to preserve the type
. The graph $G$ is unknown\, instead we only know statistics about $G$\, s
uch as the total number of edges of each type\, or information about their
degree sequences. The problem is to compute an upper bound on the number
of homomorphisms $H \\to G$\, when $G$ satisfies the given statistics. We
say that this bound is tight within a constant $c \\le 1$ if there exists
a graph $G$ satisfying the given statistics for which the number of homomo
rphisms is at least c times the bound.\n\nWe start with the AGM bound (by
Atserias\, Grohe\, Marx)\, which strengthens a prior result by Friedgut an
d Kahn. This bound uses only the cardinalities of each type of hyperedge o
f the hypergraph $G$. We will prove the AGM bound by using a numerical ine
quality due to Friedgut\, which generalizes Cauchy-Schwartz and Holder's i
nequalities. The AGM bound can be computed in polynomial time in the size
of $H$\, and is tight within a constant $1/2^k$\, where $k$ is the number
of vertices in $H$. \n\n\nNext\, we prove a general bound\, which uses bot
h the cardinalities of each type of hyperedge\, and the norms of their deg
ree sequences. In particular\, the $\\ell_p$ norms of their degree sequenc
es. In particular\, the $\\ell_\\infty$ norm is the largest degree of that
type of hyperedges in $G$. The proof uses information inequalities\, and
for that reason we call the bound the "entropic bound". However\, it is an
open problem whether the entropic bound is computable. \n\nFinally\, we r
estrict the statistics to "simple" statistics\, where all degrees are from
a single node\, as opposed to tuples of nodes: in particular\, if $G$ is
a graph\, then all statistics are simple. In this case we show that the en
tropic vector in the entropic bound can be restricted to be one with non-n
egative $I$-measure. Furthermore\, the entropic bound is computable in pol
ynomial time in the size of $H$\, and it is tight within a constant $1/2^{
2^k-1}$.\n
LOCATION:https://researchseminars.org/talk/AAIT/36/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Milan Studený (Institute of Information Theory and Automation\, P
rague))
DTSTART;VALUE=DATE-TIME:20240619T150000Z
DTEND;VALUE=DATE-TIME:20240619T161500Z
DTSTAMP;VALUE=DATE-TIME:20240624T064119Z
UID:AAIT/37
DESCRIPTION:Title: Se
lf-adhesivity in lattices of abstract conditional independence models.
\nby Milan Studený (Institute of Information Theory and Automation\, Prag
ue)) as part of Seminar on Algorithmic Aspects of Information Theory\n\n\n
Abstract\nIn the first part of the talk\, the concept of a self-adhesive p
olymatroid\, introduced in 2007 by Matus\, will be recalled. This concept
can be viewed as the formalization of a method to derive non-Shannon infor
mation-theoretical inequalities\, known in context of the so-called copy l
emma. Then an abstraction of this method leads to the notion of a self-adh
esive conditional independence (CI) model. These CI models will be defined
relative to an abstract algebraic frame of CI models closed under three b
asic operations\, called copying\, marginalization\, and intersection. Thr
ee examples of such abstract frames will be given. The application of this
theory to the theme of entropic region delimitation will be mentioned in
the end of the first part. Specifically\, most of extreme rays of the 5-po
lymatroidal were computationally excluded from being almost entropic.\n\nT
he second part of the talk will start with recalling certain basic facts f
rom lattice theory and the formal concept analysis. Two basic ways to desc
ribe finite lattices in a condensed form will be presented. Particular att
ention will be devoted to the concept of a pseudo-closed set an implicatio
nal generator for a Moore family of sets. This leads to combinatorial algo
rithms to compute the so-called canonical implicational basis. The results
of computational results on relevant families of CI models will be then p
resented\, which results can be interpreted as the canonical "axiomatizati
ons" for these CI families. The rest of the talk will be devoted other sen
sible operations with CI models\, other conceivable abstract algebraic CI
frames\, and to open questions raised in this context. \n\nThe talk is bas
ed on a joint work with T. Boege and J.H. Bolt.\n
LOCATION:https://researchseminars.org/talk/AAIT/37/
END:VEVENT
END:VCALENDAR