About

Venkat Anantharam is a professor affiliated with the Electrical Engineering and Computer Sciences department at the University of California, Berkeley. His professional contact information includes an office located at 271 Cory Hall and a phone number (510) 643-8435. His email address is ananth@eecs.berkeley.edu. While his research interests are currently under construction on his webpage, his extensive publication record and supervision of numerous doctoral and master's students indicate a deep engagement with topics in information theory, stochastic processes, game theory, and network information theory. He has supervised a significant number of doctoral and master's students and hosted several postdoctoral fellows, reflecting his active role in mentoring emerging researchers. His work includes contributions to the understanding of Nash equilibria, entropy in stochastic processes, compression of graphical data, and the geometry of information-theoretic problems. He has published in prestigious journals such as IEEE Transactions on Information Theory and has presented at major conferences, demonstrating a strong presence in the academic community. His research spans theoretical and applied aspects of information theory, probability, and optimization, with a focus on problems involving communication channels, data compression, and game-theoretic models.

Research topics

• Computer Science
• Mathematics
• Statistics
• Pure mathematics
• Theoretical computer science
• Algorithm
• Discrete mathematics
• Applied mathematics

Selected publications

• An Information-theoretic Analysis of Edge-reinforced Random Walks

  arXiv (Cornell University) · 2026-05-21

  preprintOpen accessSenior author

  Reinforced random walks are random walks on graphs whose transition probabilities along edges from a vertex are proportional to the weights of those edges, but where the weight of an edge evolves in a way that depends on the past traversals across it. In an edge-reinforced random walk (ERRW), the weight of an edge increases by $1$ whenever that edge is traversed, in either direction. On a finite graph, an ERRW admits a remarkable representation as a random walk in a random environment. The law of the environment is given by the so-called {\em magic formula}, with this law depending on the initial edge weights. This representation provides a natural route for studying statistical properties of ERRWs. This work focuses on various information-theoretic quantities associated with ERRWs on finite graphs, motivated in part by the problem of statistically distinguishing between different ERRW models from observed trajectories. In particular, we study the entropy rate of an ERRW. We also study the Kullback--Leibler divergence (KL divergence) between two ERRW environment laws, and the KL divergence between the corresponding finite-trajectory distributions. Leveraging structural properties of the underlying random environment, we derive an annealed representation of the entropy rate, a closed-form formula for the environment-level KL divergence, and quantitative bounds on the convergence of trajectory-level KL divergence toward environment-level KL divergence. These information-theoretic quantities are motivated by the two-point hypothesis testing problem for ERRW trajectories, and in particular by the associated Stein exponent. We also expect them to play a fundamental role in the study of other testing problems for ERRWs, including identity testing and closeness testing.

  PublisherDOI

• An Information-theoretic Analysis of Edge-reinforced Random Walks

  ArXiv.org · 2026-05-21

  articleOpen accessSenior author

  Reinforced random walks are random walks on graphs whose transition probabilities along edges from a vertex are proportional to the weights of those edges, but where the weight of an edge evolves in a way that depends on the past traversals across it. In an edge-reinforced random walk (ERRW), the weight of an edge increases by $1$ whenever that edge is traversed, in either direction. On a finite graph, an ERRW admits a remarkable representation as a random walk in a random environment. The law of the environment is given by the so-called {\em magic formula}, with this law depending on the initial edge weights. This representation provides a natural route for studying statistical properties of ERRWs. This work focuses on various information-theoretic quantities associated with ERRWs on finite graphs, motivated in part by the problem of statistically distinguishing between different ERRW models from observed trajectories. In particular, we study the entropy rate of an ERRW. We also study the Kullback--Leibler divergence (KL divergence) between two ERRW environment laws, and the KL divergence between the corresponding finite-trajectory distributions. Leveraging structural properties of the underlying random environment, we derive an annealed representation of the entropy rate, a closed-form formula for the environment-level KL divergence, and quantitative bounds on the convergence of trajectory-level KL divergence toward environment-level KL divergence. These information-theoretic quantities are motivated by the two-point hypothesis testing problem for ERRW trajectories, and in particular by the associated Stein exponent. We also expect them to play a fundamental role in the study of other testing problems for ERRWs, including identity testing and closeness testing.

  PublisherOA PDF

