Pulkit Grover

Pulkit Grover


Assistant Professor, ECE
B-202 Hamerschlag Hall
Carnegie Mellon University
Ph: (412) 268-3644

pgrover at andrew dot cmu dot edu


Image credit: Kris Woyach

Broadly, I am interested in an understanding of information that goes beyond just communication. Our lab seeks to attain this understanding through a mix of thought and laboratory experiments. Current topics of interest include fundamental and practical understanding of circuits for processing and communicating information; flow of information in neuronal systems; and understanding information and its use by exploring the union of control and communication.

Our new Lab Webpage is up! We are looking for 1-2 undergraduate students, 1-2 MS students, and 1-2 Ph.D. students. Drop me an email if you're interested!

Postdoctoral researcher (2011-12) in Electrical Engineering, Stanford University.
PhD, UC Berkeley, Dec 2010.
B. Tech, M.Tech, IIT Kanpur ('03, '05), Schooling: Vidyashram, Jaipur
You can find my CV here.

Do consider submitting to the JSAC special issue on Wireless Comm via Energy Harvesting and Wireless Power!

“Understanding Information and Computational Complexity:
Theoretical underpinnings and practical designs of “green” radios”



The goal is to develop a fundamental and relevant understanding of complexity of coding and communication techniques. Intellectually, complexity of coding is a missing piece that limits our larger understanding of “information”. Practically, today's short-distance communication systems require processing power that dominates transmit power, sometimes by orders of magnitude.

Theory: Developing a fundamental understanding of complexity of coding has proven extremely difficult: fundamental limits on complexity of problems are in general hard to obtain. My work establishes the first such fundamental limits on encoding and decoding power. The novelty that allows me to do so is to use models based on communication complexity, rather than Turing complexity (number of operations). Simultaneously, for today's circuits, communication complexity turns out to be more closely related to power consumption than number of operations.

