The Experts below are selected from a list of 53943 Experts worldwide ranked by ideXlab platform

Junxing Wang - One of the best experts on this subject based on the ideXlab platform.

  • graph sparsification spectral sketches and faster resistance computation via short cycle decompositions
    Foundations of Computer Science, 2018
    Co-Authors: Timothy Chu, Yu Gao, Richard Peng, Sushant Sachdeva, Saurabh Sawlani, Junxing Wang
    Abstract:

    We develop a framework for graph sparsification based on a new tool, short cycle decomposition for graphs – a decomposition of a graph into a collection of short cycles, plus a small number of extra edges. A simple observation gives that every graph G on n vertices with m edges can be decomposed in O(mn) time into cycles of length at most 2 log n, and at most 2n extra edges. We give an m1+o(1) time algorithm for constructing a short cycle decomposition of the graph, with cycles of length n^o(1), and n^1+o(1) extra edges. Both the existential and algorithmic variants of this decomposition enable us to make progress on several open problems in randomized graph algorithms. 1. We present an algorithm that runs in time m^1+o(1)e^-1.5 and returns (1 ± e)-approximations to effective resistances of all edges, improving over the previous best of O(min{me^-2, n^2 e^-1}) This gives an algorithm to approximate the determinant of a graph Laplacian up to a factor of (1 ± e) in roughly m + n^15/8 e^-7/4. 2. We show existence and efficient algorithms for constructing graphical spectral sketches – a distribution over sparse graphs H with about ne^-1 edges such that for a Fixed Vector x, we have x^T L_H x = (1 ± eps) x^T L_G x and x^T L+_H x = (1 ± e) x^T L+_G x with high probability, where L is the graph Laplacian and L+ is its pseudoinverse. This implies resistance-sparsifiers with about ne edges that preserve the effective resistances between every pair of vertices up to (1 + eps). 3. By combining short cycle decomposition with importance sampling, we show the existence of nearly-linear sized degree-preserving spectral sparsifiers, as well as significantly sparser approximations of directed graphs. The latter is critical to recent breakthroughs on faster algorithms for directed random walks and linear systems in directed Laplacian. The running time and output qualities of our spectral sketch and degree-preserving (directed) sparsification algorithms are limited by the efficiency of our routines for producing short cycle decompositions. Improved algorithms for short cycle decompositions will lead to improvements for each of these algorithms.

  • graph sparsification spectral sketches and faster resistance computation via short cycle decompositions
    arXiv: Data Structures and Algorithms, 2018
    Co-Authors: Timothy Chu, Yu Gao, Richard Peng, Sushant Sachdeva, Saurabh Sawlani, Junxing Wang
    Abstract:

    We develop a framework for graph sparsification and sketching, based on a new tool, short cycle decomposition -- a decomposition of an unweighted graph into an edge-disjoint collection of short cycles, plus few extra edges. A simple observation gives that every graph G on n vertices with m edges can be decomposed in $O(mn)$ time into cycles of length at most $2\log n$, and at most $2n$ extra edges. We give an $m^{1+o(1)}$ time algorithm for constructing a short cycle decomposition, with cycles of length $n^{o(1)}$, and $n^{1+o(1)}$ extra edges. These decompositions enable us to make progress on several open questions: * We give an algorithm to find $(1\pm\epsilon)$-approximations to effective resistances of all edges in time $m^{1+o(1)}\epsilon^{-1.5}$, improving over the previous best of $\tilde{O}(\min\{m\epsilon^{-2},n^2 \epsilon^{-1}\})$. This gives an algorithm to approximate the determinant of a Laplacian up to $(1\pm\epsilon)$ in $m^{1 + o(1)} + n^{15/8+o(1)}\epsilon^{-7/4}$ time. * We show existence and efficient algorithms for constructing graphical spectral sketches -- a distribution over sparse graphs H such that for a Fixed Vector $x$, we have w.h.p. $x'L_Hx=(1\pm\epsilon)x'L_Gx$ and $x'L_H^+x=(1\pm\epsilon)x'L_G^+x$. This implies the existence of resistance-sparsifiers with about $n\epsilon^{-1}$ edges that preserve the effective resistances between every pair of vertices up to $(1\pm\epsilon).$ * By combining short cycle decompositions with known tools in graph sparsification, we show the existence of nearly-linear sized degree-preserving spectral sparsifiers, as well as significantly sparser approximations of directed graphs. The latter is critical to recent breakthroughs on faster algorithms for solving linear systems in directed Laplacians. Improved algorithms for constructing short cycle decompositions will lead to improvements for each of the above results.

