Spectral algorithms are some of the main tools in optimization and inference problems on graphs. Typically, the graph is encoded as a matrix and eigenvectors and eigenvalues of the matrix are then used to solve the given graph problem. Spectral algorithms ...
We examine the connection of two graph parameters, the size of a minimum feedback arcs set and the acyclic disconnection. A feedback arc set of a directed graph is a subset of arcs such that after deletion the graph becomes acyclic. The acyclic disconnecti ...
We prove the non-planarity of a family of 3-regular graphs constructed from the solutions to the Markoff equation x2 + y2 + z2 = xyz modulo prime numbers greater than 7. The proof uses Euler characteristic and an enumeration of the short cycles in these gr ...
Orthogonal group synchronization is the problem of estimating n elements Z(1),& mldr;,Z(n) from the rxr orthogonal group given some relative measurements R-ij approximate to Z(i)Z(j)(-1). The least-squares formulation is nonconvex. To avoid its local minim ...
This thesis presents a comprehensive theory of information-theoretic measures for characterizing the complexity and higher-order dependence structures of graphs. We introduce multivariate complexity and dependence measures for graphs within the framework o ...
In this paper, we propose a novel approach that employs kinetic equations to describe the collective dynamics emerging from graph-mediated pairwise interactions in multi-agent systems. We formally show that for large graphs and specific classes of interact ...
We discuss two extensions to a recently introduced theory of arrays, which are based on considerations coming from the model theory of power structures. First, we discuss how the ordering relation on the index set can be expressed succinctly by referring t ...
Technology mapping transforms a technology-independent representation into a technology-dependent one given a library of cells. This process is performed by means of local replacements that are extracted by matching sections of the subject graph to library ...
The rapidly evolving field of inorganic solid-state electrolytes (ISSEs) has been driven in recent years by advances in data-mining techniques, which facilitates the high-throughput computational screening for candidate materials in the databases. The key ...
Let F be a family of n pairwise intersecting circles in the plane. We show that the number of lenses, that is convex digons, in the arrangement induced by F is at most 2n - 2. This bound is tight. Furthermore, if no two circles in F touch, then the geometr ...
Modern integrated circuits are tiny yet incredibly complex technological artifacts, composed of millions and billions of individual structures working in unison.
Managing their complexity and facilitating their design drove part of the co-evolution of mode ...
We consider the community detection problem in a sparse q-uniform hypergraph G, assuming that G is generated according to the Hypergraph Stochastic Block Model (HSBM). We prove that a spectral method based on the non-backtracking operator for hypergraphs w ...
An integer linear program is a problem of the form max{c^T x : Ax=b, x >= 0, x integer}, where A is in Z^(n x m), b in Z^m, and c in Z^n.
Solving an integer linear program is NP-hard in general, but there are several assumptions for which it becomes fixed ...
When can a unimodular random planar graph be drawn in the Euclidean or the hyperbolic plane in a way that the distribution of the random drawing is isometry-invariant? This question was answered for one-ended unimodular graphs in Benjamini and Timar, using ...
Graph machine learning offers a powerful framework with natural applications in scientific fields such as chemistry, biology and material sciences.
By representing data as a graph, we encode the prior knowledge that the data is composed of a set of entiti ...
In this thesis, we give new approximation algorithms for some NP-hard problems arising in resource allocation and network design. As a resource allocation problem, we study the Santa Claus problem (also known as the MaxMin Fair Allocation problem) in which ...
A graph H is a minor of a second graph G if G can be transformed into H by two operations: 1) deleting nodes and/or edges, or 2) contracting edges. Coarse-grained reconfigurable array (CGRA) application mapping is closely related to the graph minor problem ...
Maximal subgraph mining is increasingly important in various domains, including bioinformatics, genomics, and chemistry, as it helps identify common characteristics among a set of graphs and enables their classification into different categories. Existing ...
Natural microbial populations often have complex spatial structures. This can impact their evolution, in particular the ability of mutants to take over. While mutant fixation probabilities are known to be unaffected by sufficiently symmetric structures, ev ...
Various forms of real-world data, such as social, financial, and biological networks, can be
represented using graphs. An efficient method of analysing this type of data is to extract
subgraph patterns, such as cliques, cycles, and motifs, from graphs. For ...
