Project 3: the log-rank conjecture

The log-rank conjecture is one of my favorite open problems in complexity and combinatorics. At a high level it is asking “what is the structure of low-rank boolean matrices ?”. I will describe it and some equivalent formulations below, and then pose some more open-ended questions about low rank matrices with “combinatorial” structure.

Definitions and formulation

A boolean matrix is a matrix with 0,1 entries. A matrix is monochromatic if all its entries are the same. Given a matrix A, we denote by |A| the number of its entries. A rectangle (equivalently sub-matrix) B of A is a restriction of A to some subsets of rows and columns.

Log-rank conjecture: Let A be a boolean matrix. Assume the rank of A over the reals is r. Then there is a monochromatic rectangle  B in A of size $|B| \ge |A| / 2^{(\log r)^k}$ for some absolute constant k>0.

If we replace rank over the reals with rank over other fields (such as $\mathbb{F}_2$) then the log-rank conjecture is false. The Hadamard matrix is one such counter-example, as its rank over  $\mathbb{F}_2$ is exponentially smaller than its rank over the reals. Over large enough finite fields, the analogous conjecture is equivalent to the conjecture over the reals. An interesting question is what is the threshold needed on the field size for this to hold; is it polynomial or exponential in the size of A?

History and connections to communication complexity

The log-rank conjecture is attributed to Lovász and Saks [LS88], where it was motivated by questions in communication complexity. Related conjectures were made by van Nuffelen [vN76] and Fajtlowicz [Faj88], motivated by questions in graph theory.

The original formulation of the log-rank conjecture is in terms of the deterministic communication complexity of A. A deterministic protocol for A with c bits is an iterative procedure, where at each iteration either the row or the columns of A are partitioned into two parts. At the end, we partition A to monochromatic rectangles. Clearly, if the deterministic communication complexity of A is c, then there is a monochromatic rectangle in A of size $\ge |A| / 2^c$. The reverse direction, showing that it suffices to find one large monochromatic rectangle in a low-rank boolean matrix in order to recurse and find a partition, was shown by Nisan and Wigderson [NW94]. The following is an equivalent formulation for the log-rank conjecture.

Log-rank conjecture (original formulation): Let A be a boolean matrix. Assume the rank of A over the reals is r. Then the deterministic communication complexity of A is at most $(\log r)^k$ for some absolute constant k>0.

Known bounds

Let A be a boolean matrix of rank r. It can have at most $2^r$ distinct rows (and columns). To see why, assume that its columns space is spanned by the first r columns (permute the columns if this is not the case). Then the first r bits in a row specify the entire row. In particular, this shows that A has a monochromatic rectangle of size $\ge |A| / 2^r$, which is exponentially worse than the conjectured bound.

The best known upper bound is by Lovett [Lov16], and shows that there is a monochromatic rectangle of size $\ge |A| / r^{O(\sqrt{r})}$. The best lower bound is by Göös, Pitassi and Watson [GPW18], who showed that $k \ge 2$ is needed in the log-rank conjecture formulation above.

Special cases

There are two special cases which are natural from the communication complexity perspective, that show connections between the log-rank conjecture and boolean function analysis. They are related to “lifted functions”, and specifically are XOR-functions and AND-functions. Below let $f:\{0,1\}^n \to \{0,1\}$ be an arbitrary boolean function.

XOR functions: The corresponding XOR-function for f is the $2^n \times 2^n$ matrix $A_{x,y} = f(x \oplus y)$, where $\oplus$ is an entry-wise XOR. The log-rank conjecture for XOR-functions has an appealing equivalent form in terms of the boolean function f. First, it turns out that the rank of A is equal to the Fourier sparsity of f, namely the number of nonzero Fourier coefficients of f. Tsang, Wong, Xie, Zhang [TWXZ13] suggested the following conjecture, and shows that it implies the log-rank conjecture for XOR functions. Later, Hatami, Hosseini and Lovett [HHL18] showed that the two conjectures are equivalent. Below we identify $\{0,1\}^n$ with the linear space $\mathbb{F}_2^n$.

