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.
|