Venkata Gandikota
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Venkata Gandikota has a total of 9 co-authors. Here are the top co-authors by number of shared publications:
- Arya Mazumdar
Halicioglu Data Science Institute University of California San Diego
2 shared publications Ankit Singh Rawat
Google Research NY, New York City, NY, USA
1 shared publicationDaniel Kane
Departments of Computer Science and Mathematics, UC San Diego, La Jolla, CA, USA
1 shared publication- Elena Grigorescu
University of Waterloo, Waterloo, Canada
1 shared publication - Jeremiah Blocki
Purdue University, West Lafayette, Indiana, USA
1 shared publication - Pramod K. Varshney
Department of Electrical Engineering and Computer Science, Syracuse University, Syracuse, NY, USA
1 shared publication
Latest Publications
- 29 January 2025
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 71 (4) , 2888-2908
Robust Distributed Clustering With Redundant Data Assignment
In this work, we present distributed clustering algorithms that can handle large-scale data across multiple machines in the presence of faulty machines. These faulty machines can either be straggling machines that fail to respond within a stipulated time or Byzantines that send arbitrary responses. We propose redundant data assignment schemes that enable us to obtain clustering solutions based on the entire dataset, even when some machines are stragglers or adversarial in nature. Our proposed robust clustering algorithms generate a constant factor approximate solution in the presence of stragglers or Byzantines. We also provide various constructions of the data assignment scheme that provide resilience against a large fraction of faulty machines. Simulation results show that the distributed algorithms based on the proposed assignment scheme provide good-quality solutions for a variety of clustering problems.
- 29 January 2025
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 71 (4) , 2888-2908
Robust Distributed Clustering With Redundant Data Assignment
In this work, we present distributed clustering algorithms that can handle large-scale data across multiple machines in the presence of faulty machines. These faulty machines can either be straggling machines that fail to respond within a stipulated time or Byzantines that send arbitrary responses. We propose redundant data assignment schemes that enable us to obtain clustering solutions based on the entire dataset, even when some machines are stragglers or adversarial in nature. Our proposed robust clustering algorithms generate a constant factor approximate solution in the presence of stragglers or Byzantines. We also provide various constructions of the data assignment scheme that provide resilience against a large fraction of faulty machines. Simulation results show that the distributed algorithms based on the proposed assignment scheme provide good-quality solutions for a variety of clustering problems.
- 23 March 2022
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 68 (7) , 4573-4587
vqSGD: Vector Quantized Stochastic Gradient Descent
In this work, we present a family of vector quantization schemes vqSGD (Vector-Quantized Stochastic Gradient Descent) that provide an asymptotic reduction in the communication cost with convergence guarantees in first-order distributed optimization. In the process we derive the following fundamental information theoretic fact:$\Theta \left({\frac {d}{R^{2}}}\right)$ bits are necessary and sufficient (up to an additive$O(\log d)$ term) to describe an unbiased estimator$\hat{\boldsymbol {g}}(\boldsymbol {g})$ for any$\boldsymbol {g}$ in the$d$ -dimensional unit sphere, under the constraint that$\| \hat{\boldsymbol {g}}(\boldsymbol {g})\|_{2}\le R$ almost surely,$R > 1$ . In particular, we consider a randomized scheme based on the convex hull of a point set, that returns an unbiased estimator of a$d$ -dimensional gradient vector with almost surely bounded norm. We provide multiple efficient instances of our scheme, that are near optimal, and require$o(d)$ bits of communication at the expense of tolerable increase in error. The instances of our quantization scheme are obtained using well-known families of binary error-correcting codes and provide a smooth tradeoff between the communication and the estimation error of quantization. Furthermore, we show that vqSGD also offers automatic privacy guarantees.- 23 March 2022
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 68 (7) , 4573-4587
vqSGD: Vector Quantized Stochastic Gradient Descent
In this work, we present a family of vector quantization schemes vqSGD (Vector-Quantized Stochastic Gradient Descent) that provide an asymptotic reduction in the communication cost with convergence guarantees in first-order distributed optimization. In the process we derive the following fundamental information theoretic fact:$\Theta \left({\frac {d}{R^{2}}}\right)$ bits are necessary and sufficient (up to an additive$O(\log d)$ term) to describe an unbiased estimator$\hat{\boldsymbol {g}}(\boldsymbol {g})$ for any$\boldsymbol {g}$ in the$d$ -dimensional unit sphere, under the constraint that$\| \hat{\boldsymbol {g}}(\boldsymbol {g})\|_{2}\le R$ almost surely,$R > 1$ . In particular, we consider a randomized scheme based on the convex hull of a point set, that returns an unbiased estimator of a$d$ -dimensional gradient vector with almost surely bounded norm. We provide multiple efficient instances of our scheme, that are near optimal, and require$o(d)$ bits of communication at the expense of tolerable increase in error. The instances of our quantization scheme are obtained using well-known families of binary error-correcting codes and provide a smooth tradeoff between the communication and the estimation error of quantization. Furthermore, we show that vqSGD also offers automatic privacy guarantees.- 28 April 2021
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 67 (7) , 4338-4360
Relaxed Locally Correctable Codes in Computationally Bounded Channels
Error-correcting codes that admit local decoding and correcting algorithms have been the focus of much recent research due to their numerous applications. An important goal is to obtain the best possible tradeoffs between the number of symbols of the codeword that the local decoding algorithm must examine (the locality), and the amount of redundancy in the encoding (the information rate). In Hamming's classical adversarial channel model, the current tradeoffs are dramatic, allowing either small locality but superpolynomial blocklength, or small blocklength but high locality. However, in the computationally bounded adversarial channel model, proposed by Lipton (STACS 1994), constructions of locally decodable codes suddenly exhibit small locality and small blocklength, but these constructions require strong trusted setup assumptions. We study variants of locally decodable and locally correctable codes in computationally bounded, adversarial channels, in a setting with no trusted setup. The only assumption we require is the selection of the public parameters (seed) for a collision-resistant hash function. Specifically, we provide constructions of relaxed locally correctable and relaxed locally decodable codes over the binary alphabet, with constant information rate, and poly-logarithmic locality. Our constructions, which compare favorably with their classical analogs, crucially employ collision-resistant hash functions and local expander graphs, extending ideas from recent cryptographic constructions of memory-hard functions.
- 28 April 2021
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 67 (7) , 4338-4360
Relaxed Locally Correctable Codes in Computationally Bounded Channels
Error-correcting codes that admit local decoding and correcting algorithms have been the focus of much recent research due to their numerous applications. An important goal is to obtain the best possible tradeoffs between the number of symbols of the codeword that the local decoding algorithm must examine (the locality), and the amount of redundancy in the encoding (the information rate). In Hamming's classical adversarial channel model, the current tradeoffs are dramatic, allowing either small locality but superpolynomial blocklength, or small blocklength but high locality. However, in the computationally bounded adversarial channel model, proposed by Lipton (STACS 1994), constructions of locally decodable codes suddenly exhibit small locality and small blocklength, but these constructions require strong trusted setup assumptions. We study variants of locally decodable and locally correctable codes in computationally bounded, adversarial channels, in a setting with no trusted setup. The only assumption we require is the selection of the public parameters (seed) for a collision-resistant hash function. Specifically, we provide constructions of relaxed locally correctable and relaxed locally decodable codes over the binary alphabet, with constant information rate, and poly-logarithmic locality. Our constructions, which compare favorably with their classical analogs, crucially employ collision-resistant hash functions and local expander graphs, extending ideas from recent cryptographic constructions of memory-hard functions.