Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userTesting convexity of functions over finite domains
63
0
0.0
(
0
)
Added by
Aleksandrs Belovs
Publication date
2019
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We establish new upper and lower bounds on the number of queries required to test convexity of functions over various discrete domains. 1. We provide a simplified version of the non-adaptive convexity tester on the line. We re-prove the upper bound $O(frac{log(epsilon n)}{epsilon})$ in the usual uniform model, and prove an $O(frac{log n}{epsilon})$ upper bound in the distribution-free setting. 2. We show a tight lower bound of $Omega(frac{log(epsilon n)}{epsilon})$ queries for testing convexity of functions $f: [n] rightarrow mathbb{R}$ on the line. This lower bound applies to both adaptive and non-adaptive algorithms, and matches the upper bound from item 1, showing that adaptivity does not help in this setting. 3. Moving to higher dimensions, we consider the case of a stripe $[3] times [n]$. We construct an emph{adaptive} tester for convexity of functions $fcolon [3] times [n] to mathbb R$ with query complexity $O(log^2 n)$. We also show that any emph{non-adaptive} tester must use $Omega(sqrt{n})$ queries in this setting. Thus, adaptivity yields an exponential improvement for this problem. 4. For functions $fcolon [n]^d to mathbb R$ over domains of dimension $d geq 2$, we show a non-adaptive query lower bound $Omega((frac{n}{d})^{frac{d}{2}})$.
rate research
Read More
The well-known DeMillo-Lipton-Schwartz-Zippel lemma says that $n$-variate polynomials of total degree at most $d$ over grids, i.e. sets of the form $A_1 times A_2 times cdots times A_n$, form error-correcting codes (of distance at least $2^{-d}$ provided $min_i{|A_i|}geq 2$). In this work we explore their local decodability and (tolerant) local testability. While these aspects have been studied extensively when $A_1 = cdots = A_n = mathbb{F}_q$ are the same finite field, the setting when $A_i$s are not the full field does not seem to have been explored before. In this work we focus on the case $A_i = {0,1}$ for every $i$. We show that for every field (finite or otherwise) there is a test whose query complexity depends only on the degree (and not on the number of variables). In contrast we show that decodability is possible over fields of positive characteristic (with query complexity growing with the degree of the polynomial and the characteristic), but not over the reals, where the query complexity must grow with $n$. As a consequence we get a natural example of a code (one with a transitive group of symmetries) that is locally testable but not locally decodable. Classical results on local decoding and testing of polynomials have relied on the 2-transitive symmetries of the space of low-degree polynomials (under affine transformations). Grids do not possess this symmetry: So we introduce some new techniques to overcome this handicap and in particular use the hypercontractivity of the (constant weight) noise operator on the Hamming cube.
In this paper we study arithmetic computations in the nonassociative, and noncommutative free polynomial ring $mathbb{F}{x_1,x_2,ldots,x_n}$. Prior to this work, nonassociative arithmetic computation was considered by Hrubes, Wigderson, and Yehudayoff [HWY10], and they showed lower bounds and proved completeness results. We consider Polynomial Identity Testing (PIT) and polynomial factorization over $mathbb{F}{x_1,x_2,ldots,x_n}$ and show the following results. (1) Given an arithmetic circuit $C$ of size $s$ computing a polynomial $fin mathbb{F} {x_1,x_2,ldots,x_n}$ of degree $d$, we give a deterministic $poly(n,s,d)$ algorithm to decide if $f$ is identically zero polynomial or not. Our result is obtained by a suitable adaptation of the PIT algorithm of Raz-Shpilka [RS05] for noncommutative ABPs. (2) Given an arithmetic circuit $C$ of size $s$ computing a polynomial $fin mathbb{F} {x_1,x_2,ldots,x_n}$ of degree $d$, we give an efficient deterministic algorithm to compute circuits for the irreducible factors of $f$ in time $poly(n,s,d)$ when $mathbb{F}=mathbb{Q}$. Over finite fields of characteristic $p$, our algorithm runs in time $poly(n,s,d,p)$.
Let $mathbb{F}_{p^{n}}$ be the finite field with $p^n$ elements and $operatorname{Tr}(cdot)$ be the trace function from $mathbb{F}_{p^{n}}$ to $mathbb{F}_{p}$, where $p$ is a prime and $n$ is an integer. Inspired by the works of Mesnager (IEEE Trans. Inf. Theory 60(7): 4397-4407, 2014) and Tang et al. (IEEE Trans. Inf. Theory 63(10): 6149-6157, 2017), we study a class of bent functions of the form $f(x)=g(x)+F(operatorname{Tr}(u_1x),operatorname{Tr}(u_2x),cdots,operatorname{Tr}(u_{tau}x))$, where $g(x)$ is a function from $mathbb{F}_{p^{n}}$ to $mathbb{F}_{p}$, $taugeq2$ is an integer, $F(x_1,cdots,x_n)$ is a reduced polynomial in $mathbb{F}_{p}[x_1,cdots,x_n]$ and $u_iin mathbb{F}^{*}_{p^n}$ for $1leq i leq tau$. As a consequence, we obtain a generic result on the Walsh transform of $f(x)$ and characterize the bentness of $f(x)$ when $g(x)$ is bent for $p=2$ and $p>2$ respectively. Our results generalize some earlier works. In addition, we study the construction of bent functions $f(x)$ when $g(x)$ is not bent for the first time and present a class of bent functions from non-bent Gold functions.
In this paper necessary and sufficient conditions are deduced for the close-to-convexity of some special combinations of Bessel functions of the first kind and their derivatives by using a result of Shah and Trimble about transcendental entire functions with univalent derivatives and some newly discovered Mittag-Leffler expansions for Bessel functions of the first kind.
In 2005, Kayal suggested that Schoofs algorithm for counting points on elliptic curves over finite fields might yield an approach to factor polynomials over finite fields in deterministic polynomial time. We present an exposition of his idea and then explain details of a generalization involving Pilas algorithm for abelian varieties.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
