Search

Expansion property of a graph refers to its strong connectivity as well as sparseness. It has been reported that deep neural networks can be pruned to a high degree of sparsity while maintaining their performance. Such pruning is essential for performing real time sequence learning tasks using recurrent neural networks in resource constrained platforms. We prune recurrent networks such as RNNs and LSTMs, maintaining a large spectral gap of the underlying graphs and ensuring their layerwise expansion properties. We also study the time unfolded recurrent network graphs in terms of the properties of their bipartite layers. Experimental results for the benchmark sequence MNIST, CIFAR-10, and Google speech command data show that expander graph properties are key to preserving classification accuracy of RNN and LSTM., Comment: Accepted as tiny paper in ICLR 2024

In this paper, we devise a scheme for kernelizing, in sublinear space and polynomial time, various problems on planar graphs. The scheme exploits planarity to ensure that the resulting algorithms run in polynomial time and use O((sqrt(n) + k) log n) bits of space, where n is the number of vertices in the input instance and k is the intended solution size. As examples, we apply the scheme to Dominating Set and Vertex Cover. For Dominating Set, we also show that a well-known kernelization algorithm due to Alber et al. (JACM 2004) can be carried out in polynomial time and space O(k log n). Along the way, we devise restricted-memory procedures for computing region decompositions and approximating the aforementioned problems, which might be of independent interest.

In this article, we study the game of cops and robbers in algebraic graphs. We show that the cop number of the Cayley sum graph of a finite group $G$ with respect to a subset $S$ is at most its degree when the graph is connected, undirected. We also show that a similar bound holds for the cop number of generalised Cayley graphs and the twisted Cayley sum graphs under some conditions. These extend a result of Frankl to such graphs. Using the above bounds and a result of Bollob\'{a}s--Janson--Riordan, we show that the weak Meyniel's conjecture holds for these algebraic graphs.

We prove algorithmic results showing that a number of natural parameterized problems are in the restricted-space parameterized classes Para-L and FPT+XL. The first class comprises problems solvable in f(k) n^{O(1)} time using g(k) + O(log n)) bits of space (k is the parameter and n is the input size; f and g are computable functions). The second class comprises problems solvable under the same time bound, but using g(k) log n bits of space instead. Earlier work on these classes has focused largely on their structural aspects and their relationships with various other classes. We complement this with Para-L and FPT+XL algorithms for a restriction of Hitting Set, some graph deletion problems where the target class has an infinite forbidden set characterization, a number of problems parameterized by vertex cover number, and Feedback Vertex Set.

In the Max $r$-SAT problem, the input is a CNF formula with $n$ variables where each clause is a disjunction of at most $r$ literals. The objective is to compute an assignment which satisfies as many of the clauses as possible. While there are a large number of polynomial-time approximation algorithms for this problem, we take the viewpoint of space complexity following [Biswas et al., Algorithmica 2021] and design sublinear-space approximation algorithms for the problem. We show that the classical algorithm of [Lieberherr and Specker, JACM 1981] can be implemented to run in $n^{O(1)}$ time while using $(\log{n})$ bits of space. The more advanced algorithms use linear or semi-definite programming, and seem harder to carry out in sublinear space. We show that a more recent algorithm with approximation ratio $\sqrt{2}/2$ [Chou et al., FOCS 2020], designed for the streaming model, can be implemented to run in time $n^{O(r)}$ using $O(r \log{n})$ bits of space. While known streaming algorithms for the problem approximate optimum values and use randomization, our algorithms are deterministic and can output the approximately optimal assignments in sublinear space. For instances of Max $r$-SAT with planar incidence graphs, we devise a factor-$(1 - \epsilon)$ approximation scheme which computes assignments in time $n^{O(r / \epsilon)}$ and uses $\max\{\sqrt{n} \log{n}, (r / \epsilon) \log^2{n}\}$ bits of space.

For any finite, undirected, non-bipartite, vertex-transitive graph, we establish an explicit lower bound for the smallest eigenvalue of its normalised adjacency operator, which depends on the graph only through its degree and its isoperimetric constant.

The Cayley graphs of finite groups are known to provide several examples of families of expanders, and some of them are Ramanujan graphs. Babai studied isospectral non-isomorphic Cayley graphs of the dihedral groups. Lubotzky, Samuels and Vishne proved that there are isospectral non-isomorphic Cayley graphs of $\mathrm{PSL}_d(\mathbb F_q)$ for every $d\geq 5$ ($d \neq 6$) and prime power $q> 2$. In this article, we focus on three variants of Cayley graphs, viz., the Cayley sum graphs, the twisted Cayley graphs, and the twisted Cayley sum graphs. We prove the existence of non-isomorphic expander families of bounded degree, whose spectra are related by the values of certain characters. We also provide several new examples of expander families, and examples of non-expanders and Ramanujan graphs formed by these three variants.

