publications
Hardness/Approximation
NearOptimal UGChardness of Approximating Max $k$CSP$_R$
Pasin Manurangsi, Preetum Nakkiran, Luca Trevisan.
APPROX 2016.
Summary:
In this paper, we prove an almostoptimal hardnessofapproximation for
Maximum ConstraintSatisfaction 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 bestknown UniqueGameshardness for small $k \geq 3$, and
also give an almost tight approximation algorithm.
For example, for a constant $k \geq 3$, we improve
the previouslyknown gap between hardness and approximationalgorithm
from $O(R)$ to $O(\text{polylog} R)$.
Regenerating Codes
An overview poster is here.
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
regeneratingcodes (that is, they minimize the bandwidth required to repair
failed nodes), while still matching the sparsity of traditional erasure codes (eg,
ReedSolomon).
To achieve the same redundancy of an $[n, k]$ ReedSolomon code,
each paritysymbol in our code depends on only $O(k)$ message symbols.
For comparison, previous systematic regeneratingcodes 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 lowerbounds on communication in several related settings, and also give
matching upperbounds.
Speech Recognition (@Google)
Compressing Deep Neural Networks using a RankConstrained 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 rankconstrained
topology, which factors the weights of each node in the input
layer of the DNN into a lowrank representation.
This exploits the natural twodimensional (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.
Other
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
cardinalityconstrained leastsquares to extract keywords from text databases
like news source.
We show promising experimental results, and slightly generalize a prior
convergence analysis.
