This is a page of the online seminar on algorithmic aspects of information theory,
a follow up of Dagstuhl Seminar 22301.
If you want to add your address to the mailing list or if you want to suggest a talk please contact
us.
-
12 October 2022
Laszlo Csirmaz (Central European University, Budapest).
Around entropy inequalities.
Abstract:
This will be an introductory talk on linear inequalities for Shannon's entropy:
what the problem is, what the methods are, what is known and what is not known.
-
26 October 2022
Andrei Romashchenko (CNRS LIRMM, Montpellier).
Basic proof techniques for entropic inequalities.
Abstract:
We will consider again several classical theorems mentioned in the survey by
Laszlo Csirmaz
(the first lecture) and discuss the proof techniques behind these results.
-
9 November 2022
Andrei Romashchenko (CNRS LIRMM, Montpellier).
The Zhang-Yeung inequality: an attempt to explain.
Abstract:
We will discuss a magical proof of the first example of a non-Shannon type inequality
(Zhang-Yeung'1998) and try to explain how this and similar arguments could be invented without magic.
-
23 November 2022
Laszlo Csirmaz (Central European University, Budapest). The entropy region is not polyhedra.
Abstract:
We present the two ingredients of the proof: a set of
entropy inequalities and a collection of sample distributions,
and how these yield the famous result of Fero Matus.
If time permits, we sketch the proof of the used inequalities, and
indicate the shortcomings of other applications of the same idea.
-
7 December 2022
Alexander Shen (CNRS LIRMM, Montpellier). Information inequalities: combinatorial interpretation.
Abstract:
Information inequalities like H(A,B) ≤ H(A)+H(B) or H(A)+H(A,B,C) ≤ H(A,B)+H(A,C)
have natural interpretation. It is enough to check them for "uniform"
random variables that can be constructed starting from a group and its
subgroups (Chan,Yeung). On the other hand, they can be translated to
Kolmogorov complexity language. Combining these tools, one can get a
combinatorial characterization of the class of information inequalities.
-
04 January 2023 Frederique Elise Oggier (Nanyang Technological University, Singapore).
An overview of Ingleton's inequality from a group theory point of view.
Abstract:
We will review several works that use group theory to approach Ingleton's inequality and entropic vectors.
-
18 January 2023 LI Cheuk Ting (Chinese University of Hong Kong).
Existential Information Inequalities, Non-Shannon Inequalities, and Automated Theorem Proving.
Abstract:
Existential information inequality is a generalization of linear
information inequalities, where random variables can not only be
universally quantified, but also existentially quantified. We study the
structure of existential information inequalities, and describe
algorithms for automated verification of existential information
inequalities, which are also useful for proving (non-existential)
non-Shannon inequalities. We also describe 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 Gamal and Kim) can be proved
automatically using the proposed algorithms. The algorithms are
implemented in the PSITIP framework (
github.com/cheuktingli/psitip).
-
01 February 2023 Alexander Kozachinskiy (Catholic University of Chile).
On the recent progress on Frankl's conjecture.
Abstract:
Frankl's conjecture states that for any 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 the family. I will present a
recent result of Gilmer that this conjecture holds for some positive constant.
-
15 February 2023 Andrei Romashchenko.
Quasi-uniform distributions and the method of random covers.
Abstract:
We will talk about variations of the classical method of typical
sequence and its applications useful in studying information
inequalities. In particular, we will discuss the Ahlswede-Körner lemma
in the form that can be used to prove non-Shannon type inequalities for
entropy.
-
1 March 2023
Milan Studený (Institute of Information Theory and Automation, Prague).
On conditional Ingleton inequalities.
Abstract:
Linear information inequalities valid for entropy functions induced by
discrete random
variables play an important role in the task to characterize discrete
conditional independence
structures. Specifically, the so-called conditional Ingleton
inequalities in the case of 4 random variables are in the center of
interest: these are valid under conditional independence assumptions on
the inducing random variables. The four inequalities of this form were
earlier revealed: by Yeung and Zhang (
1997), by Matúš (
1999) and by Kaced and Romashchenko (
2013). In our recent paper (
2021)
the fifth inequality of this type was found. These five information
inequalities can be used to characterize all conditional independence
structures induced by four discrete random variables. One of open
problems in that 2021 paper was whether the list of conditional Ingleton
inequalities over 4 random variables is complete: the analysis can be
completed by a recent finding of Boege (
2022) answering that question.
-
15 March 2023 Vlad Demartsev (Max Planck Institute of Animal Behavior).
Economy of vocal repertoires: Zipf's laws in animal communication.
Abstract:
Zipf's Law of Brevity (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 linguistic regularity could be explained by
the Principle of Least Effort — a compromise between the need for
transferring information in a detailed and comprehensive manner and the
pressure for minimising the effort (cost) associated with producing
signals.
If Zipf's principles are indeed fundamental for communication we should
be able to find them in animal systems. Animal communication systems are
likely to be are constrained by the same fundamental trade-off between
minimizing signalling costs while maintaining informational integrity.
However, the pressure towards optimization of signalling is not the only
force shaping animal vocal repertoires. Factors like, sexual selection,
social organization and habitat features can generate evolutionary
forces which might push vocal repertoires further away from Zipfian
optimization.
-
22 March 2023
Oriol Farràs (Universitat Rovira i Virgili).
Introduction to Secret Sharing Schemes: Constructions.
Abstract:
A secret sharing scheme is a method by which a dealer distributes shares
to parties such that only authorized subsets of parties can reconstruct
the secret. The family of these authorized subsets is called the access
structure of the scheme. This introductory talk is focused on the
problem of finding efficient secret sharing schemes for general access
structures. We will see some general constructions as well as their
limitations. We will review connections between the problem of finding
efficient schemes and other problems, such as finding small monotone
formulas and monotone span programs for monotone Boolean functions, and
problems of matroid theory and entropy optimization.
-
29 March 2023 Carles Padro (Universitat Politècnica de Catalunya).
Lower Bounds in Secret Sharing from Information Theory.
Abstract:
Information theory has been used for decades in the search for lower
bounds in secret sharing. The main achievements and limitations of that
technique are discussed in this survey 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 intuition on the limits of the
method and a comparison with the existing lower bounds for linear secret
sharing schemes.
-
12 April 2023
Tianren Liu (Peking University).
From Private Information Retrieval to Secret Sharing.
Abstract:
We will revisit the first general secret sharing scheme with 2^cn
complexity, where c is strictly smaller than 1. Until quite recently,
its best known complexity is about 2^n. Our work established a
connection between secret sharing and private information retrieval.
The talk is based on joint works with Vinod Vaikuntanathan and Hoeteck
Wee.
-
26 April 2023
Hung Q. Ngo (relationalAI).
An Information Theoretic Approach to Estimating Query Size Bounds.
Abstract:
Cardinality estimation is one of the most important problems in database management. One
aspect of cardinality estimation 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 information-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
optimizing a linear function on the almost-entropic or polymatroidal cones. This talk
introduces the problem, the approach, summarizes some known results, and lists open
questions.
-
10 May 2023
Raymond W. Yeung (The Chinese University of Hong Kong).
Entropy Inequalities: My Personal Journey.
Abstract:
Shannon's information measures, namely entropy, mutual information, and
their conditional versions, where each of them can be expressed as a
linear combination of unconditional joint entropies. These measures are
central in information theory, and constraints on these measures, in
particular in the form of inequalities, are of fundamental interest. It
is well-known that all Shannon's information measures are nonnegative,
forming a set of inequalities on entropy. However, whether these are all
the constraints on entropy was unknown, and the problem had been rather
evasive until the introduction of the entropy function region in the
late 1990s.
This 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 Shannon'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
resemble the Venn diagram. In 1991 I introduced the I-Measure to
formally establish the one-to-one correspondence between set theory and
Shannon's information measures. In the mid-1990s, I introduced the
entropy function region Γ* that provides a geometrical interpretation of
entropy inequalities. Shortly after, Zhen Zhang and I discovered
so-called non-Shannon-type inequalities which are beyond the
nonnegativity of Shannon's information measures. Since then this subject
has been under active research
A byproduct of the entropy function region and the associated
geometrical interpretation is the machine-proving of entropy
inequalities. In the second part of this talk, I will discuss the
research along this line, including some recent results.
-
24 May 2023
Mahmoud Abo Khamis (relationalAI).
The Polymatroid Bound: Extensions and Applications in Database Query Evaluation (part 1).
Abstract:
Information 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 within these bounds. The polymatroid bound
generalizes many of these bounds and has a matching query evaluation
algorithm, called PANDA [Abo Khamis et al, PODS’17].
In this talk, we present extensions of the polymatroid bound that
utilize the query structure to derive new constraints on entropies. We
state open problems regarding the relationship between these extensions
and the original bound. On the algorithmic side, we present the PANDA
algorithm in detail and discuss its shortcomings and related open
problems.
-
7 June 2023
Mahmoud Abo Khamis (relationalAI).
The Polymatroid Bound: Extensions and Applications in Database Query Evaluation (part 2).
Abstract:
This is the second part of the talk, the first part of which took place
on May 24.
I continue 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.
Acquaintance with the first part of the talk is very desirable, although formally it is not required.
Bibliography:
Mahmoud Abo Khamis, Hung Q. Ngo, Dan Suciu.
What do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog have to do with one another?
arXiv:1612.02503.
(Also in Proceedings of the 36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2017.)
-
21 June 2023
Alexander V. Smal
(Technion, Israel; PDMI, Russia).
Information theoretic approach to Boolean formula complexity.
Abstract:
We will discuss the information-theoretic approach to proving lower
bounds on the formula complexity of Boolean functions. In the late
80s, Karchmer and Wigderson discovered that Boolean formulas could be
characterized using the language of communication complexity. This
observation allowed us to apply communication complexity methods to
prove lower and upper bounds on the Boolean formula complexity.
In particular, we can use information-theoretic methods from
communication complexity to prove formula complexity lower bounds.
This talk is a brief introduction to these techniques, as well as to some
applications.
-
September 13, 2023
Laszlo Csirmaz (Alfréd Rényi Institute of Mathematics, Budapest and UTIA, Prague).
The power of non-Shannon inequalities: a short proof of the Gács-Körner theorem.
Abstract:
We present a short proof of a celebrated result of Gács and Körner
giving sufficient and necessary condition on the joint distribution of
two discrete random variables X and Y for the case when their
mutual information matches the extractable (in the limit) common
information. Our proof is based on the observation that the mere
existence of certain random variables jointly distributed with
X and Y can impose restrictions on all random variables jointly
distributed with X and Y.
-
September 27, 2023 Andrei Romashchenko (CNRS LIRMM, Montpellier). On the common information and the Ahlswede-Körner lemma in one-shot settings.
Abstract:
The Gács-Körner common information, Wyner's common information, and
other related information quantities apply by design to long series of
independent identically distributed random variables. We will talk about
a possible adaptation of these quantities to the one-shot setting, when
the random objects cannot be represented as series of i.i.d. variables,
and the usual technics of typical sequences do not apply. We will
discuss the connection of information-theoretic profiles with
combinatorial and spectral properties of graphs.
-
October 11, 2023 LI Cheuk Ting (Chinese University of Hong Kong). Functional Representation Lemma and Minimum Entropy Coupling.
Abstract:
The functional representation lemma states that for two
jointly-distributed random variables X, Y, it 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 we minimize H(Y|Z), the
minimum can be bounded by the "strong functional representation lemma",
and has implications in lossy compression and channel simulation. If we
instead minimize H(Z), this is equivalent to the minimum entropy
coupling problem, which concerns finding the coupling of several given
distributions that gives the smallest joint entropy. In this talk, we
will discuss several recent developments regarding these problems
-
October 25, 2023
Alexander Shen (CNRS LIRMM, Montpellier).
Information theoretic proofs (a survey).
Abstract:
Some theorems that have nothing to do with information theory can
be proven using an information-theoretic argument
(entropy, or Kolmogorov complexity, or counting via compression).
For example, why are there infinitely many prime numbers?
If there were only M prime numbers, 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 numbers, but not only them.
-
November 8, 2023 Batya Kenig (Technion). Approximate Implication for Probabilistic Graphical Models.
Abstract:
The graphical structure of Probabilistic Graphical Models (PGMs)
represents the conditional
independence (CI) relations that hold in the modeled distribution.
The premise of all current systems-of-inference 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 approximate
CIs that do not hold exactly in the distribution.
In this work, we ask how the error in this set propagates to the
inferred CIs read
off the graphical structure. More precisely, what guarantee can we
provide on the inferred CI
when the set of CIs that entailed it hold only approximately?
In this talk, I will describe new positive and negative results
concerning this problem.
-
November 22, 2023 Mokshay Madiman (University of Delaware). Analogies between entropy, volume, and cardinality inequalities for projections.
Abstract:
It is well known that entropy inequalities are a quick way of obtaining
volume inequalities for projections of sets in a Euclidean space (or
cardinality inequalities for projections of subsets of the integer
lattice): for example, the Loomis-Whitney inequality follows easily from
the classical Han’s inequality. There is also a well known connection
with integral inequalities. We will review more such analogies, as well
as their limitations. For example, we will observe that volume of
projections to coordinate subspaces is not submodular (though entropy
is), and discuss general dualities between entropy and integral
inequalities. These will give at least one set of reasonable answers to
questions raised by Alexander Shen in the AAIT Seminar on 7 December
2022
(
video).
We will also discuss some particularly useful classes of Shannon-type
inequalities that may be new to the AAIT audience: these also have
applications to volume or cardinality. Most of this talk will be
tutorial: it will be based on the work of many people in the geometry,
combinatorics, probability, and information theory communities, rather
than just the work of the speaker.
-
December 6, 2023 Marius Zimand (Towson University).
Lossless expanders and Information Reconciliation with no shared randomness.
Abstract:
Lossless expanders are bipartite graphs in which for every sufficiently
small set on the left side of 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 string x and Receiver has a string y. For instance, think that x is an updated version of y. Sender sends a message m which allows Receiver to construct x. The goal is to minimize the length of m, taking into account the correlation of x and y.
This correlation can be formalized in different ways and is only known
by Receiver. Standard solutions require Sender and Receiver to share
randomness. In my talk, I will explain how lossless expanders are used
to obtain Information Reconciliation with no shared randomness.
The main idea is from the paper B. Bauwens and M. Zimand,
Universal almost optimal compression and Slepian-Wolf coding in probabilistic polynomial time, Journal of the ACM, April 2023
(also available at
arXiv:1911.04268), but I'll focus on just one particular aspect.
-
Jan 24 and 31, 2024
Amin Gohari (the Chinese University of Hong Kong).
Secret Key Generation from Dependent Sources.
Abstract:
We consider the problem of extracting a secret key from dependent
sources. In this problem, the legitimate terminals observe iid
repetition of correlated random variables and wish to create a shared
secret key that is secure from a passive eavesdropper using a noiseless
public communication channel. Finding the maximum achievable key rate is
a fundamental open problem in information-theoretic security. We review
the history and the state-of-the-art results for this problem, with an
emphasis on the speaker's prior work on this problem. Certain extensions
of the problem will also be discussed.
-
Feb 28 and Mar 13, 2024 Chao Tian (Texas A&M University).
Computer-Aided Investigation of Information-Theoretic Limits: An Overview.
Abstract:
The linear programming (LP) formulation 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 complexity. To reduce the computation
burden of this approach, we can utilize the symmetry structure in such
systems. The strength of the symmetry-reduced approach is illustrated in
several well-known difficult problems, such as regenerating codes,
coded caching, and private information retrieval, which provides new and
non-trivial outer bounds. In addition to rate bounds, more in-depth
studies can be conducted on the joint entropy structure of these
computed bounds, which often lead to reverse-engineered novel code
constructions and further allow disproving linear code achievability.
Finally, we discuss two new directions: the first is to allow the
utilization of non-Shannon-type inequalities in the computational
approach, and 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 techniques.
-
April 10, 2024 :
Alexander Kozachinskiy (Catholic University of Chile),
Information-theoretic methods in communication complexity.
Abstract:
Imagine that Alice and Bob 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 Disjointness. A fundamental result in
communication complexity states that even if Alice and Bob have access
to randomness and are allowed to error with small probability, they need
to send each other Omega(n) bits to solve Disjointness.
In the talk, I will present an information complexity proof
technique that was
developed by different authors in the 2000s and by now has become
classical.
This method, in the nutshell, uses the chain rule for mutual information
to formalize an intuition that we cannot do better in solving
Disjointness than checking individually all n positions.
-
April 24, 2024 at 16h of Central European Summer Time :
Esther Galbrun (University of Eastern Finland, Kuopio).
The minimum description length principle for pattern mining (MDL4PM).
Abstract:
Considering that patterns express the repeated presence in the data of
particular items, attribute values or other discrete properties, mining
patterns is a core task in data analysis.
Beyond issues of efficient enumeration, the selection of patterns
constitutes a major challenge.
The MDL principle, a model selection method grounded in information
theory, has been applied to pattern mining with the aim to obtain
compact high-quality sets of patterns.
After introducing some necessary concepts to formalise the pattern
mining task, we will review
MDL-based methods for mining various types of data and patterns and try
to highlight their common characteristics and differences.
Finally, we will discuss some of the issues regarding these methods, and
highlight currently active related data analysis problems.
-
May 15, 2024:
Lasse Harboe Wolff (University of Copenhagen).
Entropy inequalities in Quantum Information Theory.
Abstract:
Quantum information theory allows a wealth of new information processing possibilities, with the von Neumann (quantum) entropy playing a role analogous to the Shannon (classical) entropy in classical information theory. But although the von Neumann entropy has been the subject of intense study, there is essentially only one known (unconstrained) inequality governing the entropies of multi-party systems - strong subadditivity. Proved by Lieb and Ruskai [1] in 1973, all other known (unconstrained) von Neumann entropy inequalities can be derived from strong subadditivity, and the inequality is also used to derive virtually every nontrivial quantum coding theorem, along with interesting consequences for black holes, spin systems and more.
In this talk I will introduce the field of study concerned with von Neumann entropy inequalities and the search for inequalities beyond strong subadditivity, along with some (more or less) recent developments in the field [2-4]. The talk will be aimed towards people with limited to no experience within quantum information theory, so emphasis will be put on introducing and motivating the most relevant concepts. Whenever possible, I will also aim to highlight the similarities or differences arising between the quantum and the classical case.
Bibliography:
- Elliott H. Lieb, Mary Beth Ruskai, "Proof of the strong subadditivity of quantum‐mechanical entropy," J. Math. Phys. 1 December 1973; 14 (12): 1938-1941
- Linden, N., Winter, A. "A New Inequality for the von Neumann Entropy," Commun. Math. Phys. 259, 129-138 (2005)
- M. Christandl, B. Durhuus, L.H. Wolff, "Tip of the Quantum Entropy Cone", Phys. Rev. Lett. 131, 240201, December 2023
- N. Pippenger, "The inequalities of quantum information theory," in IEEE Transactions on Information Theory, vol. 49, no. 4, pp. 773-789, April 2003
-
May 29, 2024 at 17h CEST:
Tiago Pimentel (ETH Zurich).
Revisiting the Optimality of Word Lengths.
Abstract:
Zipf posited that wordforms are optimized to minimize utterances' communicative costs. He supported this claim by showing that words' lengths are inversely correlated with their frequencies. This correlation, however, is only expected if one assumes that a words' communicative cost is given by its length. In this talk, we will explore this assumption, comparing the predictive power over word lengths we get when assuming different operationalisations of communicative cost.
-
June 05 and 06, 2024 at 17h CEST: Dan Suciu (University of Washington).
Tight Upper Bounds on the Number of Homomorphic Images of a Hypergraph in Another.
Abstract:
Given two hypergraphs H, G, we are interested in the number of homomorphisms H → G. The hyperedges are typed, and homomorphisms need to preserve the type. The graph G is unknown, instead we only know statistics about G, such 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 → G, when G satisfies the given statistics. We say that this bound is tight within a constant c ≤ 1 if there exists a graph G satisfying the given statistics for which the number of homomorphisms is at least c times the bound.
We start with the AGM bound (by Atserias, Grohe, Marx), which strengthens a prior result by Friedgut and Kahn. This bound uses only the cardinalities of each type of hyperedge of the hypergraph G. We will prove the AGM bound by using a numerical inequality due to Friedgut, which generalizes Cauchy-Schwartz and Holder's inequalities. The AGM bound can be computed in polynomial time in the size of H, and is tight within a constant 1/2k, where k is the number of vertices in H.
Next, we prove a general bound, which uses both the cardinalities of each type of hyperedge, and the norms of their degree sequences. In particular, the
ℓp
norms of their degree sequences. In particular, the
ℓ∞
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.
Finally, we restrict 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 entropic vector in the entropic bound can be restricted to be one with non-negative I-measure. Furthermore, the entropic bound is computable in polynomial time in the size of H, and it is tight within a constant 1/22k-1.
Bibliography:
-
Atserias, A., Grohe, M., and Marx, D. (2013).
Size bounds and query plans for relational joins.
SIAM J. Comput., 42(4):1737–1767.
PDF
-
Friedgut, E. (2004).
Hypergraphs, entropy, and inequalities.
Am. Math. Mon., 111(9):749-760.
PDF
-
Friedgut, E. and Kahn, J. (1998).
On the number of copies of one hypergraph in another.
Israel Journal of Mathematics, 105(1):251-256.
PDF
-
Gottlob, G., Lee, S. T., Valiant, G., and Valiant, P. (2012).
Size and treewidth bounds for conjunctive queries.
J. ACM, 59(3):16:1-16:35.
PDF
-
Grohe, M. and Marx, D. (2006).
Constraint solving via fractional edge covers.
In Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2006, Miami, Florida,
USA, January 22-26, 2006, pages 289-298. ACM Press.
PDF
-
Im, S., Moseley, B., Ngo, H. Q., Pruhs, K., and Samadian, A. (2022).
Optimizing polymatroid functions.
CoRR, abs/2211.08381.
PDF
-
Khamis, M. A., Nakos, V., Olteanu, D., and Suciu, D. (2023).
Join size bounds using lp-norms on degree sequences.
CoRR, abs/2306.14075.
PDF
-
Khamis, M. A., Ngo, H. Q., and Suciu, D. (2016).
Computing join queries with functional dependencies.
In Milo, T. and Tan, W., editors, Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of
Database Systems, PODS 2016, San Francisco, CA, USA, June 26 - July 01, 2016, pages 327–342. ACM.
PDF
-
Khamis, M. A., Ngo, H. Q., and Suciu, D. (2017).
What do shannon-type inequalities, submodular width, and disjunctive datalog have to do with one another?
In Sallinger, E., den Bussche, J. V., and Geerts, F., editors, Proceedings of the 36th ACM SIGMOD-SIGACT-SIGAI
Symposium on Principles of Database Systems, PODS 2017, Chicago, IL, USA, May 14-19, 2017, pages 429-444. ACM.
PDF
Extended version available at arXiv:1621.02503
-
Suciu, D. (2023).
Applications of information inequalities to database theory problems.
In 38th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2023, Boston, MA, USA, June 26-29, 2023,
pages 1–30. IEEE.
PDF
-
Yeung, R. W. (2008).
Information Theory and Network Coding.
Springer Publishing Company, Incorporated, 1 edition.
PDF
A few additional links mentioned in the discussion after the talk:
-
Lech Maligranda, Why Hölder's inequality should be called Rogers' inequality. (1998)
Mathematical Inequalities and Applications, 1(1) 69-83.
PDF
-
Mahmoud Abo Khamis, Hung Q. Ngo, Dan Suciu, PANDA: Query Evaluation in Submodular Width.
arXiv:2402.02001
-
Noga Alon, Ilan Newman, Alexander Shen, Gabor Tardos, Nikolai Vereshchagin.
Partitioning multi-dimensional sets in a small number of uniform parts. (2007)
European Journal of Combinatorics, 28(1), 134-144.
pdf
-
Andrei Romashchenko, Alexander Shen, Nikolay Vereshchagin,
Combinatorial Interpretation of Kolmogorov Complexity. (2000)
Theoretical Computer Science 271, no. 1-2 (2002): 111-123.
ECCC:TR00-026
-
June 19 and 26, 2024
Milan Studený (Institute of Information Theory and Automation, Prague).
Self-adhesivity in lattices of abstract conditional independence models,
based on joint work with T. Boege and J.H. Bolt
Abstract:
In the first part of the talk, the concept of a self-adhesive polymatroid,
introduced in 2007 by Matus, will be recalled. This concept can be viewed as
the formalization of a method to derive non-Shannon information-theoretical inequalities,
known in context of the so-called copy lemma. Then an abstraction of this
method leads to the notion of a self-adhesive conditional independence (CI) model.
These CI models will be defined relative to an abstract algebraic frame of CI models
closed under three basic operations, called copying, marginalization, and intersection.
Three 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-polymatroidal were computationally excluded from being almost entropic.
The second part of the talk will start with recalling certain basic facts from lattice theory and the formal concept analysis. Two basic ways to describe finite lattices
in a condensed form will be presented. Particular attention will be devoted to the concept
of a pseudo-closed set an implicational generator for a Moore family of sets.
This leads to combinatorial algorithms to compute the so-called canonical implicational basis. The results of computational results on relevant families of CI models will be then presented, which results can be interpreted as the canonical "axiomatizations" for these CI families. The rest of the talk will be devoted other sensible operations with CI models, other conceivable abstract algebraic CI frames, and to open questions raised in this context.
Bibliography:
-
Tobias Boege, Janneke H. Bolt, and Milan Studený. "Self-adhesivity in lattices of abstract conditional independence models." (2024)
arXiv:2402.14053
-
Tobias Boege. An open database for conditional independence structures CInet.
-
October 23, 2024 Andrei Romashchenko
(LIRMM - Univ Montpellier and CNRS),
Information inequalities on graphs with a strong mixing property and their applications.
Abstract:
We will discuss the argument of Andrei Muchnik (that goes back to the 1990s) that allows to prove information inequalities specific for neighboring vertices sampled on a graph with a strong mixing property. We will use this technique to show that the classical two-phases protocol of secret key agreement proposed by Ahlswede-Csiszár and Maurer (information reconciliation + privacy amplification) is in some settings the only possible solution. In particular, in the one-shot settings, this protocol is unavoidably asymmetric: (almost) the entire burden of communication falls on one of the protocol participants. (By a joint work with Geoffroy Caillat-Grenier and Rustam Zyavgarov.)
-
November 20, 2024 at 16h CET: Satyajit THAKOR
(Indian Institute of Technology Mandi).
The Constrained Entropy Vectors Characterization Problem.
Abstract:
Properties of the Shannon entropy are instrumental for analyzing the limits of reliable communication for various communication system models. Often, situations arise where we have additional constraints on random variables and the corresponding entropy vectors due to the underlying model. In this talk, we focus on the problem of characterizing constrained entropy vectors. Constraints can be entropy equalities or belonging to a particular class of entropy vectors, e.g., quasi-uniform entropy vectors. We visit both direct and converse approaches to tackle the characterization problem. The direct approach is to construct entropy vectors given the constraints, and the converse approach is to find necessary conditions, usually equalities and inequalities, for entropy vectors given the constraints.
-
December 11, 2024:
Chandra NAIR
(the Chinese University of Hong Kong).
Additive Combinatorics, Abelian Groups, and Entropic Inequalities.
Abstract:
Ruzsa’s equivalence theorem provided a framework for converting certain families of inequalities in additive combinatorics
to entropic inequalities (which sometimes did not possess stand-alone entropic proofs). In this talk, we first establish formal
equivalences between some families (different from Ruzsa) of inequalities in additive combinatorics and entropic ones. Secondly,
we provide stand-alone entropic proofs for previously known entropic inequalities that we established via Ruzsa’s equivalence
theorem. As a first step to further these equivalences, we establish an information-theoretic characterization of the magnification
ratio of independent interest.
This talk is based on the following paper: Information Inequalities 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 Information Theory (ISIT), Taipei, Taiwan, 2023, pp. 2452-2457, doi: 10.1109/ISIT54713.2023.10206561.
Full version:
https://chandra.ie.cuhk.edu.hk/pub/papers/comb/Sumset-Entropy.pdf)
-
January 15, 2025: Bryon ARAGAM (University of Chicago).
Learning compositional structure from data
Abstract:
We introduce the neighbourhood lattice decomposition of a distribution, which is a compact, non-graphical representation of conditional independence that is valid in the absence of a faithful graphical representation. 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 graphoid and can be computed consistently in high-dimensions without the curse of dimensionality. In particular, this gives a way to learn from data all of the independence relations implied by any graphical model and thus in particular its structure.
-
January 29, 2025 at 17h (CET, Paris time): Alexander SHEN
(CNRS LIRMM, Montpellier)
Revisiting combinatorial applications of information inequalities.
Abstract:
This (short) talk is a reaction 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 that 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 statistics), and it would be interesting to find out whether one can get a similar bound for Shannon's entropies.
-
February 12, 2025: Qi CHEN (Xidian University).
Matroidal entropy functions (Part 1)
Abstract:
A 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 of a matroid M. For a matroid M, the characterization of matroidal entropy functions induced by M is to determine its probabilistic-characteristic set Χ_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 characterization also determines the entropic region on the extreme ray of the polymatroidal region containing log v · r_M.
To characterize matroidal entropy functions, variable-strength orthogonal arrays (VOA) is defined, which can be considered as special cases of classic combinatorial structure orthogonal arrays (OA). It can be proved that whether log v · r_M is entropic depends on whether a VOA(M, v) is constructible. The constructibility of VOA(M, v) is also equivalent to the partition-representability of M over an alphabet with cardinality v, defined by Fero Matúš, which generalize the linear representability of a matroid over a field.
In this part, 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.
-
February 19: Qi CHEN (Xidian University).
Matroidal entropy functions (Part 2)
Abstract:
Leveraging the correspondences between matroidal entropy functions and VOAs discussed in part 1 of the talk, we characterize the matroidal entropy functions induced by matroids obtained from matroid operations such as deletion, 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 the same p-characteristic set as uniform matroid U_{2,4}, which are located on the bottom of the lattice of all matroids ordered by operation of "taking minor". Some further research topics of matroidal entropy functions are also discussed at the end of talk.
-
March 5: Tobias BOEGE
(UiT The Arctic University of Norway in Tromsø).
On the Intersection and Composition properties for discrete random variables.
Abstract:
Compositional graphoids are fundamental combinatorial structures in the field of causality where they usually appear disguised as graphical models. 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 conditional information inequalities.
-
March 26, 2025:
Marius Zimand (Towson University).
On the existence of one-way functions and the hardness of approximating Kolmogorov complexity.
Abstract:
One-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 widely believed to exist but an unconditional proof of this fact implies P \not= NP. I will present a recent characterization due to Ilango, Ren, and Santhanam: there exists a one-way function IFF approximating the Kolmogorov complexity is hard on average with respect to some efficiently samplable distribution.
The paper by Ilango, Ren, and Santhana is available in
Proc. STOC 2022.
See also by M. Zimand
https://eccc.weizmann.ac.il/report/2024/201/
-
April 30, 2025
Julien Béguinot (Télécom Paris).
What can information guess ? From Informational Leakages to Formal Side-Channel Security Proof.
Abstract:
In this presentation, we present how formal security guarantees can be provided against side channel attacks using information theoretic analysis.
We focus on two figures of merit for the adversary, the probability to mount a successful attack and the guessing entropy which measures the average remaining time to find the find a secret key in the presence of leakages.
On the one hand, the probability of success can be upper bounded using Fano's inequality.
On the other hand, we derive the optimal inequalitiy between mutual information and guessing entropy (Massey and McEliece & Yu like inequalities) using Gibbs inequality.
-
June 11, 17h CEST Chris F. Westbury
(University of Alberta)
and
Michelle Yang (McGill University),
Orthographic uncertainty: An entropy-based measure of word form typicality.
Abstract:
Measures of orthographic typicality have long been studied as predictors of lexical access. The best-known orthographic typicality measure is orthographic neighbourhood 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 20 (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 family 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/nonword decision times and word reading times and accuracies. They are also superior to the older measures insofar as they are naturally tied to the widely-accepted quantification using Shannon Entropy of the psychological functions of familiarity, uncertainty, learnability, and representational and computational efficiency.