Log-rank conjecture for XOR functions (equivalent formulation): Let $f:\{0,1\}^n \to \{0,1\}$ be a boolean function. Assume that the Fourier sparsity of f is r. Then there is a subspace $V \subset \mathbb{F}_2^n$ on which f is constant, where the co-dimension of V is $(\log r)^k$ for some absolute constant k>0.

AND functions: The corresponding AND-function for f is the $2^n \times 2^n$ matrix $A_{x,y} = f(x \wedge y)$, where $\wedge$ is an entry-wise AND. The rank of A is equal to the sparsity of f as a polynomial. Namely, the number of nonzero coefficients when expressing f as a linear combination of monomials $\prod_{i \in S} x_i$ for $S \subseteq [n]$. The following conjecture is the natural analog of the log-rank conjecture for XOR functions. We don’t know if it is equivalent to the log-rank conjecture for AND functions, but it seems believable. Below, a subcube $C \subset \{0,1\}^n$ is obtained by fixing some inputs to constants; it’s co-dimension is the number of fixed inputs.

Log-rank conjecture for AND functions (possibly equivalent formulation): Let $f:\{0,1\}^n \to \{0,1\}$ be a boolean function. Assume that the polynomial sparsity of f is r. Then there is a subcube $C \subset \{0,1\}^n$ on which f is constant, where the co-dimension of C is $(\log r)^k$ for some absolute constant k>0.

Other communication complexity models

Analogs of the log-rank conjecture have been suggested for other models of communication complexity, such as randomized communication or quantum communication. In a recent breakthrough, Chattopadhyay, Mande, and Sherif [CMS19] disproved the relevant log-rank conjecture for randomized communication, and suggested a more refined variant that may be true. Please see their paper for details, as well as [ABT19, SdW19] for an extension to the quantum case.

Structure of low-rank matrices

A more general question is what is the structure of low-rank matrices with some “combinatorial” structure. The log-rank conjecture fixes one such structure – having boolean entries. Here is another conjecture, where we replace “boolean” with “sparse”.

Sparse low-rank conjecture: let A be matrix, where a constant fraction of its entries are zero. Then there is a rectangle B in A, where all the entries are zero, of size $|B| \ge |A| / 2^{O(\sqrt{r})}$.

The bound in the conjecture, if true, is best possible. This conjecture has connections to matrix rigidity and to additive combinatorics. You can read more about it in a survey I wrote a few years ago on progress on the log-rank conjecture [Lov14]. Note that it is missing some recent developments (eg [GPW18], [CMS19]).

In general, I think that studying questions in the intersection of algebra (e.g. low rank) and combinatorics (e.g. boolean, sparse) leads to both interesting questions, which potentially can connect various fields in TCS and math. To some extent, the entire field of additive / arithmetic combinatorics can be seen in this way.

Exact quantum vs deterministic communication protocols

(this information is from Ronald De-Wolf)

A corollary of the log-rank conjecture is that for boolean communication problems, exact quantum protocols (quantum protocols without errors) are equivalent to deterministic protocols, up to polynomial factors.

For quantum protocols without entanglement, this follows from the log-rank conjecture since it is known that an exact quantum protocol with c bits implies that the communication matrix has rank at most $2^c$. For quantum protocols with entanglement this is more involved and was proved by Buhrman and De-Wolf [BdW01].

The question of whether the sampling analog of exact quantum and deterministic protocols is equivalent is in fact equivalent to the log-rank conjecture. This is given as Conjecture 2 in [T99] and is shown in [ASTVW03].

Bibliography

[ABT19] A. Anshu, G. Boddu and D. Touchette. Quantum Log-Approximate-Rank conjecture is also false. 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS).

