BEGIN:VCALENDAR VERSION:2.0 PRODID:researchseminars.org CALSCALE:GREGORIAN X-WR-CALNAME:researchseminars.org BEGIN:VEVENT SUMMARY:Alexander Shen (CNRS - LIRMM) DTSTART:20221207T160000Z DTEND:20221207T171500Z DTSTAMP:20260422T225720Z 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:20230104T160000Z DTEND:20230104T171500Z DTSTAMP:20260422T225720Z 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:20230118T160000Z DTEND:20230118T171500Z DTSTAMP:20260422T225720Z 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:20230201T160000Z DTEND:20230201T171500Z DTSTAMP:20260422T225720Z 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:20230215T160000Z DTEND:20230215T171500Z DTSTAMP:20260422T225720Z 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:20230301T160000Z DTEND:20230301T171500Z DTSTAMP:20260422T225720Z 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:20230315T160000Z DTEND:20230315T171500Z DTSTAMP:20260422T225720Z 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:20230322T160000Z DTEND:20230322T171500Z DTSTAMP:20260422T225720Z 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:20230329T150000Z DTEND:20230329T161500Z DTSTAMP:20260422T225720Z 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:20230412T150000Z DTEND:20230412T161500Z DTSTAMP:20260422T225720Z 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:20230426T150000Z DTEND:20230426T161500Z DTSTAMP:20260422T225720Z 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:20230510T140000Z DTEND:20230510T151500Z DTSTAMP:20260422T225720Z 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:20221012T150000Z DTEND:20221012T161500Z DTSTAMP:20260422T225720Z 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:20221026T150000Z DTEND:20221026T161500Z DTSTAMP:20260422T225720Z 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:20221109T160000Z DTEND:20221109T171500Z DTSTAMP:20260422T225720Z 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:20221123T160000Z DTEND:20221123T171500Z DTSTAMP:20260422T225720Z 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:20230524T150000Z DTEND:20230524T161500Z DTSTAMP:20260422T225720Z 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:20230607T150000Z DTEND:20230607T161500Z DTSTAMP:20260422T225720Z 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:20230621T150000Z DTEND:20230621T161500Z DTSTAMP:20260422T225720Z 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:20230913T150000Z DTEND:20230913T161500Z DTSTAMP:20260422T225720Z 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:20230927T150000Z DTEND:20230927T161500Z DTSTAMP:20260422T225720Z 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:20231011T150000Z DTEND:20231011T161500Z DTSTAMP:20260422T225720Z 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:20231025T150000Z DTEND:20231025T161500Z DTSTAMP:20260422T225720Z 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:20231108T160000Z DTEND:20231108T171500Z DTSTAMP:20260422T225720Z 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:20231122T160000Z DTEND:20231122T171500Z DTSTAMP:20260422T225720Z 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:20231206T160000Z DTEND:20231206T171500Z DTSTAMP:20260422T225720Z 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:20240124T100000Z DTEND:20240124T111500Z DTSTAMP:20260422T225720Z 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:20240131T100000Z DTEND:20240131T111500Z DTSTAMP:20260422T225720Z 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:20240228T160000Z DTEND:20240228T171500Z DTSTAMP:20260422T225720Z 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:20240313T160000Z DTEND:20240313T171500Z DTSTAMP:20260422T225720Z 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:20240410T150000Z DTEND:20240410T161500Z DTSTAMP:20260422T225720Z 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:20240424T140000Z DTEND:20240424T151500Z DTSTAMP:20260422T225720Z 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:20240515T150000Z DTEND:20240515T161500Z DTSTAMP:20260422T225720Z 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:20240529T150000Z DTEND:20240529T161500Z DTSTAMP:20260422T225720Z 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:20240605T150000Z DTEND:20240605T161500Z DTSTAMP:20260422T225720Z 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:20240619T150000Z DTEND:20240619T161500Z DTSTAMP:20260422T225720Z 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 BEGIN:VEVENT SUMMARY:Andrei Romashchenko (LIRMM Univ Montpellier and CNRS) DTSTART:20241023T150000Z DTEND:20241023T161500Z DTSTAMP:20260422T225720Z UID:AAIT/38 DESCRIPTION:Title: In formation inequalities on graphs with a strong mixing property and their a pplications.\nby Andrei Romashchenko (LIRMM Univ Montpellier and CNRS) as part of Seminar on Algorithmic Aspects of Information Theory\n\n\nAbst ract\nWe will discuss the argument of Andrei Muchnik (that goes back to th e 1990s) that allows to prove information inequalities specific for neighb oring vertices sampled on a graph with a strong mixing property. We will u se this technique to show that the classical two-phases protocol of secret key agreement proposed by Ahlswede-Csiszár and Maurer (information recon ciliation + privacy amplification) is in some settings the only possible s olution. In particular\, in the one-shot settings\, this protocol is unavo idably asymmetric: (almost) the entire burden of communication falls on on e of the protocol participants. (By a joint work with Geoffroy Caillat-Gre nier and Rustam Zyavgarov.)\n LOCATION:https://researchseminars.org/talk/AAIT/38/ END:VEVENT BEGIN:VEVENT SUMMARY:Satyajit Thakor (Indian Institute of Technology Mandi) DTSTART:20241120T150000Z DTEND:20241120T161500Z DTSTAMP:20260422T225720Z UID:AAIT/39 DESCRIPTION:Title: Th e Constrained Entropy Vectors Characterization Problem.\nby Satyajit T hakor (Indian Institute of Technology Mandi) as part of Seminar on Algorit hmic Aspects of Information Theory\n\n\nAbstract\nProperties of the Shanno n entropy are instrumental for analyzing the limits of reliable communicat ion for various communication system models. Often\, situations arise wher e we have additional constraints on random variables and the corresponding entropy vectors due to the underlying model. In this talk\, we focus on t he problem of characterizing constrained entropy vectors. Constraints can be entropy equalities or belonging to a particular class of entropy vector s\, e.g.\, quasi-uniform entropy vectors. We visit both direct and convers e approaches to tackle the characterization problem. The direct approach i s to construct entropy vectors given the constraints\, and the converse ap proach is to find necessary conditions\, usually equalities and inequaliti es\, for entropy vectors given the constraints.\n LOCATION:https://researchseminars.org/talk/AAIT/39/ END:VEVENT BEGIN:VEVENT SUMMARY:Chandra NAIR and Chin Wa (Ken) LAU (the Chinese University of Hong Kong) DTSTART:20241211T160000Z DTEND:20241211T171500Z DTSTAMP:20260422T225720Z UID:AAIT/40 DESCRIPTION:Title: Ad ditive Combinatorics\, Abelian Groups\, and Entropic Inequalities.\nby Chandra NAIR and Chin Wa (Ken) LAU (the Chinese University of Hong Kong) as part of Seminar on Algorithmic Aspects of Information Theory\n\n\nAbstr act\nuzsa’s equivalence theorem provided a framework for converting cert ain families of inequalities in additive combinatorics to entropic inequal ities (which sometimes did not possess stand-alone entropic proofs). In th is talk\, we first establish formal equivalences between some families (di fferent from Ruzsa) of inequalities in additive combinatorics and entropic ones. Secondly\, we provide stand-alone entropic proofs for previously kn own entropic inequalities that we established via Ruzsa’s equivalence th eorem. As a first step to further these equivalences\, we establish an inf ormation-theoretic characterization of the magnification ratio of independ ent interest.\n\nThis talk is based on the following paper: Information In equalities via Ideas from Additive Combinatorics (conference version ISIT 2023: C. W. Ken Lau and C. Nair\, "Information Inequalities via Ideas from Additive Combinatorics\," 2023 IEEE International Symposium on Informatio n Theory (ISIT)\, Taipei\, Taiwan\, 2023\, pp. 2452-2457\, doi: 10.1109/IS IT54713.2023.10206561.\n LOCATION:https://researchseminars.org/talk/AAIT/40/ END:VEVENT BEGIN:VEVENT SUMMARY:Bryon ARAGAM (University of Chicago) DTSTART:20250115T160000Z DTEND:20250115T171500Z DTSTAMP:20260422T225720Z UID:AAIT/41 DESCRIPTION:Title: Le arning compositional structure from data\nby Bryon ARAGAM (University of Chicago) as part of Seminar on Algorithmic Aspects of Information Theor y\n\n\nAbstract\nWe introduce the neighbourhood lattice decomposition of a distribution\, which is a compact\, non-graphical representation of condi tional independence that is valid in the absence of a faithful graphical r epresentation. The idea is to view the set of neighbourhoods of a variable as a subset lattice\, and partition this lattice into convex sublattices\ , each of which directly encodes a collection of conditional independence relations. We show that this decomposition exists in any compositional gra phoid and can be computed consistently in high-dimensions without the curs e of dimensionality. In particular\, this gives a way to learn from data a ll of the independence relations implied by any graphical model and thus i n particular its structure.\n LOCATION:https://researchseminars.org/talk/AAIT/41/ END:VEVENT BEGIN:VEVENT SUMMARY:Alexander SHEN (CNRS LIRMM\, Montpellier) DTSTART:20250129T160000Z DTEND:20250129T171500Z DTSTAMP:20260422T225720Z UID:AAIT/42 DESCRIPTION:Title: Re visiting combinatorial applications of information inequalities.\nby A lexander SHEN (CNRS LIRMM\, Montpellier) as part of Seminar on Algorithmic Aspects of Information Theory\n\n\nAbstract\nThis (short) talk is a react ion to Dan Suciu's talk of the last year. He showed some new combinatorial inequalities that use L_p-size of sections of some sets. One could note t hat they have Kolmogorov complexity versions (even a bit more general that give a bound for the pair (C(x)\,C(y|x)) in terms of the section size sta tistics)\, and it would be interesting to find out whether one can get a s imilar bound for Shannon's entropies.\n LOCATION:https://researchseminars.org/talk/AAIT/42/ END:VEVENT BEGIN:VEVENT SUMMARY:Qi CHEN (Xidian University) DTSTART:20250212T140000Z DTEND:20250212T151500Z DTSTAMP:20260422T225720Z UID:AAIT/43 DESCRIPTION:Title: Ma troidal entropy functions (Part 1)\nby Qi CHEN (Xidian University) as part of Seminar on Algorithmic Aspects of Information Theory\n\n\nAbstract \nA matroidal entropy function is an entropy function in the form log v · r_M \, where v is an integer exceeding one and r_M is the rank function o f a matroid M. For a matroid M\, the characterization of matroidal entropy functions induced by M is to determine its probabilistic-characteristic s et Χ_M\, i.e.\, the set of integers v such that log v · r_M is entropic. When M is a connected matroid with rank not less than 2\, such characteri zation also determines the entropic region on the extreme ray of the polym atroidal region containing log v · r_M.\n\nTo characterize matroidal entr opy functions\, variable-strength orthogonal arrays (VOA) is defined\, whi ch can be considered as special cases of classic combinatorial structure o rthogonal arrays (OA). It can be proved that whether log v · r_M is entro pic depends on whether a VOA(M\, v) is constructible. The constructibility of VOA(M\, v) is also equivalent to the partition-representability of M o ver an alphabet with cardinality v\, defined by Fero Matúš\, which gener alize the linear representability of a matroid over a field.\n\nIn this pa rt\, we characterize all matroidal entropy functions with ground set size not exceeding 5 except for log v · r_{U_{2\,5}} and log v · r_{U_{3\,5}} for some v. We also briefly discuss the application of matroidal entropy functions to network coding and secret sharing.\n LOCATION:https://researchseminars.org/talk/AAIT/43/ END:VEVENT BEGIN:VEVENT SUMMARY:Qi CHEN (Xidian University) DTSTART:20250219T140000Z DTEND:20250219T151500Z DTSTAMP:20260422T225720Z UID:AAIT/44 DESCRIPTION:Title: Ma troidal entropy functions (Part 2)\nby Qi CHEN (Xidian University) as part of Seminar on Algorithmic Aspects of Information Theory\n\n\nAbstract \nLeveraging the correspondences between matroidal entropy functions and V OAs discussed in part 1 of the talk\, we characterize the matroidal entrop y functions induced by matroids obtained from matroid operations such as d eletion\, contraction\, minor\, series and parallel connection and 2-sum. Utilizing these results\, we characterize two classes of matroidal entropy functions\, i.e.\, those induced by regular matroids and matroids with th e same p-characteristic set as uniform matroid U_{2\,4}\, which are locate d on the bottom of the lattice of all matroids ordered by operation of "ta king minor". Some further research topics of matroidal entropy functions a re also discussed at the end of talk.\nZoom link: will be posted here shor tly before the meeting.\n LOCATION:https://researchseminars.org/talk/AAIT/44/ END:VEVENT BEGIN:VEVENT SUMMARY:Tobias BOEGE (UiT The Arctic University of Norway in Tromsø) DTSTART:20250305T160000Z DTEND:20250305T171500Z DTSTAMP:20260422T225720Z UID:AAIT/45 DESCRIPTION:Title: On the Intersection and Composition properties for discrete random variables .\nby Tobias BOEGE (UiT The Arctic University of Norway in Tromsø) as part of Seminar on Algorithmic Aspects of Information Theory\n\n\nAbstrac t\nCompositional graphoids are fundamental combinatorial structures in the field of causality where they usually appear disguised as graphical model s. Their usefulness relies on the Intersection and Composition properties. We survey sufficient conditions for a system of discrete random variables to satisfy either of these properties and tie this investigation to condi tional information inequalities.\n LOCATION:https://researchseminars.org/talk/AAIT/45/ END:VEVENT BEGIN:VEVENT SUMMARY:Marius ZIMAND (Towson University) DTSTART:20250326T160000Z DTEND:20250326T171500Z DTSTAMP:20260422T225720Z UID:AAIT/46 DESCRIPTION:Title: On the existence of one-way functions and the hardness of approximating Kolm ogorov complexity.\nby Marius ZIMAND (Towson University) as part of Se minar on Algorithmic Aspects of Information Theory\n\n\nAbstract\nOne-way functions are functions that are easy to compute and hard to invert. They yield private-key encryption\, zero-knowledge proofs\, digital signatures\ , commitment schemes\, and other applications in cryptography. They are wi dely believed to exist but an unconditional proof of this fact implies P \ \not= NP. I will present a recent characterization due to Ilango\, Ren\, a nd Santhanam: there exists a one-way function IFF approximating the Kolmog orov complexity is hard on average with respect to some efficiently sampla ble distribution.\n\nThe paper by Ilango\, Ren\, and Santhana is available in Proc. STOC 2022\, https://dl.acm.org/doi/10.1145/3519935.3520051\nSee also by M. Zimand https://eccc.weizmann.ac.il/report/2024/201/\n LOCATION:https://researchseminars.org/talk/AAIT/46/ END:VEVENT BEGIN:VEVENT SUMMARY:Chris F. Westbury and Michelle Yang (Chris F. Westbury (University of Alberta) and Michelle Yang (McGill University)) DTSTART:20250611T150000Z DTEND:20250611T161500Z DTSTAMP:20260422T225720Z UID:AAIT/47 DESCRIPTION:Title: Or thographic uncertainty: An entropy-based measure of word form typicality.< /a>\nby Chris F. Westbury and Michelle Yang (Chris F. Westbury (University of Alberta) and Michelle Yang (McGill University)) as part of Seminar on Algorithmic Aspects of Information Theory\n\n\nAbstract\nMeasures of ortho graphic typicality have long been studied as predictors of lexical access. The best-known orthographic typicality measure is orthographic neighbourh ood size (Coltheart’s N or ON)\, the number of words that are one letter different\, by substitution\, from the target word. A more recent related measure of orthographic typicality is orthographic Levenshtein distance 2 0 (OLD20)\, the average Levenshtein orthographic edit distance of a target word from its 20 closest neighbours (Yarkoni\, Balota\, and Yap\, 2008). Both measures have been implicated in lexical access. We will discuss a fa mily of measures of word form similarity we call orthographic uncertainty. These measures are based on Shannon entropy (Shannon\, 1948)\, which has a long history of being considered psychologically relevant. Orthographic uncertainty measures are superior to ON and OLD20 at predicting word/nonwo rd decision times and word reading times and accuracies. They are also sup erior to the older measures insofar as they are naturally tied to the wide ly-accepted quantification using Shannon Entropy of the psychological func tions of familiarity\, uncertainty\, learnability\, and representational a nd computational efficiency.\n LOCATION:https://researchseminars.org/talk/AAIT/47/ END:VEVENT BEGIN:VEVENT SUMMARY:Laszlo Csirmaz (Budapest) DTSTART:20260211T160000Z DTEND:20260211T171500Z DTSTAMP:20260422T225720Z UID:AAIT/48 DESCRIPTION:Title: In formation Inequalities for Five Random Variables.\nby Laszlo Csirmaz ( Budapest) as part of Seminar on Algorithmic Aspects of Information Theory\ n\n\nAbstract\nSplit the base set N into the disjoint union YXZ\, and let Y1\,...\,Yn be copies of Y\, and Z1\,...\,Zm be copies of Z. For any proba bility distribution on YXZ there is another probability distribution on (Y 1 ... Yn X Z1 ... Zm) such that the marginals on XYi and XY are the same\; the marginals on XZj and XZ are the same\; moreover the variable sets {Yi \,Zj} are completely conditionally independent over X.\n\nApplying this pr operty for Y={cd}\, X={ab}\, and Z={z}\, all consequences are computed for n<10. Based on the results\, two infinite families of five-variable non-S hannon inequalities are defined and proved to be consequences of the above property. We investigate the “extremal” inequalities among them\, the ir asymptotic behavior\, and how they delimit the five-variable entropy re gion. At the end we discuss how they relate to Matus’ inequalities.\n LOCATION:https://researchseminars.org/talk/AAIT/48/ END:VEVENT BEGIN:VEVENT SUMMARY:Cheuk Ting LI (The Chinese University of Hong Kong) DTSTART:20260225T160000Z DTEND:20260225T171500Z DTSTAMP:20260422T225720Z UID:AAIT/49 DESCRIPTION:Title: Di screte Layered Entropy\, Conditional Compression and a Tighter Strong Func tional Representation Lemma.\nby Cheuk Ting LI (The Chinese University of Hong Kong) as part of Seminar on Algorithmic Aspects of Information Th eory\n\n\nAbstract\nGiven two pieces of information\, we can take the "uni on" of them (the joint random variable)\, but the natural definition of th e difference between them (the information in X but not in Y) is less clea r. The conditional entropy H(X|Y) is often interpreted as the amount of in formation in X but not in Y\, but H(X|Y) cannot be regarded as the entropy of the "conditional random variable X|Y"\, i.e.\, conditional entropy is not a special case of entropy. In this talk\, we discuss a notion of diffe rence motivated by a conditional compression problem\, and a quantity Lamb da(X)\, called discrete layered entropy. Lambda(X) has properties similar to the Shannon entropy H(X)\, and is close to H(X) within a logarithmic ga p. Moreover\, Lambda(X|Y) is indeed the discrete layered entropy of the "c onditional random variable X|Y"\, so conditional discrete layered entropy is a special case of discrete layered entropy (unlike Shannon entropy). Th ese properties make Lambda(X) useful for analyzing conditional compression problems such as channel simulation with common randomness. In particular \, it can give a tighter bound for the strong functional representation le mma.\n LOCATION:https://researchseminars.org/talk/AAIT/49/ END:VEVENT BEGIN:VEVENT SUMMARY:Carles Padró (Universitat Politècnica de Catalunya) DTSTART:20260311T160000Z DTEND:20260311T171500Z DTSTAMP:20260422T225720Z UID:AAIT/50 DESCRIPTION:Title: In teraction between skew-representability\, tensor products\, extension prop erties\, and rank inequalities.\nby Carles Padró (Universitat Politè cnica de Catalunya) as part of Seminar on Algorithmic Aspects of Informati on Theory\n\n\nAbstract\nSkew-representable matroids form a fundamental cl ass in matroid theory\, bridging combinatorics and linear algebra. They pl ay an important role in areas such as coding theory\, optimization\, and c ombinatorial geometry\, where linear structure is crucial for both theoret ical insights and algorithmic applications. Since deciding skew-representa bility is computationally intractable\, much effort has been focused on id entifying necessary or sufficient conditions for a matroid to be skew-repr esentable.\n\nIn this paper\, we introduce a novel approach to studying sk ew-representability and structural properties of matroids and polymatroid functions via tensor products. We provide a characterization of skew-repre sentable matroids\, as well as of those representable over skew fields of a given prime characteristic\, in terms of tensor products. As an algorith mic consequence\, we show that deciding skew-representability\, or represe ntability over a skew field of fixed prime characteristic\, is co-recursiv ely enumerable: that is\, certificates of non-skew-representability — in general or over a fixed prime characteristic — can be verified. We also prove that every rank-3 matroid admits a tensor product with any uniform matroid and give a construction yielding the unique freest tensor product in this setting. Finally\, as an application of the tensor product framewo rk\, we give a new proof of Ingleton's inequality and\, more importantly\, derive the first known linear rank inequality for folded skew-representab le matroids that does not follow from the common information property.\n LOCATION:https://researchseminars.org/talk/AAIT/50/ END:VEVENT BEGIN:VEVENT SUMMARY:Slava Matveev (Leipzig) DTSTART:20260325T160000Z DTEND:20260325T171500Z DTSTAMP:20260422T225720Z UID:AAIT/51 DESCRIPTION:Title: Sp ectral Conditions for the Ingleton Inequality.\nby Slava Matveev (Leip zig) as part of Seminar on Algorithmic Aspects of Information Theory\n\n\n Abstract\nThe Ingleton inequality is a classical linear information inequa lity that holds for representable matroids but fails to be universally val id for entropic vectors. Understanding the extent to which this inequality can be violated has been a longstanding problem in information theory. In this paper\, we show that for a broad class of jointly distributed random variables (X\,Y) the Ingleton inequality holds up to a small additive err or\, even even though the mutual information between X and Y is far from b eing extractable. Contrary to common intuition\, strongly non-extractable mutual information does not lead to large violations of the Ingleton inequ ality in this setting. More precisely\, we consider pairs (X\,Y) that are uniformly distributed on their joint support and whose associated biregula r bipartite graph is an expander. For all auxiliary random variables A and B jointly distributed with (X\,Y)\, we establish a lower bound on the Ing leton quantity I(X:Y|A)+I(X:Y|B)+I(A:B)-I(X:Y) in terms of the spectral pa rameters of the underlying graph. Our proof combines the expander mixing l emma with a partitioning technique for finite sets (cf. Alon\, Newman\, Sh en\, Tardos\, Vereshchagin\, 2007).\n LOCATION:https://researchseminars.org/talk/AAIT/51/ END:VEVENT BEGIN:VEVENT SUMMARY:Milan Studený (Institute of Information Theory and Automation\, P rague) DTSTART:20260409T150000Z DTEND:20260409T161500Z DTSTAMP:20260422T225720Z UID:AAIT/52 DESCRIPTION:Title: Se mi-graphoids interpreted as collections of posets.\nby Milan Studený (Institute of Information Theory and Automation\, Prague) as part of Semin ar on Algorithmic Aspects of Information Theory\n\n\nAbstract\nSemi-grapho ids are discrete structures introduced in context of probabilistic reasoni ng. Particular structural semi-graphoids correspond to the non-empty faces of the cone of tight polymatroids. A result will be presented that any se mi-graphoid over a finite non-empty variable set N can be viewed as a coll ection of posets (= partial orderings) on N. To this end\, a semi-graphoid is first identified with a particular subgraph of the so-called permutohe dral graph\, whose nodes are enumerations (= total orderings) of N. The co mponents of this semi-graphoidal subgraph appear to be special geodeticall y convex sets in the permutohedral graph and\, for this reason\, each of t hese components uniquely corresponds to a poset on N. We also mention geom etrical interpretation of finite posets in terms of so-called braid cones. \n\nThe presentation is based on the paper Semi-graphoids viewed as collec tions of posets. To appear in Proceedings of the 21th conference IPMU 2026 (B. Vantaggi et al. eds)\, Springer.\n LOCATION:https://researchseminars.org/talk/AAIT/52/ END:VEVENT BEGIN:VEVENT SUMMARY:Raymond W. Yeung (The Chinese University of Hong Kong) DTSTART:20260422T150000Z DTEND:20260422T161500Z DTSTAMP:20260422T225720Z UID:AAIT/53 DESCRIPTION:Title: In equalities Revisited.\nby Raymond W. Yeung (The Chinese University of Hong Kong) as part of Seminar on Algorithmic Aspects of Information Theory \n\n\nAbstract\nIn the past over two decades\, researchers in information theory have obtained very fruitful results in the study of the Shannon ent ropy. This study has led to the discovery of a new class of constraints on the Shannon entropy\, called non-Shannon-type inequalities. Intimate conn ections between the Shannon entropy and different branches of mathematics including finite group theory\, combinatorics\, Kolmogorov complexity\, pr obability\, matrix theory\, etc\, have been established. All these discove ries are based on a geometrical interpretation of constraints on the entro py function. We assert that the same formality can be applied to the study of inequalities in other branches of mathematics. To illustrate the idea\ , we revisit with this formality a few celebrated inequalities: the AM—G M inequality\, the Markov inequality\, and the Cauchy—Schwarz inequality . Applications of this formality has the potential of leading to the disco very of new inequalities in different branches of mathematics.\n LOCATION:https://researchseminars.org/talk/AAIT/53/ END:VEVENT END:VCALENDAR