publications

Hardness/Approximation

  • Near-Optimal UGC-hardness of Approximating Max $k$-CSP$_R$
    Pasin Manurangsi, Preetum Nakkiran, Luca Trevisan. APPROX 2016.

    Summary: In this paper, we prove an almost-optimal hardness-of-approximation for Maximum Constraint-Satisfaction Problems (Max CSPs), based on Khot's Unique Games Conjecture (UGC). In Max $k$-CSP$_R$, we are given a set of predicates each of which depends on exactly $k$ variables. Each variable can take any value from $1, 2,\dots, R$. The goal is to find an assignment to variables that maximizes the number of satisfied predicates. We improve the best-known Unique-Games-hardness for small $k \geq 3$, and also give an almost tight approximation algorithm. For example, for a constant $k \geq 3$, we improve the previously-known gap between hardness and approximation-algorithm from $O(R)$ to $O(\text{polylog} R)$.

Coding Theory


  • General Strong Polarization
    Jarosław Błasiok, Venkatesan Guruswami, Preetum Nakkiran, Atri Rudra, Madhu Sudan. STOC 2018.

    Summary: We abstract, generalize, and simplify the analysis of polar codes. Our techniques give an exact charecterization of matrices which polarize over prime fields. This leads to efficient capacity-achieving source codes for compressing arbitrary i.i.d. sources, and capacity-achieving channel codes for arbitrary symmetric memoryless channels.
  • Optimal Systematic Distributed Storage Codes with Fast Encoding     (Full version)
    Preetum Nakkiran, K.V. Rashmi, Kannan Ramchandran. ISIT 2016.

    Summary: We construct storage codes that have the optimal repair properties of regenerating-codes (that is, they minimize the bandwidth required to repair failed nodes), while still matching the sparsity of traditional erasure codes (eg, Reed-Solomon). To achieve the same redundancy of an $[n, k]$ Reed-Solomon code, each parity-symbol in our code depends on only $O(k)$ message symbols. For comparison, previous systematic regenerating-codes required a sparsity of $O(k^2)$ symbols. We also present a general framework for understanding how a certain type of code transformation affect sparsity, which yields a procedure for constructing other sparse storage codes.
  • Fundamental Limits on Communication for Oblivious Updates in Storage Networks     (slides)
    Preetum Nakkiran, Nihar B. Shah, K.V. Rashmi. IEEE GLOBECOM 2014

    Summary: We determine the communication complexity of a certain "update" operation in distributed storage codes. The setting is that one machine was offline while the message being stored was updated. Upon coming back online, this stale machine needs to update its encoded data, using the (updated) encoded data from other machines. The setting is "oblivious" in that all parties know that something has updated, but nobody knows exactly what changed. We show lower-bounds on communication in several related settings, and also give matching upper-bounds.

Speech Recognition (@Google)

  • Compressing Deep Neural Networks using a Rank-Constrained Topology
    Preetum Nakkiran, Raziel Alvarez, Rohit Prabhavalkar, Carolina Parada. INTERSPEECH 2015

    Summary: We present a general approach to reduce the size of deep neural networks (DNNs), especially those used in speech recognition. We propose a rank-constrained topology, which factors the weights of each node in the input layer of the DNN into a low-rank representation. This exploits the natural two-dimensional (time x frequency) structure in the input. These techniques are applied to a keyword spotting task (eg, like detecting "ok google"), where we found that we can reduce model size by 75% relative to the baseline, without any loss in performance.

Misc.

  • Iterative Hard Thresholding for Keyword Extraction from Large Text Corpora
    Steve Yadlowsky, Preetum Nakkiran, Jingyan Wang, Rishi Sharma, L. El Ghaoui. Proc. ICMLA 2014

    Summary: We explore applying an algorithm for handling cardinality-constrained least-squares to extract keywords from text databases like news source. We show promising experimental results, and slightly generalize a prior convergence analysis.