[ASTVW03] Ambainis, A., Schulman, L. J., Ta-Shma, A., Vazirani, U., & Wigderson, A. (2003). The quantum communication complexity of sampling. SIAM Journal on Computing, 32(6), 1570-1585.

[BdW01] Buhrman, Harry, and Ronald de Wolf. Communication complexity lower bounds by polynomials. Proceedings 16th Annual IEEE Conference on Computational Complexity. IEEE, 2001.

[CMS19] A. Chattopadhyay, N.S. Mande, and S. Sherif. The log-approximate-rank conjecture is false. Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing. 2019.

[Faj88] S. Fajtlowicz. On conjectures of graffiti. Discrete mathematics, 72(1):113–118, 1988.

[GPW18] M. Göös, T. Pitassi, and T. Watson. Deterministic communication vs. partition number. SIAM Journal on Computing 47.6 (2018): 2435-2450.

[HHL18] H. Hatami, K. Hosseini and S. Lovett. Structure of protocols for XOR functions. SIAM Journal on Computing 47.1 (2018): 208-217.

[Lov14] S. Lovett. Recent advances on the log-rank conjecture in communication complexity. Bulletin of EATCS 1.112 (2014).

[Lov16] S. Lovett. Communication is bounded by root of rank. Journal of the ACM (JACM) 63.1 (2016): 1-9.

[LS88] L. Lovász and M. Saks. Lattices, Möbius Functions and Communication Complexity. Annual Symposium on Foundations of Computer Science, pages 81–90, 1988.

[NW94] N. Nisan and A. Wigderson. On Rank vs. Communication Complexity. Proceedings of the 35rd Annual Symposium on Foundations of Computer Science, pages 831–836, 1994.

[SdW19] M. Sinha and R. de Wolf. Exponential separation between quantum communication and logarithm of approximate rank. 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS).

[T99] Amnon Ta-Shma. Classical versus Quantum Communication Complexity. SIGACT News, Complexity Theory Column 23, 1999.

[TWXZ13] H. Y. Tsang, C. H. Wong, N. Xie and S. Zhang. Fourier sparsity, spectral norm, and the log-rank conjecture. 2013 IEEE 54th Annual Symposium on Foundations of Computer Science.

[vN76] C. van Nuffelen. A bound for the chromatic number of a graph. American Mathematical Monthly, pages 265–266, 1976.

Dear all, please don’t freak out by the famous log-rank conjecture. 😉 As request by some participants, Professor Lovett kindly gave an online tutorial and updated the proposal with several more approachable subproblems. You may find this survey paper helpful to get more background on this problem: Lokam, Satya. Complexity lower bounds using linear algebra. Now Publishers Inc, 2009. http://www.cs.toronto.edu/~toni/Courses/CommComplexity/Papers/lokam-book.pdf

Like

Let me link here to this recent paper on this topic: https://arxiv.org/abs/2101.09592

Like

Project 2: Is Semidefinite Programming (SDP) Polynomial-Time Solvable?

Semidefinite Programming (SDP) is a subfield of convex optimization concerned with the optimization of a linear objective function over the intersection of the cone of positive semidefinite matrices with an affine space, i.e., a spectrahedron. SDP is an extension of Linear Programming (LP), with vector variables replaced by matrix variables and nonnegativity elementwise replaced by positive semidefiniteness. One may refer to these two papers [Poru20][Lova03] for more background on SDP.

It is known that LP is solvable in polynomial time. SDP shares some good properties of LP, yet it has more challenging difficulties. In 2014, the well-known TCS blog Gödel’s Lost Letter and P=NP posted one article about this topic: Could We Have Felt Evidence For SDP ≠ P?

In this project, we would like to collect theoretical obstacles that prevent us from getting a polynomial-time algorithm of SDP in different aspects and discuss how to make any new progress.

References

[Poru20] Porumbel, Daniel. Demystifying the characterization of SDP matrices in mathematical programming. No. 2530. EasyChair, 2020. link