Eswarathasan Suresh - One of the best experts on this subject based on the ideXlab platform.

  • Tangent nodal sets for random spherical harmonics
    American Mathematical Society, 2019
    Co-Authors: Eswarathasan Suresh
    Abstract:

    In this note, we consider a Fixed Vector field $V$ on $S^2$ and study the distribution of points which lie on the nodal set (of a random spherical harmonic) where $V$ is also tangent. We show that the expected value of the corresponding counting function is asymptotic to the eigenvalue with a leading coefficient that is independent of the Vector field $V$. This demonstrates, in some form, a universality for Vector fields up to lower order terms

  • Tangent nodal sets for random spherical harmonics
    2018
    Co-Authors: Eswarathasan Suresh
    Abstract:

    In this note, we consider a Fixed Vector field $V$ on $S^2$ and study the distribution of points which lie on the nodal set (of a random spherical harmonic) where $V$ is also tangent. We show that the expected value of the corresponding counting function is asymptotic to the eigenvalue with a leading coefficient that is independent of the Vector field $V$. This demonstrates, in some form, a universality for Vector fields up to lower order terms.Comment: 26 pages. Minor changes with equation numbering. Updated introduction. All comments are welcom

Timothy Chu - One of the best experts on this subject based on the ideXlab platform.

  • graph sparsification spectral sketches and faster resistance computation via short cycle decompositions
    Foundations of Computer Science, 2018
    Co-Authors: Timothy Chu, Yu Gao, Richard Peng, Sushant Sachdeva, Saurabh Sawlani, Junxing Wang
    Abstract:

    We develop a framework for graph sparsification based on a new tool, short cycle decomposition for graphs – a decomposition of a graph into a collection of short cycles, plus a small number of extra edges. A simple observation gives that every graph G on n vertices with m edges can be decomposed in O(mn) time into cycles of length at most 2 log n, and at most 2n extra edges. We give an m1+o(1) time algorithm for constructing a short cycle decomposition of the graph, with cycles of length n^o(1), and n^1+o(1) extra edges. Both the existential and algorithmic variants of this decomposition enable us to make progress on several open problems in randomized graph algorithms. 1. We present an algorithm that runs in time m^1+o(1)e^-1.5 and returns (1 ± e)-approximations to effective resistances of all edges, improving over the previous best of O(min{me^-2, n^2 e^-1}) This gives an algorithm to approximate the determinant of a graph Laplacian up to a factor of (1 ± e) in roughly m + n^15/8 e^-7/4. 2. We show existence and efficient algorithms for constructing graphical spectral sketches – a distribution over sparse graphs H with about ne^-1 edges such that for a Fixed Vector x, we have x^T L_H x = (1 ± eps) x^T L_G x and x^T L+_H x = (1 ± e) x^T L+_G x with high probability, where L is the graph Laplacian and L+ is its pseudoinverse. This implies resistance-sparsifiers with about ne edges that preserve the effective resistances between every pair of vertices up to (1 + eps). 3. By combining short cycle decomposition with importance sampling, we show the existence of nearly-linear sized degree-preserving spectral sparsifiers, as well as significantly sparser approximations of directed graphs. The latter is critical to recent breakthroughs on faster algorithms for directed random walks and linear systems in directed Laplacian. The running time and output qualities of our spectral sketch and degree-preserving (directed) sparsification algorithms are limited by the efficiency of our routines for producing short cycle decompositions. Improved algorithms for short cycle decompositions will lead to improvements for each of these algorithms.

  • graph sparsification spectral sketches and faster resistance computation via short cycle decompositions
    arXiv: Data Structures and Algorithms, 2018
    Co-Authors: Timothy Chu, Yu Gao, Richard Peng, Sushant Sachdeva, Saurabh Sawlani, Junxing Wang
    Abstract:

    We develop a framework for graph sparsification and sketching, based on a new tool, short cycle decomposition -- a decomposition of an unweighted graph into an edge-disjoint collection of short cycles, plus few extra edges. A simple observation gives that every graph G on n vertices with m edges can be decomposed in $O(mn)$ time into cycles of length at most $2\log n$, and at most $2n$ extra edges. We give an $m^{1+o(1)}$ time algorithm for constructing a short cycle decomposition, with cycles of length $n^{o(1)}$, and $n^{1+o(1)}$ extra edges. These decompositions enable us to make progress on several open questions: * We give an algorithm to find $(1\pm\epsilon)$-approximations to effective resistances of all edges in time $m^{1+o(1)}\epsilon^{-1.5}$, improving over the previous best of $\tilde{O}(\min\{m\epsilon^{-2},n^2 \epsilon^{-1}\})$. This gives an algorithm to approximate the determinant of a Laplacian up to $(1\pm\epsilon)$ in $m^{1 + o(1)} + n^{15/8+o(1)}\epsilon^{-7/4}$ time. * We show existence and efficient algorithms for constructing graphical spectral sketches -- a distribution over sparse graphs H such that for a Fixed Vector $x$, we have w.h.p. $x'L_Hx=(1\pm\epsilon)x'L_Gx$ and $x'L_H^+x=(1\pm\epsilon)x'L_G^+x$. This implies the existence of resistance-sparsifiers with about $n\epsilon^{-1}$ edges that preserve the effective resistances between every pair of vertices up to $(1\pm\epsilon).$ * By combining short cycle decompositions with known tools in graph sparsification, we show the existence of nearly-linear sized degree-preserving spectral sparsifiers, as well as significantly sparser approximations of directed graphs. The latter is critical to recent breakthroughs on faster algorithms for solving linear systems in directed Laplacians. Improved algorithms for constructing short cycle decompositions will lead to improvements for each of the above results.