• The Density Formula Approach for Non-Reversible Isomorphism Theorems, with Applications

  2025-06-22 · 1 citations

  articleSenior author
  PublisherDOI

• Quantum advantage in decentralized control of POMDPs: A control-theoretic view of the Mermin-Peres square

  ArXiv.org · 2025-01-28

  preprintOpen access1st authorCorresponding

  Consider a decentralized partially-observed Markov decision problem (POMDP) with multiple cooperative agents aiming to maximize a long-term-average reward criterion. We observe that the availability, at a fixed rate, of entangled states of a product quantum system between the agents, where each agent has access to one of the component systems, can result in strictly improved performance even compared to the scenario where common randomness is provided to the agents, i.e. there is a quantum advantage in decentralized control. This observation comes from a simple reinterpretation of the conclusions of the well-known Mermin-Peres square, which underpins the Mermin-Peres game. While quantum advantage has been demonstrated earlier in one-shot team problems of this kind, it is notable that there are examples where there is a quantum advantage for the one-shot criterion but it disappears in the dynamical scenario. The presence of a quantum advantage in dynamical scenarios is thus seen to be a novel finding relative to the current state of knowledge about the achievable performance in decentralized control problems. This paper is dedicated to the memory of Pravin P. Varaiya.

  PublisherOA PDFDOI

• On Statistical Estimation of Edge-Reinforced Random Walks

  2025-06-22 · 1 citations

  articleSenior author

  Reinforced random walks (RRWs), including vertex-reinforced random walks (VRRWs) and edge-reinforced reinforced random walks (ERRWs), model phenomena where transition probabilities evolve based on prior visitation history [5], [8], [15], [16]. These models have found applications in various areas, such as network embedding [18], reinforced PageRank [6], and modeling animal behaviors [14], among others. However, statistical estimation of the parameters governing RRWs remains underexplored. This work focuses on estimating the initial edge weights of ERRWs using observed trajectory data. Leveraging the connections between ERRW and random walks in a random environment (RWRE) [9], [10], we propose an estimator based on the generalized method of moments and the “magic formula”. To analyze the sample complexity, we exploit the hyperbolic Gaussian structure embedded in the random environment to bound the order of the random conductance, and hence derive sample complexity bounds. These findings contribute to the theoretical foundation of promising statistical and algorithmic applications of ERRWs.

  PublisherDOI

• Graphs of Joint Types, Noninteractive Simulation, and Stronger Hypercontractivity

  IEEE Transactions on Information Theory · 2024-01-24 · 1 citations

  article

  In this paper, we study the type graph, namely, a bipartite graph induced by a joint type. We investigate the maximum edge density of induced bipartite subgraphs of this graph having a number of vertices on each side on an exponential scale in the length <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$n$ </tex-math></inline-formula> of the type. This can be seen as an isoperimetric problem. We provide asymptotically sharp bounds for the exponent of the maximum edge density as the length of the type goes to infinity. We also study the biclique rate region of the type graph, which is defined as the set of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$(R_{1},R_{2})$ </tex-math></inline-formula> such that there exists a biclique of the type graph which has respectively <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$2^{nR_{1}}$ </tex-math></inline-formula> and <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$2^{nR_{2}}$ </tex-math></inline-formula> vertices on the two sides. We provide asymptotically sharp bounds for the biclique rate region as well. We then discuss the connections of these results to noninteractive simulation and hypercontractivity inequalities. Furthermore, as an application of our results, a new outer bound for the zero-error capacity region of the binary adder channel is provided, which improves the previously best known bound, due to Austrin, Kaski, Koivisto, and Nederlof. Our proofs in this paper are based on the method of types and linear algebra.

  PublisherDOI

• An Information-Theoretic Proof of the Shannon-Hagelbarger Theorem

  2024-07-07

  article1st authorCorresponding

  The Shannon-Hagelbarger theorem states that the effective resistance across any pair of nodes in a resistive network is a concave function of the edge resistances. We give an information-theoretic proof of this result, building on the theory of the Gaussian free field. This also allows us to prove an extension of the result to determinants of matrices of cross effective resistances.

  PublisherDOI

