Recent Updates Toggle Comment Threads | Keyboard Shortcuts

  • PolyTCS 7:35 pm on October 4, 2019 Permalink |  

    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.

     
    • Gil Kalai 5:32 am on October 7, 2019 Permalink | Log in to Reply

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

      Liked by 2 people

      • PolyTCS 5:44 am on October 7, 2019 Permalink | Log in to Reply

        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 🙂

          Like

    • Grigory Yaroslavtsev 11:27 am on October 7, 2019 Permalink | Log in to Reply

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

      Like

      • PolyTCS 8:38 pm on October 7, 2019 Permalink | Log in to Reply

        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

      • PolyTCS 8:30 pm on October 8, 2019 Permalink | Log in to Reply

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

        Like

  • shacharlovett 2:15 am on March 23, 2020 Permalink |  

    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.

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

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

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

     

     
  • Rupei Xu 3:24 am on March 6, 2020 Permalink |  

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

    More links: 

    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!

     
    • Gil Kalai 9:15 pm on March 7, 2020 Permalink | Log in to Reply

      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

    • PolyTCS 10:13 pm on March 7, 2020 Permalink | Log in to Reply

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

      Liked by 1 person

  • Jiapeng Zhang 1:20 pm on November 1, 2019 Permalink |  

    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})?

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

     
c
Compose new post
j
Next post/Next comment
k
Previous post/Previous comment
r
Reply
e
Edit
o
Show/Hide comments
t
Go to top
l
Go to login
h
Show/Hide help
shift + esc
Cancel
Create your website at WordPress.com
Get started