Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userSet Families with Low Pairwise Intersection
158
0
0.0
(
0
)
Added by
Jeremiah Blocki
Publication date
2014
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
A $left(n,ell,gammaright)$-sharing set family of size $m$ is a family of sets $S_1,ldots,S_msubseteq [n]$ s.t. each set has size $ell$ and each pair of sets shares at most $gamma$ elements. We let $mleft(n,ell,gammaright)$ denote the maximum size of any such set family and we consider the following question: How large can $mleft(n,ell,gammaright)$ be? $left(n,ell,gammaright)$-sharing set families have a rich set of applications including the construction of pseudorandom number generators and usable and secure password management schemes. We analyze the explicit construction of Blocki et al using recent bounds on the value of the $t$th Ramanujan prime. We show that this explicit construction produces a $left(4ell^2ln 4ell,ell,gammaright)$-sharing set family of size $left(2 ell ln 2ellright)^{gamma+1}$ for any $ellgeq gamma$. We also show that the construction of Blocki et al can be used to obtain a weak $left(n,ell,gammaright)$-sharing set family of size $m$ for any $m >0$. These results are competitive with the inexplicit construction of Raz et al for weak $left(n,ell,gammaright)$-sharing families. We show that our explicit construction of weak $left(n,ell,gammaright)$-sharing set families can be used to obtain a parallelizable pseudorandom number generator with a low memory footprint by using the pseudorandom number generator of Nisan and Wigderson. We also prove that $mleft(n,n/c_1,c_2nright)$ must be a constant whenever $c_2 leq frac{2}{c_1^3+c_1^2}$. We show that this bound is nearly tight as $mleft(n,n/c_1,c_2nright)$ grows exponentially fast whenever $c_2 > c_1^{-2}$.
rate research
Read More
Say that A is a Hadamard factorization of the identity I_n of size n if the entrywise product of A and the transpose of A is I_n. It can be easily seen that the rank of any Hadamard factorization of the identity must be at least sqrt{n}. Dietzfelbinger et al. raised the question if this bound can be achieved, and showed a boolean Hadamard factorization of the identity of rank n^{0.792}. More recently, Klauck and Wolf gave a construction of Hadamard factorizations of the identity of rank n^{0.613}. Over finite fields, Friesen and Theis resolved the question, showing for a prime p and r=p^t+1 a Hadamard factorization of the identity A of size r(r-1)+1 and rank r over F_p. Here we resolve the question for fields of zero characteristic, up to a constant factor, giving a construction of Hadamard factorizations of the identity of rank r and size (r+1)r/2. The matrices in our construction are blockwise Toeplitz, and have entries whose magnitudes are binomial coefficients.
We obtain an estimate on the average cardinality of the value set of any family of monic polynomials of Fq[T] of degree d for which s consecutive coefficients a_{d-1},..., a_{d-s} are fixed. Our estimate holds without restrictions on the characteristic of Fq and asserts that V(d,s,bfs{a})=mu_d.q+mathcal{O}(1), where V(d,s,bfs{a}) is such an average cardinality, mu_d:=sum_{r=1}^d{(-1)^{r-1}}/{r!} and bfs{a}:=(a_{d-1},.., d_{d-s}). We provide an explicit upper bound for the constant underlying the mathcal{O}--notation in terms of d and s with good behavior. Our approach reduces the question to estimate the number of Fq--rational points with pairwise--distinct coordinates of a certain family of complete intersections defined over Fq. We show that the polynomials defining such complete intersections are invariant under the action of the symmetric group of permutations of the coordinates. This allows us to obtain critical information concerning the singular locus of the varieties under consideration, from which a suitable estimate on the number of Fq--rational points is established.
The communication class $mathbf{UPP}^{text{cc}}$ is a communication analog of the Turing Machine complexity class $mathbf{PP}$. It is characterized by a matrix-analytic complexity measure called sign-rank (also called dimension complexity), and is essentially the most powerful communication class against which we know how to prove lower bounds. For a communication problem $f$, let $f wedge f$ denote the function that evaluates $f$ on two disjoint inputs and outputs the AND of the results. We exhibit a communication problem $f$ with $mathbf{UPP}(f)= O(log n)$, and $mathbf{UPP}(f wedge f) = Theta(log^2 n)$. This is the first result showing that $mathbf{UPP}$ communication complexity can increase by more than a constant factor under intersection. We view this as a first step toward showing that $mathbf{UPP}^{text{cc}}$, the class of problems with polylogarithmic-cost $mathbf{UPP}$ communication protocols, is not closed under intersection. Our result shows that the function class consisting of intersections of two majorities on $n$ bits has dimension complexity $n^{Omega(log n)}$. This matches an upper bound of (Klivans, ODonnell, and Servedio, FOCS 2002), who used it to give a quasipolynomial time algorithm for PAC learning intersections of polylogarithmically many majorities. Hence, fundamentally new techniques will be needed to learn this class of functions in polynomial time.
We prove that for every $epsilon>0$ and predicate $P:{0,1}^krightarrow {0,1}$ that supports a pairwise independent distribution, there exists an instance $mathcal{I}$ of the $mathsf{Max}P$ constraint satisfaction problem on $n$ variables such that no assignment can satisfy more than a $tfrac{|P^{-1}(1)|}{2^k}+epsilon$ fraction of $mathcal{I}$s constraints but the degree $Omega(n)$ Sum of Squares semidefinite programming hierarchy cannot certify that $mathcal{I}$ is unsatisfiable. Similar results were previously only known for weaker hierarchies.
Set disjointness is a central problem in communication complexity. Here Alice and Bob each receive a subset of an n-element universe, and they need to decide whether their inputs intersect or not. The communication complexity of this problem is relatively well understood, and in most models, including $-$ most famously $-$ interactive randomised communication with bounded error, the problem requires much communication. In this work we were looking for a variation of the set disjointness problem, as natural and simple as possible, for which the known lower bound methods would fail, and thus a new approach would be required in order to understand its complexity. The problem that we have found is a relational one: each player receives a subset as input, and the goal is to find an element that belongs to both players. We call it inevitable intersection.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