• An information-theoretic proof of the Shannon-Hagelbarger theorem

  arXiv (Cornell University) · 2023-12-18

  preprintOpen access1st authorCorresponding

  The Shannon-Hagelbarger theorem states that the effective resistance across any pair of nodes in a resistive network is a concave function of the edge resistances. We give an information-theoretic proof of this result, building on the theory of the Gaussian free field. This also allows us to prove an extension of the result to determinants of matrices of cross effective resistances.

  PublisherOA PDFDOI

• A Universal Low Complexity Compression Algorithm for Sparse Marked Graphs

  arXiv (Cornell University) · 2023-01-13

  preprintOpen accessSenior author

  Many modern applications involve accessing and processing graphical data, i.e. data that is naturally indexed by graphs. Examples come from internet graphs, social networks, genomics and proteomics, and other sources. The typically large size of such data motivates seeking efficient ways for its compression and decompression. The current compression methods are usually tailored to specific models, or do not provide theoretical guarantees. In this paper, we introduce a low-complexity lossless compression algorithm for sparse marked graphs, i.e. graphical data indexed by sparse graphs, which is capable of universally achieving the optimal compression rate in a precisely defined sense. In order to define universality, we employ the framework of local weak convergence, which allows one to make sense of a notion of stochastic processes for sparse graphs. Moreover, we investigate the performance of our algorithm through some experimental results on both synthetic and real-world data.

  PublisherOA PDFDOI

• A Universal Low Complexity Compression Algorithm for Sparse Marked Graphs

  IEEE Journal on Selected Areas in Information Theory · 2022-12-01 · 1 citations

  articleOpen accessSenior author

  Many modern applications involve accessing and processing graphical data, i.e. data that is naturally indexed by graphs. Examples come from internet graphs, social networks, genomics and proteomics, and other sources. The typically large size of such data motivates seeking efficient ways for its compression and decompression. The current compression methods are usually tailored to specific models, or do not provide theoretical guarantees. In this paper, we introduce a low-complexity lossless compression algorithm for sparse marked graphs, i.e. graphical data indexed by sparse graphs, which is capable of universally achieving the optimal compression rate defined on a per-node basis. The time and memory complexities of our compression and decompression algorithms are optimal within logarithmic factors. In order to define universality we employ the framework of local weak convergence, which allows one to make sense of a notion of stochastic processes for sparse graphs. Moreover, we investigate the performance of our algorithm through some experimental results on both synthetic and real-world data.

  PublisherOA PDFDOI

Recent grants

• Presidential Young Investigator Award (Computer Research)

  NSF · $291k · 1988–1995

• New Techniques for the Control of Multi-Agent Systems in Uncertain Environments

  NSF · $305k · 2005–2009

• CIF: Small: Poisson matching: A new tool for information theory

  NSF · $500k · 2020–2026

• NeTS: Small: PTERA: Prospect Theory Enhanced Resource Allocation

  NSF · $500k · 2015–2020

• Theory and Methodology for the Design and Evaluation of High-Performance LDPC Codes

  NSF · $672k · 2006–2010

Frequent coauthors

• Amin Gohari

  Chinese University of Hong Kong

  29 shared

• Varun Jog

  University of Cambridge

  18 shared

• Payam Delgosha

  University of Illinois Urbana-Champaign

  18 shared

• Takis Konstantopoulos

  Uppsala University

  13 shared

• Chandra Nair

  Chinese University of Hong Kong

  11 shared

• Soham R. Phade

  11 shared

• Jean Walrand

  10 shared

• François Baccelli

  École Normale Supérieure - PSL

  10 shared

Labs

• CLIMBPI

  Center for the Theoretical Foundations of Learning, Inference, Information, Intelligence, Mathematics and Microeconomics at Berkeley

Education

• Ph.D., Electrical Engineering and Computer Sciences

  University of California, Berkeley

  1990

• M.S., Electrical Engineering and Computer Sciences

  University of California, Berkeley

  1986

• B.S., Electrical Engineering

  Indian Institute of Technology, Madras

  1984

Awards & honors

• IEEE Information Theory Society Paper Award (1998)
• IEEE ComSoc Stephen O. Rice Prize (2000)
• IEEE Trans. on Communications (Stephen O. Rice Prize Paper A…
• IEEE Trans. Information Theory (Bits through queues) (1996)
• IEEE Trans. Automatic Control (Asymptotically efficient adap…