skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.

Explore Research Products in the PAR
It may take a few hours for recently added research products to appear in PAR search results.


Title: Spectra of Random Regular Hypergraphs
In this paper, we study the spectra of regular hypergraphs following the definitions from Feng and Li (1996). Our main result is an analog of Alon's conjecture for the spectral gap of the random regular hypergraphs. We then relate the second eigenvalues to both its expansion property and the mixing rate of the non-backtracking random walk on regular hypergraphs. We also prove the spectral gap for the non-backtracking operator of a random regular hypergraph introduced in Angelini et al. (2015). Finally, we obtain the convergence of the empirical spectral distribution (ESD) for random regular hypergraphs in different regimes. Under certain conditions, we can show a local law for the ESD.  more » « less
Award ID(s):
1949617
PAR ID:
10294639
Author(s) / Creator(s):
;
Date Published:
Journal Name:
The Electronic Journal of Combinatorics
Volume:
28
Issue:
3
ISSN:
1077-8926
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. ; (, Random Matrices: Theory and Applications)
    We compute the eigenvalue fluctuations of uniformly distributed random biregular bipartite graphs with fixed and growing degrees for a large class of analytic functions. As a key step in the proof, we obtain a total variation distance bound for the Poisson approximation of the number of cycles and cyclically non-backtracking walks in random biregular bipartite graphs, which might be of independent interest. We also prove a semicircle law for random [Formula: see text]-biregular bipartite graphs when [Formula: see text]. As an application, we translate the results to adjacency matrices of uniformly distributed random regular hypergraphs. 
    more » « less
  2. ; (, Bernoulli)
    We develop a unified approach to bounding the largest and smallest singular values of an inhomogeneous random rectangular matrix, based on the non-backtracking operator and the Ihara-Bass formula for general random Hermitian matrices with a bipartite block structure. We obtain probabilistic upper (respectively, lower) bounds for the largest (respectively, smallest) singular values of a large rectangular random matrix X. These bounds are given in terms of the maximal and minimal 2-norms of the rows and columns of the variance profile of X. The proofs involve finding probabilistic upper bounds on the spectral radius of an associated non-backtracking matrix B. The two-sided bounds can be applied to the centered adjacency matrix of sparse inhomogeneous Erd˝os-Rényi bipartite graphs for a wide range of sparsity, down to criticality. In particular, for Erd˝os-Rényi bipartite graphs G(n,m, p) with p = ω(log n)/n, and m/n→ y ∈ (0,1), our sharp bounds imply that there are no outliers outside the support of the Marˇcenko-Pastur law almost surely. This result extends the Bai-Yin theorem to sparse rectangular random matrices. 
    more » « less
  3. ; ; ; (, Proc. IEEE Electron Devices Technology and Manufacturing Conference (EDTM))
    CDM ESD protection is a major ESD protection design challenge for advanced ICs, often suffering from random design failures. It was recently reported that the traditional pad-based CDM ESD protection method is fundamentally faulty, contributing to design uncertainties in CDM ESD testing and field failures. This paper reports a novel internally distributed CDM ESD protection method to overcome this major design challenge, which was validated using an internal-CDM-protected oscillator IC implemented in a foundry 45nm SOI CMOS technology. ESD protection is required for all systems. 
    more » « less
  4. ; ; (, Springer Nature Singapore)
    The spectral properties of traditional (dyadic) graphs, where an edge connects exactly two vertices, are widely studied in different applications. These spectral properties are closely connected to the structural properties of dyadic graphs. We generalize such connections and characterize higher-order networks by their spectral information. We first split the higher-order graphs by their “edge orders” into several uniform hypergraphs. For each uniform hypergraph, we extract the corresponding spectral information from the transition matrices of carefully designed random walks. From each spectrum, we compute the first few spectral moments and use all such spectral moments across different “edge orders” as the higher-order graph representation. We show that these moments not only clearly indicate the return probabilities of random walks but are also closely related to various higher-order network properties such as degree distribution and clustering coefficient. Extensive experiments show the utility of this new representation in various settings. For instance, graph classification on higher-order graphs shows that this representation significantly outperforms other techniques. 
    more » « less
  5. (, Proceedings of the USENIX conference)
    Regular expressions (regexps) are a convenient way for programmers to express complex string searching logic. Sev- eral popular programming languages expose an interface to a regexp matching subsystem, either by language-level primi- tives or through standard libraries. The implementations be- hind these matching systems vary greatly in their capabilities and running-time characteristics. In particular, backtracking matchers may exhibit worst-case running-time that is either linear, polynomial, or exponential in the length of the string being searched. Such super-linear worst-case regexps expose applications to Regular Expression Denial-of-Service (Re- DoS) when inputs can be controlled by an adversarial attacker. In this work, we investigate the impact of ReDoS in back- tracking engines, a popular type of engine used by most programming languages. We evaluate several existing tools against a dataset of broadly collected regexps, and find that despite extensive theoretical work in this field, none are able to achieve both high precision and high recall. To address this gap in existing work, we develop REGULATOR, a novel dy- namic, fuzzer-based analysis system for identifying regexps vulnerable to ReDoS. We implement this system by directly instrumenting a popular backtracking regexp engine, which increases the scope of supported regexp syntax and features over prior work. Finally, we evaluate this system against three common regexp datasets, and demonstrate a seven-fold in- crease in true positives discovered when comparing against existing tools. 
    more » « less
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Save / Share this Record
  • Send to Email