Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userCan One Hear the Shape of a Graph?
232
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We show that the spectrum of the Schrodinger operator on a finite, metric graph determines uniquely the connectivity matrix and the bond lengths, provided that the lengths are non-commensurate and the connectivity is simple (no parallel bonds between vertices and no loops connecting a vertex to itself). That is, one can hear the shape of the graph! We also consider a related inversion problem: A compact graph can be converted into a scattering system by attaching to its vertices leads to infinity. We show that the scattering phase determines uniquely the compact part of the graph, under similar conditions as above.
rate research
Read More
Neural network applications have become popular in both enterprise and personal settings. Network solutions are tuned meticulously for each task, and designs that can robustly resolve queries end up in high demand. As the commercial value of accurate and performant machine learning models increases, so too does the demand to protect neural architectures as confidential investments. We explore the vulnerability of neural networks deployed as black boxes across accelerated hardware through electromagnetic side channels. We examine the magnetic flux emanating from a graphics processing units power cable, as acquired by a cheap $3 induction sensor, and find that this signal betrays the detailed topology and hyperparameters of a black-box neural network model. The attack acquires the magnetic signal for one query with unknown input values, but known input dimensions. The network reconstruction is possible due to the modular layer sequence in which deep neural networks are evaluated. We find that each layer components evaluation produces an identifiable magnetic signal signature, from which layer topology, width, function type, and sequence order can be inferred using a suitably trained classifier and a joint consistency optimization based on integer programming. We study the extent to which network specifications can be recovered, and consider metrics for comparing network similarity. We demonstrate the potential accuracy of this side channel attack in recovering the details for a broad range of network architectures, including random designs. We consider applications that may exploit this novel side channel exposure, such as adversarial transfer attacks. In response, we discuss countermeasures to protect against our method and other similar snooping techniques.
We study the question of whether it is possible to determine a finitely generated group $G$ up to some notion of equivalence from the spectrum $mathrm{sp}(G)$ of $G$. We show that the answer is No in a strong sense. As the first example we present the collection of amenable 4-generated groups $G_omega$, $omegain{0,1,2}^mathbb N$, constructed by the second author in 1984. We show that among them there is a continuum of pairwise non-quasi-isometric groups with $mathrm{sp}(G_omega)=[-tfrac{1}{2},0]cup[tfrac{1}{2},1]$. Moreover, for each of these groups $G_omega$ there is a continuum of covering groups $G$ with the same spectrum. As the second example we construct a continuum of $2$-generated torsion-free step-3 solvable groups with the spectrum $[-1,1]$. In addition, in relation to the above results we prove a version of Hulanicki Theorem about inclusion of spectra for covering graphs.
Traditionally, network analysis is based on local properties of vertices, like their degree or clustering, and their statistical behavior across the network in question. This paper develops an approach which is different in two respects. We investigate edge-based properties, and we define global characteristics of networks directly. The latter will provide our affirmative answer to the question raised in the title. More concretely, we start with Formans notion of the Ricci curvature of a graph, or more generally, a polyhedral complex. This will allow us to pass from a graph as representing a network to a polyhedral complex for instance by filling in triangles into connected triples of edges and to investigate the resulting effect on the curvature. This is insightful for two reasons: First, we can define a curvature flow in order to asymptotically simplify a network and reduce it to its essentials. Second, using a construction of Bloch, which yields a discrete Gauss-Bonnet theorem, we have the Euler characteristic of a network as a global characteristic. These two aspects beautifully merge in the sense that the asymptotic properties of the curvature flow are indicated by that Euler characteristic.
We give a complete characterization of the relationship between the shape of a Euclidean polygon and the symbolic dynamics of its billiard flow. We prove that the only pairs of tables that can have the same bounce spectrum are right-angled tables that differ by an affine map. The main tool is a new theorem that establishes that a flat cone metric is completely determined by the support of its Liouville current.
All physical systems are affected by some noise that limits the resolution that can be attained in partitioning their state space. For chaotic, locally hyperbolic flows, this resolution depends on the interplay of the local stretching/contraction and the smearing due to noise. We propose to determine the `finest attainable partition for a given hyperbolic dynamical system and a given weak additive white noise, by computing the local eigenfunctions of the adjoint Fokker-Planck operator along each periodic point, and using overlaps of their widths as the criterion for an optimal partition. The Fokker-Planck evolution is then represented by a finite transition graph, whose spectral determinant yields time averages of dynamical observables. Numerical tests of such `optimal partition of a one-dimensional repeller support our hypothesis.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
