BZPEERReading, trust and collaboration for researchDiscover
Workspaces
Network
Opportunities
Account
Researcher profile
Joe Neeman contributes to research discovery and scholarly infrastructure.
Trust snapshot
Actions
Identity and collaboration
Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.
Log in to claimDirect collaboration
Claim this author entity first to unlock direct invitations.
Research graph
Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Published work
We extend Caffarelli's contraction theorem, by proving that there exists a Lipschitz changes of variables between the Gaussian measure and certain perturbations of it. Our approach is based on an argument due to Kim and Milman, in which the changes of variables are constructed using a heat flow.
We prove moderate deviations bounds for the lower tail of the number of odd cycles in a $\calG(n, m)$ random graph. We show that the probability of decreasing triangle density by $t^3$, is $\exp(-Θ(n^2 t^2))$ whenever $n^{-3/4} \ll t^3 \ll 1$, while for $k \ge 5$ we give the same estimate for the probability of decreasing the $k$-cycle density by $t^k$, but for the larger range $n^{-1} \ll t^k \ll 1$. When $m \ge \frac 12 \binom n2$, we also find the leading coefficient in the exponent. This complements results of Goldschmidt et al., who showed that for $n^{-3/2} \ll t^k \ll n^{-1}$, the probability is $\exp(-Θ(n^3 t^{2k}))$. That is, deviations of order smaller than $n^{-1}$ behave like small deviations, and deviations of order larger than $n^{-3/4}$ (for triangles) or $n^{-1}$ (for $k$-cycles with $k \ge 5$) behave like large deviations. For triangles, we conjecture that a sharp change between the two regimes occurs for deviations of size $n^{-3/4}$, which we associate with a single large negative eigenvalue of the adjacency matrix becoming responsible for almost all of the cycle deficit. Our results can be interpreted as finite size effects in phase transitions in constrained random graphs.
The analysis of large simple graphs with extreme values of the densities of edges and triangles has been extended to the statistical structure of typical graphs of fixed intermediate densities, by the use of large deviations of Erdoes-Renyi graphs. We prove that the typical graph exhibits sharp singularities as the constraining densities vary between different curves of extreme values, and we determine the precise nature of the singularities. The extension to graphs with fixed densities of edges and k-cycles for odd k>3 is straightforward and we note the simple changes in the proof.
A natural problem in high-dimensional inference is to decide if a classifier $f:\mathbb{R}^n \rightarrow \{-1,1\}$ depends on a small number of linear directions of its input data. Call a function $g: \mathbb{R}^n \rightarrow \{-1,1\}$, a linear $k$-junta if it is completely determined by some $k$-dimensional subspace of the input space. A recent work of the authors showed that linear $k$-juntas are testable. Thus there exists an algorithm to distinguish between: 1. $f: \mathbb{R}^n \rightarrow \{-1,1\}$ which is a linear $k$-junta with surface area $s$, 2. $f$ is $ε$-far from any linear $k$-junta with surface area $(1+ε)s$, where the query complexity of the algorithm is independent of the ambient dimension $n$. Following the surge of interest in noise-tolerant property testing, in this paper we prove a noise-tolerant (or robust) version of this result. Namely, we give an algorithm which given any $c>0$, $ε>0$, distinguishes between 1. $f: \mathbb{R}^n \rightarrow \{-1,1\}$ has correlation at least $c$ with some linear $k$-junta with surface area $s$. 2. $f$ has correlation at most $c-ε$ with any linear $k$-junta with surface area at most $s$. The query complexity of our tester is $k^{\mathsf{poly}(s/ε)}$. Using our techniques, we also obtain a fully noise tolerant tester with the same query complexity for any class $\mathcal{C}$ of linear $k$-juntas with surface area bounded by $s$. As a consequence, we obtain a fully noise tolerant tester with query complexity $k^{O(\mathsf{poly}(\log k/ε))}$ for the class of intersection of $k$-halfspaces (for constant $k$) over the Gaussian space. Our query complexity is independent of the ambient dimension $n$. Previously, no non-trivial noise tolerant testers were known even for a single halfspace.
The planted bisection model is a random graph model in which the nodes are divided into two equal-sized communities and then edges are added randomly in a way that depends on the community membership. We establish necessary and sufficient conditions for the asymptotic recoverability of the planted bisection in this model. When the bisection is asymptotically recoverable, we give an efficient algorithm that successfully recovers it. We also show that the planted bisection is recoverable asymptotically if and only if with high probability every node belongs to the same community as the majority of its neighbors. Our algorithm for finding the planted bisection runs in time almost linear in the number of edges. It has three stages: spectral clustering to compute an initial guess, a "replica" stage to get almost every vertex correct, and then some simple local moves to finish the job. An independent work by Abbe, Bandeira, and Hall establishes similar (slightly weaker) results but only in the case of logarithmic average degree.