Jambor--Liebeck--O'Brien showed that there exist non-proper-power word maps which are not surjective on $\mathrm{PSL}_{2}(\mathbb{F}_{q})$ for infinitely many $q$. This provided the first counterexamples to a conjecture of Shalev which stated that if a two-variable word is not a proper power of a non-trivial word, then the corresponding word map is surjective on $\mathrm{PSL}_2(\mathbb{F}_{q})$ for all sufficiently large $q$. Motivated by their work, we construct new examples of these types of non-surjective word maps. As an application, we obtain non-surjective word maps on the absolute Galois group of $\mathbb Q$.

Let $G$ be a finite group with $|G|\geq 4$ and $S$ be a subset of $G$. Given an automorphism $\sigma$ of $G$, the twisted Cayley graph $C(G, S)^\sigma$ (resp. the twisted Cayley sum graph $C_\Sigma(G, S)^\sigma$) is defined as the graph having $G$ as its set of vertices and the adjacent vertices of a vertex $g\in G$ are of the form $\sigma(gs)$ (resp. $\sigma(g^{-1} s)$) for some $s\in S$. If the twisted Cayley graph $C(G, S)^\sigma$ is undirected and connected, then we prove that the nontrivial spectrum of its normalised adjacency operator is bounded away from $-1$ and this bound depends only on its degree, the order of $\sigma$ and the vertex Cheeger constant of $C(G, S)^\sigma$. Moreover, if the twisted Cayley sum graph $C_\Sigma(G, S)^\sigma$ is undirected and connected, then we prove that the nontrivial spectrum of its normalised adjacency operator is bounded away from $-1$ and this bound depends only on its degree and the vertex Cheeger constant of $C_\Sigma(G, S)^\sigma$. We also study these twisted graphs with respect to anti-automorphisms, and obtain similar results. Further, we prove an analogous result for the Schreier graphs satisfying certain conditions.

We develop new approximation algorithms for classical graph and set problems in the RAM model under space constraints. As one of our main results, we devise an algorithm for d-Hitting Set that runs in time n^{O(d^2 + d/\epsilon})}, uses O((d^2 + d/\epsilon) log n) bits of space, and achieves an approximation ratio of O((d/{\epsilon}) n^{\epsilon}) for any positive \epsilon \leq 1 and any natural number d. In particular, this yields a factor-O(log n) approximation algorithm which runs in time n^{O(log n)} and uses O(log^2 n) bits of space (for constant d). As a corollary, we obtain similar bounds for Vertex Cover and several graph deletion problems. For bounded-multiplicity problem instances, one can do better. We devise a factor-2 approximation algorithm for Vertex Cover on graphs with maximum degree \Delta, and an algorithm for computing maximal independent sets which both run in time n^{O(\Delta)} and use O(\Delta log n) bits of space. For the more general d-Hitting Set problem, we devise a factor-d approximation algorithm which runs in time n^{O(d {\delta}^2)} and uses O(d {\delta}^2 log n) bits of space on set families where each element appears in at most \delta sets. For Independent Set restricted to graphs with average degree d, we give a factor-(2d) approximation algorithm which runs in polynomial time and uses O(log n) bits of space. We also devise a factor-O(d^2) approximation algorithm for Dominating Set on d-degenerate graphs which runs in time n^{O(log n)} and uses O(log^2 n) bits of space. For d-regular graphs, we show how a known randomized factor-O(log d) approximation algorithm can be derandomized to run in time n^{O(1)} and use O(log n) bits of space. Our results use a combination of ideas from the theory of kernelization, distributed algorithms and randomized algorithms., Comment: MFCS 2020

The notion of minimal complements was introduced by Nathanson in 2011 as a natural group-theoretic analogue of the metric concept of nets. Given two non-empty subsets $W,W'$ in a group $G$, the set $W'$ is said to be a complement to $W$ if $W\cdot W'=G$ and it is minimal if no proper subset of $W'$ is a complement to $W$. The inverse problem asks which sets may or not occur as minimal complements. We show some new results on the inverse problem and investigate how the study of the inverse problem naturally gives rise to questions about the asymptotic behaviour of these sets, providing partial answers to some of them.

The notion of minimal complements was introduced by Nathanson in 2011. Since then, the existence or the inexistence of minimal complements of sets have been extensively studied. Recently, the study of inverse problems, i.e., which sets can or cannot occur as minimal complements has gained traction. For example, the works of Kwon, Alon--Kravitz--Larson, Burcroff--Luntzlara and also that of the authors, shed light on some of the questions in this direction. These works have focussed mainly on the group of integers, or on abelian groups. In this work, our motivation is two-fold: (i) to show some new results on the inverse problem, (ii) to concentrate on the inverse problem in not necessarily abelian groups. As a by-product, we obtain new results on non-minimal complements in the group of integers and more generally, in any finitely generated abelian group of positive rank and in any free abelian group of positive rank. Moreover, we show the existence of uncountably many subsets in such groups which are "robust" non-minimal complements.