[Lova03] Lovász, László. “Semidefinite programs and combinatorial optimization.” In Recent advances in algorithms and combinatorics, pp. 137-194. Springer, New York, NY, 2003. link

(1) The Complexity of Sum-of-square-roots

In 1976, Ron Graham, Michael Garey, and David Johnson could not show some geometric optimization problems such as Euclidean Traveling Salesman Problem is NP-complete or not (they can only show the problem is NP-hard), the reason is that they could not figure out whether the sum-of-square-roots problem is polynomial-time solvable or not. Ron Graham Gives a Talk

In 2019, Ron Graham [Grah19] listed this problem as one of his favorite problems and offered $10 for the following challenge: Challenge 1: ($10) Show that two sums of square roots of integers cannot agree for exponentially many digits (measured by the size of the input).

Actually, Yap and Sharma showed that the best known bounds for the required bit-precision of the input is exponential in $n$ [YaSh17] (chapter 45).  In the recent work,  Erickson, van der Hoog and  Miltzow [EHM19]  proved that under perturbations of the input of magnitude $\delta$, the sum-of-square-roots can be computed on a real RAM with an expected bit-precision of $O(n\log(n/\delta))$ per input variable.

Ron Graham presented it at the Fiftieth Southeastern International Conference on Combinatorics, Graph Theory, and Computing (SEICCGTC), March 4-8, 2019,  in the Student Union at Florida Atlantic University in Boca Raton, FL.  Fan Chung Graham (she was the most frequent invited female speaker of that conference, Paul Erdős was one of the most frequent male participants) was also the invited plenary speaker at that conference.  As always, his talk was mixed with fun, magic games, interesting problems and monetary prizes! There were two other special things of that talk: a sign language translator standing on the stage to help the audience in need (it is such a wonder to translate math into sign language!); Fan Chung Graham standing in front of the laptop table to help to switch slides pages due to technical problems (we all owed her a lot, with her kind help, the audience enjoyed a wonderful talk!) .

slides Ron Graham-A few of my favorite problems

(When we copied the slides, Ron Graham joked he was gonna square root those prizes, but he didn’t.)

In 1998, Michel X. Goemans gave an ICM talk, in which, he addressed this issue: “Semidefinite programs can be solved(or more precisely, approximated) in polynomial-time within any specific accuracy either by the ellipsoid algorithm or more efficiently through interior-point algorithms…The above algorithms produce a strictly feasible solution(or slightly infeasible for some versions of the ellipsoid algorithm) and, in fact, the problem of deciding whether a semidefinite program is feasible(exactly) is still open. A special case of semidefinite programming feasibility is the square-root-sum problem. The complexity of this problem is still open.” [Goem97]

The most remarkable progress towards this problem is by Allender et al. [ABKM03], they showed this problem lies in the 3rd level of the Counting Hierarchy (CH): ${{P^{PP}}^{PP}}^{PP}$.

In CCC 2019 workshop open problem session, I presented the sum-of-square-roots problem, Eric Allender was also in the audience, he commented “we still embarrassingly have little understanding of it. ”

I also asked Mihalis Yannakakis about the connection of square-root sum and PosSLP in Papafest, he kindly explained more details:

“PosSLP is a problem, not a class, which encapsulates the essential power of the unit-cost arithmetic RAM model. Basically, the corresponding class is the class of decision problems solvable in polynomial time in the Blum-Shub-Smale model with rational constants.  The paper by Allender et al is the best reference for PosSLP. That paper introduced and studied thoroughly the problem. There is no further progress with respect to its relation to the classical complexity classes, like NP, Polynomial hierarchy, etc, as far as I know.

The square-root sum problem is reducible to PosSLP, but it is not known to be equivalent. That is if someone proves that the square-root sum problem is in P or NP (in the standard Turing model of complexity), it will not follow from this that PosSLP is also in P or NP, from what we know today.