Madeleine Schlag-rey - One of the best experts on this subject based on the ideXlab platform.

  • The frontal eye field provides the goal of saccadic eye movement.
    Experimental brain research, 1992
    Co-Authors: Paul Dassonville, John Schlag, Madeleine Schlag-rey
    Abstract:

    Microstimulation of oculomotor regions in primate cortex normally evokes saccadic eye movements of stereotypic directions and amplitudes. The Fixed-Vector nature of the evoked movements is compatible with the creation of either an artificial retinal or motor error signal. However, when microstimulation is applied during an ongoing natural saccade, the starting eye position of the evoked movement differs from the eye position at stimulation onset (due to the latency of the evoked saccade). An analysis of the effect of this eye position discrepancy on the trajectory of the eventual evoked saccade can clarify the oculomotor role of the structure stimulated. The colliding saccade paradigm of microstimulation was used in the present study to investigate the type of signals conveyed by visual, visuomovement, and movement unit activities in the primate frontal eye field. Colliding saccades elicited from all sites were found to compensate for the portion of the initial movement occurring between stimulation and evoked movement onset, plus a portion of the initial movement occurring before stimulation. This finding suggests that activity in the frontal eye field encodes a retinotopic goal that is converted by a downstream structure into the Vector of the eventual saccade.

Constantin Costara - One of the best experts on this subject based on the ideXlab platform.