Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userTowards Stronger Counterexamples to the Log-Approximate-Rank Conjecture
95
0
0.0
(
0
)
Added by
Suhail Sherif
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We give improved separations for the query complexity analogue of the log-approximate-rank conjecture i.e. we show that there are a plethora of total Boolean functions on $n$ input bits, each of which has approximate Fourier sparsity at most $O(n^3)$ and randomized parity decision tree complexity $Theta(n)$. This improves upon the recent work of Chattopadhyay, Mande and Sherif (JACM 20) both qualitatively (in terms of designing a large number of examples) and quantitatively (improving the gap from quartic to cubic). We leave open the problem of proving a randomized communication complexity lower bound for XOR compositions of our examples. A linear lower bound would lead to new and improved refutations of the log-approximate-rank conjecture. Moreover, if any of these compositions had even a sub-linear cost randomized communication protocol, it would demonstrate that randomized parity decision tree complexity does not lift to randomized communication complexity in general (with the XOR gadget).
rate research
Read More
A quadrisecant of a knot is a straight line intersecting the knot at four points. If a knot has finitely many quadrisecants, one can replace each subarc between two adjacent secant points by the line segment between them to get the quadrisecant approximation of the original knot. It was conjectured that the quadrisecant approximation is always a knot with the same knot type as the original knot. We show that every knot type contains two knots, the quadrisecant approximation of one knot has self intersections while the quadrisecant approximation of the other knot is a knot with different knot type.
We prove upper bounds on deterministic communication complexity in terms of log of the rank and simp
Let $f: {0,1}^n to {0, 1}$ be a boolean function, and let $f_land (x, y) = f(x land y)$ denote the AND-function of $f$, where $x land y$ denotes bit-wise AND. We study the deterministic communication complexity of $f_land$ and show that, up to a $log n$ factor, it is bounded by a polynomial in the logarithm of the real rank of the communication matrix of $f_land$. This comes within a $log n$ factor of establishing the log-rank conjecturefor AND-functions with no assumptions on $f$. Our result stands in contrast with previous results on special cases of the log-rank conjecture, which needed significant restrictions on $f$ such as monotonicity or low $mathbb{F}_2$-degree. Our techniques can also be used to prove (within a $log n$ factor) a lifting theorem for AND-functions, stating that the deterministic communication complexity of $f_land$ is polynomially-related to the AND-decision tree complexity of $f$. The results rely on a new structural result regarding boolean functions $f:{0, 1}^n to {0, 1}$ with a sparse polynomial representation, which may be of independent interest. We show that if the polynomial computing $f$ has few monomials then the set system of the monomials has a small hitting set, of size poly-logarithmic in its sparsity. We also establish extensions of this result to multi-linear polynomials $f:{0,1}^n to mathbb{R}$ with a larger range.
Hedetniemi conjectured in 1966 that $chi(G times H) = min{chi(G), chi(H)}$ for all graphs $G$ and $H$. Here $Gtimes H$ is the graph with vertex set $ V(G)times V(H)$ defined by putting $(x,y)$ and $(x,y)$ adjacent if and only if $xxin E(G)$ and $yyin E(H)$. This conjecture received a lot of attention in the past half century. Recently, Shitov refuted this conjecture. Let $p$ be the minimum number of vertices in a graph of odd girth $7$ and fractional chromatic number greater than $3+4/(p-1)$. Shitovs proof shows that Hedetniemis conjecture fails for some graphs with chromatic number about $p^22^{p+1} $ and with about $(p^22^{p+1})^{p^32^{p-1}} $ vertices. In this paper, we show that the conjecture fails already for some graphs $G$ and $H$ with chromatic number $3lceil frac {p+1}2 rceil $ and with $p lceil (p-1)/2 rceil$ and $3 lceil frac {p+1}2 rceil (p+1)-p$ vertices, respectively. The currently known upper bound for $p$ is $148$. Thus Hedetniemis conjecture fails for some graphs $G$ and $H$ with chromatic number $225$, and with $10,952$ and $33,377$ vertices, respectively.
We study the log-rank conjecture from the perspective of point-hyperplane incidence geometry. We formulate the following conjecture: Given a point set in $mathbb{R}^d$ that is covered by constant-sized sets of parallel hyperplanes, there exists an affine subspace that accounts for a large (i.e., $2^{-{operatorname{polylog}(d)}}$) fraction of the incidences. Alternatively, our conjecture may be interpreted linear-algebraically as follows: Any rank-$d$ matrix containing at most $O(1)$ distinct entries in each column contains a submatrix of fractional size $2^{-{operatorname{polylog}(d)}}$, in which each column contains one distinct entry. We prove that our conjecture is equivalent to the log-rank conjecture. Motivated by the connections above, we revisit well-studied questions in point-hyperplane incidence geometry without structural assumptions (i.e., the existence of partitions). We give an elementary argument for the existence of complete bipartite subgraphs of density $Omega(epsilon^{2d}/d)$ in any $d$-dimensional configuration with incidence density $epsilon$. We also improve an upper-bound construction of Apfelbaum and Sharir (SIAM J. Discrete Math. 07), yielding a configuration whose complete bipartite subgraphs are exponentially small and whose incidence density is $Omega(1/sqrt d)$. Finally, we discuss various constructions (due to others) which yield configurations with incidence density $Omega(1)$ and bipartite subgraph density $2^{-Omega(sqrt d)}$. Our framework and results may help shed light on the difficulty of improving Lovetts $tilde{O}(sqrt{operatorname{rank}(f)})$ bound (J. ACM 16) for the log-rank conjecture; in particular, any improvement on this bound would imply the first bipartite subgraph size bounds for parallel $3$-partitioned configurations which beat our generic bounds for unstructured configurations.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