There are some problems that are equivalent to PosSLP (i.e. reductions going both ways), for example, one is in my paper with Etessami on Recursive Markov chains in JACM 2009, another in the paper with Etessami and Stewart in our paper on Branching processes in SIAM J. Computing 2017.”

Kristoffer Arnsfelt Hansen mentioned Tarasov and Vyalyi (also cited by Allender et al.)  [TaVy08] proved that semidefinite feasibility is PosSLP-hard. However, based on the explanation of Yannakakis, one can see SDP is not equivalent to PosSLP. Thus, even PosSLP is in CH, there is still hope to solve SDP more efficiently.  Bahman Kalantari [Kala20] recently showed that SDP feasibility problem is equivalent to solving a convex hull relaxation (CHR) for a finite system of quadratic equations.

One may refer to the following two books for numerical algorithm and optimization techniques [Solo15] [NoSt06], the books [BCS13] and [BCSS98] for numerical complexity and algebraic complexity.

References

[Grah19] Graham, Ron. “Some of My Favorite Problems (I).” In 50 years of Combinatorics, Graph Theory, and Computing, pp. 21-35. Chapman and Hall/CRC, 2019. link

[YaSh17] Toth, C. D., O’Rourke, J., & Goodman, J. E. (Eds.). (2017). Handbook of discrete and computational geometry. CRC press. Link

[EHM19] Erickson, J., van der Hoog, I., & Miltzow, T. (2019). A Framework for Robust Realistic Geometric Computations. arXiv preprint arXiv:1912.02278. Link

[Goem97] Goemans, Michel X. “Semidefinite programming in combinatorial optimization.” Mathematical Programming 79, no. 1-3 (1997): 143-161. link

[ABPM03] Allender, Eric, Peter Bürgisser, Johan Kjeldgaard-Pedersen, and Peter Bro Miltersen. “On the complexity of numerical analysis.” SIAM Journal on Computing 38, no. 5 (2009): 1987-2006. link

[TaVy08] Tarasov, Sergey P., and Mikhail N. Vyalyi. “Semidefinite programming and arithmetic circuit evaluation.” Discrete applied mathematics 156, no. 11 (2008): 2070-2078. link

[Kala20] Kalantari, Bahman. “On the Equivalence of SDP Feasibility and a Convex Hull Relaxation for System of Quadratic Equations.” arXiv preprint arXiv:1911.03989 (2019). link

[Solo15] Solomon, Justin. Numerical algorithms: methods for computer vision, machine learning, and graphics. CRC press, 2015.

[NoSt06] Nocedal, Jorge, and Stephen Wright. Numerical optimization. Springer Science & Business Media, 2006.

[BCS13] Bürgisser, Peter, Michael Clausen, and Mohammad A. Shokrollahi. Algebraic complexity theory. Vol. 315. Springer Science & Business Media, 2013.

[BCSS98] Blum, Lenore, LENORE AUTOR BLUM, Felipe Cucker, Michael Shub, and Steve Smale. Complexity and real computation. Springer Science & Business Media, 1998.

complexity of square-root sum

TOPP Problem 33

The Curse of Euclidean Metric: Square Roots

(2) Logic and P

In his Ph.D. thesis, Ronald Fagin created the area of Finite Model Theory and stated that the set of all properties expressible in existential second-order logic is precisely the complexity class NP (It is known as Fagin’s Theorem) [Fagi74].

It is a long open problem in descriptive complexity that what logic structure can capture P?  The logic FPC (Fixed-Point Logic with Counting) is a powerful and natural fragment of P, but it is not all of P.  Jin-Yi Cai, Martin Fürer and Neil Immerman found one counterexample [CFI92] . It is also known that FPC could not express the solvability of systems of linear equations over a finite field. However, Martin Grohe showed that for every surface, a property of graphs embeddable in that surface is decidable in polynomial time if and only if it is definable in FPC [Groh12].

