## 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

## 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.

## Project 2: Is Semi-Definite Programming (SDP) Polynomial-Time Solvable?

Semi-Definite Programming (SDP) is an extension of Linear Programming (LP), with vector variables replaced by matrix variables and nonnegativity elementwise replaced by positive semidefiniteness.

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 to get a truly polynomial-time algorithm for SDP in several aspects and discuss how to make any new progress.

## (1) The Complexity of Square-Root Sum

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 show whether the square-root-sum problem is polynomial-time solvable or not. link

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.” link

The most remarkable progress towards this problem is by Eric Allender and his co-authors, in 2003, they showed this problem lies in the 4th level of the Counting Hierarchy. link

In CCC 2019 workshop open problem session, I presented the square-root sum 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.”

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). Link

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 link . 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 link .

Matthew Anderson, Anuj Dawar and  Bjarki Holm showed that the optimization of linear programs is expressible in FPC link. 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) link.

How does that new progress help us to understand the complexity of SDP?

## (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 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.

## (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 disproved the continuous analogue of Hirsch conjecture and showed primal-dual log-barrier interior point methods are not strongly polynomial together with other coauthors using an amazing new technique–Tropical Geometry link.  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 link.

Pablo A. Parrilo also showed the connection of SDP and convex algebraic geometry link.

Can those tools help to get a truly polynomial-time algorithm of SDP?

## (5) Exact Computation and Number Theory

Yuan Zhou (University of Kentucky) suggested the interval approximate method from the exact computation area to handle the square-root sum problem.  Yuan Zhou has a series of excellent papers about function generating together with her Ph.D. advisor. It is interesting to ask if one can generate a function related to square-root sum efficiently, is that helpful to say something about its complexity? (In P or in NP? )

Qi Cheng (University of Oklahoma) suggested applying diophantine approximation from number theory to improve the square-root sum problem.  What is the minimum nonzero difference between two sums of square roots of integers? Qi Cheng, Xianmeng Meng, Celi Sun, and Jiazhe Chen gave a tighter upper bound 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 Link and the Kabanets-Impagliazzo paper Link. 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!

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.

Like

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).

Like

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

Like

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

Dear Jiapeng, yes this is what I meant!

Like

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