Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userRandom restrictions and PRGs for PTFs in Gaussian Space
241
0
0.0
(
0
)
Added by
Zander Kelley
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
A polynomial threshold function (PTF) $f:mathbb{R}^n rightarrow mathbb{R}$ is a function of the form $f(x) = mathsf{sign}(p(x))$ where $p$ is a polynomial of degree at most $d$. PTFs are a classical and well-studied complexity class with applications across complexity theory, learning theory, approximation theory, quantum complexity and more. We address the question of designing pseudorandom generators (PRG) for polynomial threshold functions (PTFs) in the gaussian space: design a PRG that takes a seed of few bits of randomness and outputs a $n$-dimensional vector whose distribution is indistinguishable from a standard multivariate gaussian by a degree $d$ PTF. Our main result is a PRG that takes a seed of $d^{O(1)}log ( n / varepsilon)log(1/varepsilon)/varepsilon^2$ random bits with output that cannot be distinguished from $n$-dimensional gaussian distribution with advantage better than $varepsilon$ by degree $d$ PTFs. The best previous generator due to ODonnell, Servedio, and Tan (STOC20) had a quasi-polynomial dependence (i.e., seedlength of $d^{O(log d)}$) in the degree $d$. Along the way we prove a few nearly-tight structural properties of restrictions of PTFs that may be of independent interest.
rate research
Read More
We give a pseudorandom generator that fools degree-$d$ polynomial threshold functions over $n$-dimensional Gaussian space with seed length $mathrm{poly}(d)cdot log n$. All previous generators had a seed length with at least a $2^d$ dependence on $d$. The key new ingredient is a Local Hyperconcentration Theorem, which shows that every degree-$d$ Gaussian polynomial is hyperconcentrated almost everywhere at scale $d^{-O(1)}$.
We give a deterministic, nearly logarithmic-space algorithm that given an undirected graph $G$, a positive integer $r$, and a set $S$ of vertices, approximates the conductance of $S$ in the $r$-step random walk on $G$ to within a factor of $1+epsilon$, where $epsilon>0$ is an arbitrarily small constant. More generally, our algorithm computes an $epsilon$-spectral approximation to the normalized Laplacian of the $r$-step walk. Our algorithm combines the derandomized square graph operation (Rozenman and Vadhan, 2005), which we recently used for solving Laplacian systems in nearly logarithmic space (Murtagh, Reingold, Sidford, and Vadhan, 2017), with ideas from (Cheng, Cheng, Liu, Peng, and Teng, 2015), which gave an algorithm that is time-efficient (while ours is space-efficient) and randomized (while ours is deterministic) for the case of even $r$ (while ours works for all $r$). Along the way, we provide some new results that generalize technical machinery and yield improvements over previous work. First, we obtain a nearly linear-time randomized algorithm for computing a spectral approximation to the normalized Laplacian for odd $r$. Second, we define and analyze a generalization of the derandomized square for irregular graphs and for sparsifying the product of two distinct graphs. As part of this generalization, we also give a strongly explicit construction of expander graphs of every size.
We provide a deterministic $tilde{O}(log N)$-space algorithm for estimating random walk probabilities on undirected graphs, and more generally Eulerian directed graphs, to within inverse polynomial additive error ($epsilon=1/mathrm{poly}(N)$) where $N$ is the length of the input. Previously, this problem was known to be solvable by a randomized algorithm using space $O(log N)$ (following Aleliunas et al., FOCS 79) and by a deterministic algorithm using space $O(log^{3/2} N)$ (Saks and Zhou, FOCS 95 and JCSS 99), both of which held for arbitrary directed graphs but had not been improved even for undirected graphs. We also give improvements on the space complexity of both of these previous algorithms for non-Eulerian directed graphs when the error is negligible ($epsilon=1/N^{omega(1)}$), generalizing what Hoza and Zuckerman (FOCS 18) recently showed for the special case of distinguishing whether a random walk probability is $0$ or greater than $epsilon$. We achieve these results by giving new reductions between powering Eulerian random-walk matrices and inverting Eulerian Laplacian matrices, providing a new notion of spectral approximation for Eulerian graphs that is preserved under powering, and giving the first deterministic $tilde{O}(log N)$-space algorithm for inverting Eulerian Laplacian matrices. The latter algorithm builds on the work of Murtagh et al. (FOCS 17) that gave a deterministic $tilde{O}(log N)$-space algorithm for inverting undirected Laplacian matrices, and the work of Cohen et al. (FOCS 19) that gave a randomized $tilde{O}(N)$-time algorithm for inverting Eulerian Laplacian matrices. A running theme throughout these contributions is an analysis of cycle-lifted graphs, where we take a graph and lift it to a new graph whose adjacency matrix is the tensor product of the original adjacency matrix and a directed cycle (or variants of one).
A resolution of the quantum measurement problem(s) using the consistent histories interpretation yields in a rather natural way a restriction on what an observer can know about a quantum system, one that is also consistent with some results in quantum information theory. This analysis provides a quantum mechanical understanding of some recent work that shows that certain kinds of quantum behavior are exhibited by a fully classical model if by hypothesis an observers knowledge of its state is appropriately limited.
The problem of distinguishing between a random function and a random permutation on a domain of size $N$ is important in theoretical cryptography, where the security of many primitives depend on the problems hardness. We study the quantum query complexity of this problem, and show that any quantum algorithm that solves this problem with bounded error must make $Omega(N^{1/5}/log N)$ queries to the input function. Our lower bound proof uses a combination of the Collision Problem lower bound and Ambainiss adversary theorem.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