Matthew Anderson, Anuj Dawar and  Bjarki Holm showed that the optimization of linear programs is expressible in FPC [ADH15]. Then, how about SDP?  Anuj Dawar and Pengming Wang showed the FPC implementation of the ellipsoid method extends to semidefinite programs (subject to some technical conditions) [DW16].

How does that new progress help us to understand the complexity of SDP? According to Rice’s Theorem,  it is undecidable to determine if a given problem is in P or not, which may limit the above approach.

References

[Fagi74] Fagin, Ronald. “Generalized first-order spectra and polynomial-time recognizable sets.” Complexity of computation 7 (1974): 43-73. Link

[CFI92] Cai, Jin-Yi, Martin Fürer, and Neil Immerman. “An optimal lower bound on the number of variables for graph identification.” Combinatorica 12, no. 4 (1992): 389-410. link

[Groh12] Grohe, Martin. “Fixed-point definability and polynomial time on graphs with excluded minors.” Journal of the ACM (JACM) 59, no. 5 (2012): 1-64. link

[ADH15] Anderson, Matthew, Anuj Dawar, and Bjarki Holm. “Solving linear programs without breaking abstractions.” Journal of the ACM (JACM) 62, no. 6 (2015): 1-26. link

[DW16] Dawar, Anuj, and Pengming Wang. “Lasserre lower bounds and definability of semidefinite programming.” arXiv preprint arXiv:1602.05409 (2016). link

(3) Semialgebraic Proof System

In the recent paper Semialgebraic Proofs and Efficient Algorithm Design published on Foundations and Trends in Theoretical Computer Science, Noah Fleming, Pravesh Kothari and Toniann Pitassi [FKP19] bridge Semialgebraic Proofs and Efficient Algorithm Design. It is amazing that some natural families of algorithms can be viewed as a generic translation from a proof that a solution exists into an algorithm for finding the solution itself! That paper mainly discusses two semialgebraic proof systems– Sherali-Adams and Sum-of-Squares, and shows up to an additive small error, SDP can be solvable in polynomial time (Corollary 3.12).

What proof system is strong enough to capture the nature of SPD? Is there any hope we can get a truly polynomial-time algorithm to solve SDP with it? Paul Beame discussed the limit of proof in the open lecture of the Simons Institute: The Limits of Proof.

References

[FKP19] Fleming, Noah, Pravesh Kothari, and Toniann Pitassi. Semialgebraic Proofs and Efficient Algorithm Design. now the essence of knowledge, 2019. link

(4) Tropical Geometry and Algebraic Geometry

In recent years, there has been some surprising new progress towards some fundamental open problems in linear programming with the help of tropical and algebraic geometry.  For example, Michael Joswig et al. [ABGJ18] disproved the continuous analogue of Hirsch conjecture and showed primal-dual log-barrier interior point methods are not strongly polynomial using an amazing new technique–Tropical Geometry.  Jesús A. De Loera gave a talk of their new contributions of simplicial polytopes and central path curvature with tropical and algebraic geometry tools in JMM 2019 video  slides.  Pablo A. Parrilo also showed the connection of SDP and convex algebraic geometry [BPT12] .

Can those tools help to get a truly polynomial-time algorithm of SDP (or give negative answers)?

References

[ABGJ18]  Allamigeon, Xavier, Pascal Benchimol, Stéphane Gaubert, and Michael Joswig. “Log-barrier interior point methods are not strongly polynomial.” SIAM Journal on Applied Algebra and Geometry 2, no. 1 (2018): 140-178.  link

[BPT12] Blekherman, Grigoriy, Pablo A. Parrilo, and Rekha R. Thomas, eds. Semidefinite optimization and convex algebraic geometry. Society for Industrial and Applied Mathematics, 2012.  link

(5) Number Theory and Lattice

