ﻻ يوجد ملخص باللغة العربية
We study the probabilistic degree over reals of the OR function on $n$ variables. For an error parameter $epsilon$ in (0,1/3), the $epsilon$-error probabilistic degree of any Boolean function $f$ over reals is the smallest non-negative integer $d$ such that the following holds: there exists a distribution $D$ of polynomials entirely supported on polynomials of degree at most $d$ such that for all $z in {0,1}^n$, we have $Pr_{P sim D} [P(z) = f(z) ] geq 1- epsilon$. It is known from the works of Tarui ({Theoret. Comput. Sci.} 1993) and Beigel, Reingold, and Spielman ({ Proc. 6th CCC} 1991), that the $epsilon$-error probabilistic degree of the OR function is at most $O(log n.log 1/epsilon)$. Our first observation is that this can be improved to $O{log {{n}choose{leq log 1/epsilon}}}$, which is better for small values of $epsilon$. In all known constructions of probabilistic polynomials for the OR function (including the above improvement), the polynomials $P$ in the support of the distribution $D$ have the following special structure:$P = 1 - (1-L_1).(1-L_2)...(1-L_t)$, where each $L_i(x_1,..., x_n)$ is a linear form in the variables $x_1,...,x_n$, i.e., the polynomial $1-P(x_1,...,x_n)$ is a product of affine forms. We show that the $epsilon$-error probabilistic degree of OR when restricted to polynomials of the above form is $Omega ( log a/log^2 a )$ where $a = log {{n}choose{leq log 1/epsilon}}$. Thus matching the above upper bound (up to poly-logarithmic factors).
We prove that 3-query linear locally correctable codes over the Reals of dimension $d$ require block length $n>d^{2+lambda}$ for some fixed, positive $lambda >0$. Geometrically, this means that if $n$ vectors in $R^d$ are such that each vector is spa
We study how well functions over the boolean hypercube of the form $f_k(x)=(|x|-k)(|x|-k-1)$ can be approximated by sums of squares of low-degree polynomials, obtaining good bounds for the case of approximation in $ell_{infty}$-norm as well as in $el
This paper is concerned with exact real solving of well-constrained, bivariate polynomial systems. The main problem is to isolate all common real roots in rational rectangles, and to determine their intersection multiplicities. We present three algor
We propose models for lobbying in a probabilistic environment, in which an actor (called The Lobby) seeks to influence voters preferences of voting for or against multiple issues when the voters preferences are represented in terms of probabilities.
We show that for any odd $k$ and any instance of the Max-kXOR constraint satisfaction problem, there is an efficient algorithm that finds an assignment satisfying at least a $frac{1}{2} + Omega(1/sqrt{D})$ fraction of constraints, where $D$ is a boun