VSVenkatesh Srinivasan

Venkatesh Srinivasan

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article


Venkatesh Srinivasan has a total of 26 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Scalable probabilistic truss decomposition using central limit theorem and H-index

    by Fatemeh Esfahani, Mahsa Daneshmand, Venkatesh Srinivasan, Alex Thomo, Kui Wu

    Truss decomposition is a popular notion of hierarchical dense substructures in graphs. In a nutshell, k-truss is the largest subgraph in which every edge is contained in at least k triangles. Truss decomposition aims to compute k-trusses for each possible value of k. There are many works that study truss decomposition in deterministic graphs. However, in probabilistic graphs, truss decomposition is significantly more challenging and has received much less attention; state-of-the-art approaches do not scale well to large probabilistic graphs. Finding the tail probabilities of the number of triangles that contain each edge is a critical challenge of those approaches. This is achieved using dynamic programming which has quadratic run-time and thus not scalable to real large networks which, quite commonly, can have edges contained in many triangles (in the millions). To address this challenge, we employ a special version of the Central Limit Theorem (CLT) to obtain the tail probabilities efficiently. Based on our CLT approach we propose a peeling algorithm for truss decomposition that scales to large probabilistic graphs and offers significant improvement over state-of-the-art. We also design a second method which progressively tightens the estimate of the truss value of each edge and is based on h-index computation. In contrast to our CLT-based approach, our h-index algorithm (1) is progressive by allowing the user to see near-results along the way, (2) does not sacrifice the exactness of final result, and (3) achieves all these while processing only one edge and its immediate neighbors at a time, thus resulting in smaller memory footprint. We perform extensive experiments to show the scalability of both of our proposed algorithms.


  • Open Access

    Authentication of variable length messages in quantum key distribution

    by Khodakhast Bibak, Bruce M. Kapron, Venkatesh Srinivasan

    Authentication plays a critical role in the security of quantum key distribution (QKD) protocols. We propose using Polynomial Hash and its variants for authentication of variable length messages in QKD protocols. Since universal hashing is used not only for authentication in QKD but also in other steps in QKD like error correction and privacy amplification, and also in several other areas of quantum cryptography, Polynomial Hash and its variants as the most efficient universal hash function families can be used in these important steps and areas, as well. We introduce and analyze several efficient variants of Polynomial Hash and, using deep results from number theory, prove that each variant gives an ε-almost-Δ-universal family of hash functions. We also give a general method for transforming any such family to an ε-almost-strongly universal family of hash functions. The latter families can then, among other applications, be used in the Wegman–Carter MAC construction which has been shown to provide a universally composable authentication method in QKD protocols. As Polynomial Hash has found many applications, our constructions and results are potentially of interest in various areas.


  • Open Access

    MMH* with arbitrary modulus is always almost-universal

    by Khodakhast Bibak, Bruce M. Kapron, Venkatesh Srinivasan

    Universal hash functions, discovered by Carter and Wegman in 1979, are of great importance in computer science with many applications. MMH$^*$ is a well-known $\triangle$-universal hash function family, based on the evaluation of a dot product modulo a prime. In this paper, we introduce a generalization of MMH$^*$, that we call GMMH$^*$, using the same construction as MMH$^*$ but with an arbitrary integer modulus $n>1$, and show that GMMH$^*$ is $\frac{1}{p}$-almost-$\triangle$-universal, where $p$ is the smallest prime divisor of $n$. This bound is tight.

  • Open Access

    Unweighted linear congruences with distinct coordinates and the Varshamov--Tenengolts codes

    by Khodakhast Bibak, Bruce M. Kapron, Venkatesh Srinivasan

    In this paper, we first give explicit formulas for the number of solutions of unweighted linear congruences with distinct coordinates. Our main tools are properties of Ramanujan sums and of the discrete Fourier transform of arithmetic functions. Then, as an application, we derive an explicit formula for the number of codewords in the Varshamov--Tenengolts code $VT_b(n)$ with Hamming weight $k$, that is, with exactly $k$ $1$'s. The Varshamov--Tenengolts codes are an important class of codes that are capable of correcting asymmetric errors on a $Z$-channel. As another application, we derive Ginzburg's formula for the number of codewords in $VT_b(n)$, that is, $|VT_b(n)|$. We even go further and discuss connections to several other combinatorial problems, some of which have appeared in seemingly unrelated contexts. This provides a general framework and gives new insight into all these problems which might lead to further work.

  • A generalization of Schönemann’s theorem via a graph theoretic method

    by Khodakhast Bibak, Bruce M. Kapron, Venkatesh Srinivasan


  • Open Access

    A generalization of Schönemann's theorem via a graph theoretic method

    by Khodakhast Bibak, Bruce M. Kapron, Venkatesh Srinivasan

    Recently, Grynkiewicz et al. [{\it Israel J. Math.} {\bf 193} (2013), 359--398], using tools from additive combinatorics and group theory, proved necessary and sufficient conditions under which the linear congruence $a_1x_1+\cdots +a_kx_k\equiv b \pmod{n}$, where $a_1,\ldots,a_k,b,n$ ($n\geq 1$) are arbitrary integers, has a solution $\langle x_1,\ldots,x_k \rangle \in \Z_{n}^k$ with all $x_i$ distinct. So, it would be an interesting problem to give an explicit formula for the number of such solutions. Quite surprisingly, this problem was first considered, in a special case, by Sch\"{o}nemann almost two centuries ago(!) but his result seems to have been forgotten. Sch\"{o}nemann [{\it J. Reine Angew. Math.} {\bf 1839} (1839), 231--243] proved an explicit formula for the number of such solutions when $b=0$, $n=p$ a prime, and $\sum_{i=1}^k a_i \equiv 0 \pmod{p}$ but $\sum_{i \in I} a_i \not\equiv 0 \pmod{p}$ for all $\emptyset \not= I\varsubsetneq \lbrace 1, \ldots, k\rbrace$. In this paper, we generalize Sch\"{o}nemann's theorem using a result on the number of solutions of linear congruences due to D. N. Lehmer and also a result on graph enumeration. This seems to be a rather uncommon method in the area; besides, our proof technique or its modifications may be useful for dealing with other cases of this problem (or even the general case) or other relevant problems.