Qi Cheng (University of Oklahoma) suggested applying diophantine approximation from number theory [Habe18] to improve the sum-of-square-roots problem.

What is the minimum nonzero difference between two sums of square roots of integers? Qi Cheng, Xianmeng Meng, Celi Sun, and Jiazhe Chen [CMSC10] gave a tighter upper bound via lattice reduction.

References

[Habe18] Habegger, Philipp. “Diophantine approximations on definable sets.” Selecta Mathematica 24, no. 2 (2018): 1633-1675. link

[CMSC10] Cheng, Qi, Xianmeng Meng, Celi Sun, and Jiazhe Chen. “Bounding the sum of square roots via lattice reduction.” Mathematics of computation 79, no. 270 (2010): 1109-1122. link

(6) Circuit Lower Bound and Other Consequences of SDP=P

Noah Fleming proposed one interesting research direction: instead of trying to put SDP into P, it might also be interesting to prove that putting SDP in P is hard! So like show that if SDP=P, then we get circuit lower bounds or derandomization or something.

Noah Fleming recommended the paper showing that complexity class separations imply circuit lower bounds by Nissan-Wigderson Generator [NoWi94] and the Kabanets-Impagliazzo paper [KaIm04] . Noah also attempted to connect this problem to degree 2 polynomial and SETH.

Thanks to the brilliant idea by Noah Fleming, this problem would connect to the hardcore areas of TCS–Circuit Lower Bound and Pseudorandoness!

References

[NoWi94] Nisan, Noam, and Avi Wigderson. “Hardness vs randomness.” Journal of computer and System Sciences 49, no. 2 (1994): 149-167. Link

[KaIm04] Kabanets, Valentine, and Russell Impagliazzo. “Derandomizing polynomial identity tests means proving circuit lower bounds.” computational complexity 13, no. 1-2 (2004): 1-46. Link

This is a fascinating problem. A technical remark I suggest to have new comments appearing on the front page of the blog. (Like in the polymath blog, or my blog and many others.) This can be done via a suitable editing of the “widgets” in “appearance”.

Like

Dear Professor Kalai, thank you very much for your suggestions! The PolyTCS Editor Team has taken care of it. 😉

Liked by 1 person

Project 1: The Entropy-Influence Conjecture

The entropy-influence conjecture was originally asked by Ehud Friedgut and Gil Kalai in 1996.

For a boolean function $f:\{-1,1\}^{n}\rightarrow\{-1,1\}$, its influence is $I(f) := \sum_{i\in[n]}\Pr_{x}[f(x) \neq f(x\oplus e_{i})]$.
The entropy of $f$ is defined by $\mathcal{H}(f):= -\sum_{S}\hat{f}(S)^{2}\log(\hat{f}(S)^{2})$. The entropy-influence conjecture asks, could we prove that $\mathcal{H}(f) = O(I(f))$ for any boolean function $f$.

In my knowledge, the best known (general) result was given by Gopalan, Servedio, Tal and Wigderson [1]. They proved that $\mathcal{H}(f) = O(\log (s_{f}) \cdot I(f))$ where $s_{f}$ is the sensitivity of $f$. By plugging-in a robust version of [1], a result of Lovett, Tal and Zhang [2] shows that we can replace $s_{f}$ by the robust sensitivity. In particular, it shows $\mathcal{H}(f) = O(w\cdot \log w)$ for any width-$w$ DNF $f$.

The entropy-influence conjecture is known true for some classes of boolean functions. However it is still hard for general boolean functions. It is even non-trivial to prove that $\mathcal{H}(f) = 2^{O(I(f))}$.

An easier question is the min-entropy influence conjecture. Which asks could we prove that $\mathcal{H}_{\infty}(f) = O(I(f))$. By Friedgut’s juntas theorem, we are able to prove $\mathcal{H}_{\infty}(f) = O(I(f)^{2})$. It is interesting to ask could we prove this true for entropy, i.e., could we prove that $\mathcal{H}(f) = O(I(f)^{2})$?

