Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userJunta correlation is testable
55
0
0.0
(
0
)
Added by
Anindya De
Publication date
2019
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
The problem of tolerant junta testing is a natural and challenging problem which asks if the property of a function having some specified correlation with a $k$-Junta is testable. In this paper we give an affirmative answer to this question: We show that given distance parameters $frac{1}{2} >c_u>c_{ell} ge 0$, there is a tester which given oracle access to $f:{-1,1}^n rightarrow {-1,1}$, with query complexity $ 2^k cdot mathsf{poly}(k,1/|c_u-c_{ell}|)$ and distinguishes between the following cases: $mathbf{1.}$ The distance of $f$ from any $k$-junta is at least $c_u$; $mathbf{2.}$ There is a $k$-junta $g$ which has distance at most $c_ell$ from $f$. This is the first non-trivial tester (i.e., query complexity is independent of $n$) which works for all $1/2 > c_u > c_ell ge 0$. The best previously known results by Blais emph{et~ al.}, required $c_u ge 16 c_ell$. In fact, with the same query complexity, we accomplish the stronger goal of identifying the most correlated $k$-junta, up to permutations of the coordinates. We can further improve the query complexity to $mathsf{poly}(k, 1/|c_u-c_{ell}|)$ for the (weaker) task of distinguishing between the following cases: $mathbf{1.}$ The distance of $f$ from any $k$-junta is at least $c_u$. $mathbf{2.}$ There is a $k$-junta $g$ which is at a distance at most $c_ell$ from $f$. Here $k=O(k^2/|c_u-c_ell|)$. Our main tools are Fourier analysis based algorithms that simulate oracle access to influential coordinates of functions.
rate research
Read More
We present an algorithm for strongly refuting smoothed instances of all Boolean CSPs. The smoothed model is a hybrid between worst and average-case input models, where the input is an arbitrary instance of the CSP with only the negation patterns of the literals re-randomized with some small probability. For an $n$-variable smoothed instance of a $k$-arity CSP, our algorithm runs in $n^{O(ell)}$ time, and succeeds with high probability in bounding the optimum fraction of satisfiable constraints away from $1$, provided that the number of constraints is at least $tilde{O}(n) (frac{n}{ell})^{frac{k}{2} - 1}$. This matches, up to polylogarithmic factors in $n$, the trade-off between running time and the number of constraints of the state-of-the-art algorithms for refuting fully random instances of CSPs [RRS17]. We also make a surprising new connection between our algorithm and even covers in hypergraphs, which we use to positively resolve Feiges 2008 conjecture, an extremal combinatorics conjecture on the existence of even covers in sufficiently dense hypergraphs that generalizes the well-known Moore bound for the girth of graphs. As a corollary, we show that polynomial-size refutation witnesses exist for arbitrary smoothed CSP instances with number of constraints a polynomial factor below the spectral threshold of $n^{k/2}$, extending the celebrated result for random 3-SAT of Feige, Kim and Ofek [FKO06].
The square root rank of a nonnegative matrix $A$ is the minimum rank of a matrix $B$ such that $A=B circ B$, where $circ$ denotes entrywise product. We show that the square root rank of the slack matrix of the correlation polytope is exponential. Our main technique is a way to lower bound the rank of certain matrices under arbitrary sign changes of the entries using properties of the roots of polynomials in number fields. The square root rank is an upper bound on the positive semidefinite rank of a matrix, and corresponds the special case where all matrices in the factorization are rank-one.
Let $mathcal{F}_{n}^*$ be the set of Boolean functions depending on all $n$ variables. We prove that for any $fin mathcal{F}_{n}^*$, $f|_{x_i=0}$ or $f|_{x_i=1}$ depends on the remaining $n-1$ variables, for some variable $x_i$. This existent result suggests a possible way to deal with general Boolean functions via its subfunctions of some restrictions. As an application, we consider the degree lower bound of representing polynomials over finite rings. Let $fin mathcal{F}_{n}^*$ and denote the exact representing degree over the ring $mathbb{Z}_m$ (with the integer $m>2$) as $d_m(f)$. Let $m=Pi_{i=1}^{r}p_i^{e_i}$, where $p_i$s are distinct primes, and $r$ and $e_i$s are positive integers. If $f$ is symmetric, then $mcdot d_{p_1^{e_1}}(f)... d_{p_r^{e_r}}(f) > n$. If $f$ is non-symmetric, by the second moment method we prove almost always $mcdot d_{p_1^{e_1}}(f)... d_{p_r^{e_r}}(f) > lg{n}-1$. In particular, as $m=pq$ where $p$ and $q$ are arbitrary distinct primes, we have $d_p(f)d_q(f)=Omega(n)$ for symmetric $f$ and $d_p(f)d_q(f)=Omega(lg{n}-1)$ almost always for non-symmetric $f$. Hence any $n$-variate symmetric Boolean function can have exact representing degree $o(sqrt{n})$ in at most one finite field, and for non-symmetric functions, with $o(sqrt{lg{n}})$-degree in at most one finite field.
We study property testing of (di)graph properties in bounded-degree graph models. The study of graph properties in bounded-degree models is one of the focal directions of research in property testing in the last 15 years. However, despite of the many results and the extensive research effort, there is no characterization of the properties that are strongly-testable (i.e., testable with constant query complexity) even for $1$-sided error tests. The bounded-degree model can naturally be generalized to directed graphs resulting in two models that were considered in the literature. The first contains the directed graphs in which the outdegree is bounded but the indegree is not restricted. In the other, both the outdegree and indegree are bounded. We give a characterization of the $1$-sided error strongly-testable {em monotone} graph properties, and the $1$-sided error strongly-testable {em hereditary} graph properties in all the bounded-degree directed and undirected graphs models.
In the Nikoli pencil-and-paper game Tatamibari, a puzzle consists of an $m times n$ grid of cells, where each cell possibly contains a clue among +, -, |. The goal is to partition the grid into disjoint rectangles, where every rectangle contains exactly one clue, rectangles containing + are square, rectangles containing - are strictly longer horizontally than vertically, rectangles containing | are strictly longer vertically than horizontally, and no four rectangles share a corner. We prove this puzzle NP-complete, establishing a Nikoli gap of 16 years. Along the way, we introduce a gadget framework for proving hardness of similar puzzles involving area coverage, and show that it applies to an existing NP-hardness proof for Spiral Galaxies. We also present a mathematical puzzle font for Tatamibari.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
