Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userLower Bounds by Birkhoff Interpolation
304
0
0.0
(
0
)
Added by
Pascal Koiran
Publication date
2015
fields
Informatics Engineering
and research's language is
English
Authors
Ignacio Garcia-Marco
Ask ChatGPT about the research
No Arabic abstract
In this paper we give lower bounds for the representation of real univariate polynomials as sums of powers of degree 1 polynomials. We present two families of polynomials of degree d such that the number of powers that are required in such a representation must be at least of order d. This is clearly optimal up to a constant factor. Previous lower bounds for this problem were only of order $Omega$($sqrt$ d), and were obtained from arguments based on Wronskian determinants and shifted derivatives. We obtain this improvement thanks to a new lower bound method based on Birkhoff interpolation (also known as lacunary polynomial interpolation).
rate research
Read More
We demonstrate a lower bound technique for linear decision lists, which are decision lists where the queries are arbitrary linear threshold functions. We use this technique to prove an explicit lower bound by showing that any linear decision list computing the function $MAJ circ XOR$ requires size $2^{0.18 n}$. This completely answers an open question of Tur{a}n and Vatan [FoCM97]. We also show that the spectral classes $PL_1, PL_infty$, and the polynomial threshold function classes $widehat{PT}_1, PT_1$, are incomparable to linear decision lists.
We show that every construction of one-time signature schemes from a random oracle achieves black-box security at most $2^{(1+o(1))q}$, where $q$ is the total number of oracle queries asked by the key generation, signing, and verification algorithms. That is, any such scheme can be broken with probability close to $1$ by a (computationally unbounded) adversary making $2^{(1+o(1))q}$ queries to the oracle. This is tight up to a constant factor in the number of queries, since a simple modification of Lamports one-time signatures (Lamport 79) achieves $2^{(0.812-o(1))q}$ black-box security using $q$ queries to the oracle. Our result extends (with a loss of a constant factor in the number of queries) also to the random permutation and ideal-cipher oracles. Since the symmetric primitives (e.g. block ciphers, hash functions, and message authentication codes) can be constructed by a constant number of queries to the mentioned oracles, as corollary we get lower bounds on the efficiency of signature schemes from symmetric primitives when the construction is black-box. This can be taken as evidence of an inherent efficiency gap between signature schemes and symmetric primitives.
We prove a query complexity lower bound for $mathsf{QMA}$ protocols that solve approximate counting: estimating the size of a set given a membership oracle. This gives rise to an oracle $A$ such that $mathsf{SBP}^A otsubset mathsf{QMA}^A$, resolving an open problem of Aaronson [2]. Our proof uses the polynomial method to derive a lower bound for the $mathsf{SBQP}$ query complexity of the $mathsf{AND}$ of two approximate counting instances. We use Laurent polynomials as a tool in our proof, showing that the Laurent polynomial method can be useful even for problems involving ordinary polynomials.
Robust sunflowers are a generalization of combinatorial sunflowers that have applications in monotone circuit complexity, DNF sparsification, randomness extractors, and recent advances on the ErdH{o}s-Rado sunflower conjecture. The recent breakthrough of Alweiss, Lovett, Wu and Zhang gives an improved bound on the maximum size of a $w$-set system that excludes a robust sunflower. In this paper, we use this result to obtain an $exp(n^{1/2-o(1)})$ lower bound on the monotone circuit size of an explicit $n$-variate monotone function, improving the previous best known $exp(n^{1/3-o(1)})$ due to Andreev and Harnik and Raz. We also show an $exp(Omega(n))$ lower bound on the monotone arithmetic circuit size of a related polynomial. Finally, we introduce a notion of robust clique-sunflowers and use this to prove an $n^{Omega(k)}$ lower bound on the monotone circuit size of the CLIQUE function for all $k le n^{1/3-o(1)}$, strengthening the bound of Alon and Boppana.
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.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