For certain classes:

• KKL theorem implies min-entropy influence conjecture holds for monotone functions.
• O’Donnell, Wright and Zhou [3] proved entropy influence conjecture holds for symmetric functions.

[1] Gopalan, P., Servedio, R., Tal, A. and Wigderson, A., 2016. Degree and sensitivity: tails of two distributions. arXiv preprint arXiv:1604.07432.

[2] Lovett, S., Tal, A. and Zhang, J., 2018. The robust sensitivity of boolean functions. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (pp. 1822-1833). Society for Industrial and Applied Mathematics.

[3] O’Donnell, R., Wright, J. and Zhou, Y. 2011. The Fourier Entropy-Influence Conjecture for certain classes of Boolean functions. In Proceedings of ICALP 2011.

Thank you for sharing your treasure, Jiapeng! That’s indeed a very interesting problem! Could you please provide a link of your result you mentioned?

Like

Which result? $\mathcal{H}_{\infty}(f) = O(I(f)^{2})$? I don’t think there is a link. It is a folklore.

Like

• Rupei Xu 6:02 pm on November 1, 2019 Permalink

“By Friedgut’s juntas theorem, we are able to prove…”

Like

Yes, there is no link for this result. It is an unpublished observation. It could be a good exercise.

Liked by 1 person

Ok, thank you.

Like

This is indeed a very nice problem and thankful to Jiapeng Zhang for proposing it. Two quick remarks are that I wrote in 2007 a post about it on Terry Tao’s blog https://terrytao.wordpress.com/2007/08/16/gil-kalai-the-entropyinfluence-conjecture/ , the second remark is that I heard about some recent soon-to-be-published works related to the conjecture (but not solving it).

Liked by 1 person

Thank you Gil. I will add more references about works in this conjecture soon. There are a lot of nice results (after your blog 😉 )

Like

Dear Gil, do you mean this paper? https://arxiv.org/pdf/1911.10579.pdf

Liked by 1 person

• Gil Kalai 6:32 pm on December 1, 2019 Permalink

Dear Jiapeng, yes this is what I meant!

Like

• Rupei Xu 7:37 pm on December 6, 2020 Permalink

Recently this paper was presented in FOCS 2020, here is the link to the talk: https://www.youtube.com/watch?v=X3mkTUmlX2Y

Like

Welcome to PolyTCS!

Let’s propose TCS problems and achieve amazing results together!

“Coming together is a beginning, staying together is progress, and working together is success.”

Henry Ford

“It is the long history of humankind (and animal kind, too) that those who learned to collaborate and improvise most effectively have prevailed.”

Charles Darwin

“Talent wins games, but teamwork and intelligence win championships.”

Michael Jordan

This is the first post on my new blog. I’m just getting this new blog going, so stay tuned for more. Subscribe below to get notified when I post new updates.

The precise quote of Michael Jordan should be: “Talent wins games, but teamwork and machine learning win championships.”

Liked by 2 people

I like this joke! If Michael Jordan trains another Michael Jordan with machine learning techniques, maybe there will be more championships! 😄

Like

• Gil Kalai 5:56 pm on October 12, 2019 Permalink

For me, the famous Michael Jordan is doing machine learning, but the less famous Michael Jordan is highly impressive as well 🙂

Liked by 1 person

You can use this logo I created a while back: http://grigory.us/pics/notequal.png

Like

Thank you Grigory! Could you please give an explanation of the meaning of your designed logo?

Like

• Grigory Yaroslavtsev 1:43 pm on October 8, 2019 Permalink

Well, it kind of says “one person is strictly less computationally powerful than the same person given oracle access to other people”, no?

Liked by 1 person

Great! Thank you, Grigory! I just changed the logo, it looks nice!

Like

c
Compose new post
j
Next post/Next comment
k
Previous post/Previous comment
r