Practice: Taking these results towards practice, I use these bounds as guiding principles behind code designs. Not only does this lead to new code-design problems (see [Globecom '12]), we also show that this approach of jointly designing code/encoder/decoder triples (rather than designing them in isolation) has the potential to significantly reduce power consumed in short-distance communication systems.

Power is consumed not just in transmission, but in ALL of these components!

Main contributions

Theory: Our main contribution is to provide fundamental bounds on encoding/decoding power. These limits offer a different picture when compared with the traditional (transmit-power-only) Shannon-limit.

Conclusions derived from our “Node Model” and “Wire Model” are as follows:


Practice: What are the best codes now? A joint theory-practice approach based on modeling of circuit-power using rigorous circuit simulation shows that the code construction and the complexity of decoding algorithm needs to increase as the target error probability is lowered or as the communication distance is increased.


Our results have the potential to drastically reduce power consumed in short-distance wireless (e.g. 60 GHz band) and wired (e.g. multi-Gbps communication in data-centers) communication.

Salient references (full list at here)

Theory:

[ITW '07] Pulkit Grover, Bounds on the Tradeoff between decoding complexity and rate for codes on graphs, Proceedings of the IEEE Information Theory Workshop (ITW) 2007, Lake Tahoe, CA, 2007. [PDF]

[ISIT '09] Pulkit Grover and Anant Sahai, Time-division multiplexing for Green Broadcasting. (extended version) Proceedings of the IEEE International Symposium on Information Theory (ISIT), 2009. [Short description] [PDF] [Handout] [Slides] [MATLAB code]

[JSAC '11] Pulkit Grover, Kristen Ann Woyach and Anant Sahai, Towards a communication-theoretic understanding of system-level power consumption, IEEE Journal of Selected Areas in Communication (JSAC) Special Issue on Energy-Efficient Wireless Communications. [PDF][MATLAB Code]

[CISS '11] Pulkit Grover and Anant Sahai, Fundamental bounds on the interconnect complexity of decoder implementations, Accepted at Conference on Information Sciences and Systems (CISS) 2011. [PDF]

[ISIT '12] Pulkit Grover, Andrea Goldsmith and Anant Sahai. Fundamental limits on complexity and power consumption in coded communication. Proceedings of the IEEE International Symposium on Information Theory (ISIT), 2012. [PDF]

Practice:

[DAC '11] Karthik Ganesan and Pulkit Grover, Decoding power can increase significantly with increased wire-lengths and code performance: empirical results, Design Automation Conference (DAC) 2011, Work In Progress Session.

[SiPS '11] Karthik Ganesan, Pulkit Grover, and Jan Rabaey, The power cost of overdesigning codes, 2011 IEEE Workshop on Signal Processing Systems, Beirut, Lebanon.

[Globecom '12] Karthik Ganesan, Yang Wen, Pulkit Grover, Andrea Goldsmith and Jan Rabaey, Mixing theory and experiments to choose the “greenest” code-decoder pair, Globecom 2012.

“Understanding Information and its Use:
Control and communication in cyber-physical systems”



The goal: How do we connect the “cyber” -- the computational/ communicating/ controlling agents -- with the “physical” -- the world around us? My dissertation lays down the foundations of a theory to help answer this question.

The question: Let us consider two control agents that are connected using a noisy communication link. How should they share their workload? I was surprised to find that we do not know the answer! This is because most of the problem formulations and solution techniques in this field are inspired from those in modern communication theory, and simplify the control agents into “observers” or “controllers.”

The “observers” cannot act on the system, and therefore they communicate their observations to the “controllers.” The “controllers” cannot observe the state directly, and thus rely on the signals sent by the “observers” to decide on their actions. In a realistic control system, these simplified control agents may be extremely limiting. However, analytically, they have been simpler to understand because they disallow implicit communication through the system from the observer to the controller.

A theory of implicit communication:

The crux of this issue is captured in a deceptively simple problem called the Witsenhausen counterexample, which has been open despite more than 40 years of research effort. In my dissertation, I provide the first provably approximately-optimal solution to the Witsenhausen counterexample by understanding the potential of implicit communication between the controllers. These approximately-optimal solutions were developed in the following sequence of results. In [CDC '08, IJSCC '10, ITW '10], we introduce a vector version of Witsenhausen's counterexample, and obtain approximately-optimal solutions for an asymptotically infinite- length version of the problem. In [ConCom '09, CDC '09, TAC '10 Sub.], we pull the results back to finite-lengths, including the original (scalar) counterexample, using techniques from large-deviation theory.

Building a communication theory for decentralized control: In my dissertation, I argue that the Witsenhausen counterexample has been a major bottleneck in understanding the interplay of control and communication. Because the counterexample was viewed as essentially unsolvable, it forced problem formulations into corners where the obtained engineering insights could only be very limited. Our approach of using semi-deterministic models to obtain approximately-optimal strategies can be extended to understand toy problems of control under commu- nication constraints which could not have been understood earlier. For instance, what happens when controllers can communicate implicitly as well as explicitly [Allerton '10]? How should one communicate implicitly in a dynamic setting with feedback [Ph.D. thesis]? Various extensions of the counterexample appear in [Allerton '09, ISIT '10, CDC '10].

Salient references

[CDC '08] Pulkit Grover and Anant Sahai, A vector version of Witsenhausen's counterexample : Towards convergence of control, communication and computation. Proceedings of the IEEE Conference on Decision and Control in Cancun, Mexico, 2008. [PDF] [Handout] [Slides]

[IJSCC '10] Pulkit Grover and Anant Sahai, Vector Witsenhausen Counterexample as Assisted Interference Suppression. Special Issue on "Information Processing and Decision Making in Distributed Control Systems" of the International Journal of Systems, Control and Communications (IJSCC), 2010.

[ITW '10] Pulkit Grover, Aaron B. Wagner and Anant Sahai, Information Embedding Meets Distributed Control. Proceedings of the IEEE Information Theory Workshop 2010, Cairo, Egypt. [PDF] [MATLAB code]

[ConCom '09] Pulkit Grover, Anant Sahai and Se Yong Park, The finite-dimensional Witsenhausen counterexample. (Extended version) Proceedings of the 7th International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks (WiOpt), Workshop on Control over Communication Channels (ConCom) 2009. [Short description] [PDF] [Handout] [Slides][MATLAB code]

[Allerton '09] Pulkit Grover, Se Yong Park and Anant Sahai, On the Generalized Witsenhausen Counterexample. Allerton Conference on Communication, Control, and Computing, Illinois, 2009. [PDF]

[ISIT '10] Pulkit Grover and Anant Sahai, Distributed signal cancelation inspired by Witsenhausen's counterexample. IEEE International Symposium on Information Theory (ISIT) 2010. [expanded PDF] [Proceedings version]

[TAC '10 Sub.] Pulkit Grover, Anant Sahai and Se Yong Park, The finite-dimensional Witsenhausen counterexample. IEEE Transactions on Automatic Control, to appear (2013). [PDF] [Talk Handout] [Talk Slides][MATLAB code]

Students


PhD
  • Yaoqing (Jordan) Yang (jointly with Soummya Kar)
  • Majid Mahzoon


  • UG/MS
  • Ana Beisy Cruz, undergraduate, CMU (since summer 2013; demos for signals and systems, neural measurements)
  • Peter Wei, undergraduate, CMU (summer 2013; demos for signals and systems)
  • Phillip Fynan, undergraduate, Calvin College (since summer 2013; "green" communications)
  • Rahshel Brown, undergraduate, CMU (since 2013; energy harvesting)
  • Max Regan, undergraduate, CMU (since 2013; energy harvesting)

  • Past students


  • Karthik Ganesan, undergraduate, UC Berkeley (2010--; "green" communications theory & circuits, now a grad student at Stanford)
  • George Alexandrov, undergraduate, Stanford (2012-13; circuits for inductively coupled communication, now a grad student at Berkeley)
  • Yang Wen, senior undergraduate, UC Berkeley (2011-12; worked on green code/decoder pairs, now at Oracle designing green servers)

  • The epithet “students” is unfair to all of the above who have taught me a lot during our collaborations.

    Research support


  • NSF-ECCS-1343324 (through NSF EARS program)
  • NSF-CCF-1350314 (through NSF CAREER award)
  • Seed grants from NSF CSoI (the NSF Center for Science of Information)
  • NSF CSoI affiliate
  • The support from these organizations is gratefully acknowledged.