99 citations · 220 across the 16 of their papers we have counts for
7 papers · 1 filter
Lower Bounds for Pseudo-Deterministic Counting in a Stream
Vladimir Braverman, Robert Krauthgamer, Aditya Krishnan +1
Many streaming algorithms provide only a high-probability relative approximation. These two relaxations, of allowing approximation and randomization, seem necessary -- for many str…
Projective Clustering Product Quantization
Aditya Krishnan, Edo Liberty
This paper suggests the use of projective clustering based product quantization for improving nearest neighbor and max-inner-product vector search (MIPS) algorithms. We provide ani…
Sublinear Time Spectral Density Estimation
Vladimir Braverman, Aditya Krishnan, Christopher Musco
We present a new sublinear time algorithm for approximating the spectral density (eigenvalue distribution) of an normalized graph adjacency or Laplacian matrix. The alg…
Near-Optimal Entrywise Sampling of Numerically Sparse Matrices
Vladimir Braverman, Robert Krauthgamer, Aditya Krishnan +1
Many real-world data sets are sparse or almost sparse. One method to measure this for a matrix is the \emph{numerical sparsity}, denoted $\mathsf{ns}(…
Competitively Pricing Parking in a Tree
Max Bender, Jacob Gilbert, Aditya Krishnan +1
Motivated by demand-responsive parking pricing systems we consider posted-price algorithms for the online metrical matching problem and the online metrical searching problem in a t…
Schatten Norms in Matrix Streams: Hello Sparsity, Goodbye Dimension
Vladimir Braverman, Robert Krauthgamer, Aditya Krishnan +1
Spectral functions of large matrices contains important structural information about the underlying data, and is thus becoming increasingly important. Many times, large matrices re…
On Sketching the to norms
Aditya Krishnan, Sidhanth Mohanty, David P. Woodruff
We initiate the study of data dimensionality reduction, or sketching, for the norms. Given an matrix , the norm, denoted $\|A\|_{q \to p} = \sup_{…