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/
Zoom link: will be posted here shortly before the meeting.
Past events in the community:
-
March 13, 2023 Mini-Symposium MTR 2023 - Secret Sharing (Institute of Information Theory and Automation, Prague).
The speakers: Carles Padro, Laszlo Csirmaz, and Mate Gyarmati.
See the recorded talks on YouTube.
Past meetings of the seminar:
-
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.Bibliography: Zhen Zhang and Raymond W. Yeung. On Characterization of Entropy Function via Information Inequalities. IEEE Transactions on Information Theory, 44(4), 1440-1452.
-
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.Bibliography: Frantisek Matus. Infinitely many information inequalities. IEEE International Symposium on Information Theory 2007, pp. 41-44.
-
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.slides video; 3D image of the tension region from the talk (can be browsed online on https://3dviewer.net)Bibliography: arXiv:2306.14718.
-
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.Based on:
- Batya Kenig and Dan Suciu. Integrity Constraints Revisited: From Exact to Approximate Implication. Logical Methods in Computer Science. 18(1:5)2022.
- Batya Kenig. Approximate implication with d-separation. 37th Conference on Uncertainty in Artificial Intelligence, PMLR 161:301-311, 2021.
- Batya Kenig. Approximate Implication for Probabilistic Graphical Models. arXiv:2310.13942.
-
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.)Bibliography: arXiv:2405.05831
-
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.
Last update: Mar 17, 2025