## Karthik Gajulapalli

- Position: Undergraduate Student Researcher
- Areas:
- Complexity Theory
- Theoretical Cryptography
- Algorithmic Game Theory

- Advisor:
- Office: DBH
- E-mail: kgajulap@uci.edu

### Brief BIO

I am a fourth year undergraduate at UCI. I am pursuing a double major in Computer Science and Math. I am interested in areas of complexity theory like circuit lower bounds, psuedorandomness and derandomization. I am also interested in areas of theoretical cryptography like oblivious ram and multiparty computations. I also enjoy economics and have an interest in Algorithmic Game Theory.

I have been involved with the ACM club on campus and have taught a year long course on competitive programming.
### Projects

#### CURRENT PROJECTS

I am currently working on understanding the structure of popular marriages. Popular marriages is a weaker notion than stable marriage, it is defined on incomplete preference lists and popularity implies a matching that is a condorcet winner amongst all other matchings in the graph. The problem is especially interesting because we can efficiently compute min-size popular marriage and max-size popular marriage , but if we ask about the existence of k-size popular marriage in between the problem becomes NP-complete.

----------------------------------------------------------------------
#### PAST PROJECTS

#### TIPPERS

I worked on TIPPERS under Professor Sharad Mehrotra for 3 years and was funded by a DARPA grant. Most of my work relied on implementing sensor subsytems around donald bren hall and providing a mechanism for data capture from all these sensors. At a high level the problem we were trying to address was the following, aggregate queries could have large privacy implications. For example knowing the power consumption of the whole floor could tell who is in the building at some particular time. The project used techiniques like differential privacy to approach the problem.

-------------------------------------------------------------------------
#### List of Papers that Everyone should read

- Coin Flipping over a Telephone (Manuel Blum)
- The Complexity of Interactive Proof Systems (Goldwasser, Micali, Rackoff)
- Probabilistic Encryption (Goldwasser, Micali)
- The Serializability of Concurrent Database Updates (Christos Papadimitriou)
- Non-Uniform ACC Circuit Lower Bounds (Ryan Williams)
- The complexity of computing a nash equilibrium (Daskalakis, Goldberg, Papadimitriou)
- How to Write a Proof (Lamport)

#### A Collection of Quotes

- "If greedy approach fails for a competitive programming problem then the input is wrong." -- Karthik Gajulapalli
- "There is an art to flying, or rather a knack. The knack lies in learning how to throw yourself at the ground and miss. Clearly, it is the second part, the missing, that presents the difficulties." --Douglas Adams (Hitchikers Guide)
- "For the strength of the pack is the wolf, and the strength of the wolf is the pack." -- Rudyard Kipling (Jungle Book)

Information and Computer Science

University of California, Irvine

Irvine, CA 92697-3425
Last modified: 02 Jul 2016