8 citations · 41 across the 26 of their papers we have counts for
12 papers · 1 filter
Exponentially Improving the Complexity of Simulating the Weisfeiler-Lehman Test with Graph Neural Networks
Anders Aamand, Justin Y. Chen, Piotr Indyk +5
Recent work shows that the expressive power of Graph Neural Networks (GNNs) in distinguishing non-isomorphic graphs is exactly the same as that of the Weisfeiler-Lehman (WL) graph…
Robustness Implies Privacy in Statistical Estimation
Samuel B. Hopkins, Gautam Kamath, Mahbod Majid +1
We study the relationship between adversarial robustness and differential privacy in high-dimensional algorithmic statistics. We give the first black-box reduction from privacy to…
Estimating the Effective Support Size in Constant Query Complexity
Shyam Narayanan, Jakub Tětek
Estimating the support size of a distribution is a well-studied problem in statistics. Motivated by the fact that this problem is highly non-robust (as small perturbations in the d…
Sampling an Edge in Sublinear Time Exactly and Optimally
Talya Eden, Shyam Narayanan, Jakub Tětek
Sampling edges from a graph in sublinear time is a fundamental problem and a powerful subroutine for designing sublinear-time algorithms. Suppose we have access to the vertices of…
Bias Reduction for Sum Estimation
Talya Eden, Jakob Bæk Tejs Houen, Shyam Narayanan +2
In classical statistics and distribution testing, it is often assumed that elements can be sampled from some distribution , and that when an element is sampled, the probabil…
Optimal Time-Backlog Tradeoffs for the Variable-Processor Cup Game
William Kuszmaul, Shyam Narayanan
The \emph{-processor cup game} is a classic and widely studied scheduling problem that captures the setting in which a -processor machine must assign tasks to processors ove…
Improved Approximations for Euclidean -means and -median, via Nested Quasi-Independent Sets
Vincent Cohen-Addad, Hossein Esfandiari, Vahab Mirrokni +1
Motivated by data analysis and machine learning applications, we consider the popular high-dimensional Euclidean -median and -means problems. We propose a new primal-dual alg…
All-Pairs Shortest Path Distances with Differential Privacy: Improved Algorithms for Bounded and Unbounded Weights
Justin Y. Chen, Shyam Narayanan, Yinzhan Xu
We revisit the problem of privately releasing the all-pairs shortest path distances of a weighted undirected graph up to low additive error, which was first studied by Sealfon [Sea…
Triangle and Four Cycle Counting with Predictions in Graph Streams
Justin Y. Chen, Talya Eden, Piotr Indyk +7
We propose data-driven one-pass streaming algorithms for estimating the number of triangles and four cycles, two fundamental problems in graph analytics that are widely studied in…
Private High-Dimensional Hypothesis Testing
Shyam Narayanan
We provide improved differentially private algorithms for identity testing of high-dimensional distributions. Specifically, for -dimensional Gaussian distributions with known co…
A 120dB Programmable-Range On-Chip Pulse Generator for Characterizing Ferroelectric Devices
Shyam Narayanan, Erika Covi, Viktor Havel +7
Novel non-volatile memory devices based on ferroelectric thin films represent a promising emerging technology that is ideally suited for neuromorphic applications. The physical swi…
Stochastic dendrites enable online learning in mixed-signal neuromorphic processing systems
Matteo Cartiglia, Arianna Rubino, Shyam Narayanan +4
The stringent memory and power constraints required in edge-computing sensory-processing applications have made event-driven neuromorphic systems a promising technology. On-chip on…