research
∙
09/11/2023
Testing Spreading Behavior in Networks with Arbitrary Topologies
Inspired by the works of Goldreich and Ron (J. ACM, 2017) and Nakar and ...
share
research
∙
07/17/2023
Lipschitz Continuous Algorithms for Covering Problems
Combinatorial algorithms are widely used for decision-making and knowled...
research
∙
06/14/2023
The Secretary Problem with Predictions
The value maximization version of the secretary problem is the problem o...
research
∙
06/12/2023
General Transformation for Consistent Online Approximation Algorithms
We introduce a transformation framework that can be utilized to develop ...
research
∙
11/09/2022
Lipschitz Continuous Algorithms for Graph Problems
It has been widely observed in the machine learning community that a sma...
research
∙
10/23/2022
Sublinear-Time Algorithms for Max Cut, Max E2Lin(q), and Unique Label Cover on Expanders
We show sublinear-time algorithms for Max Cut and Max E2Lin(q) on expand...
research
∙
04/18/2022
Low Degree Testing over the Reals
We study the problem of testing whether a function f: ℝ^n →ℝ is a polyno...
research
∙
01/18/2022
Sparsification of Decomposable Submodular Functions
Submodular functions are at the core of many machine learning and data m...
research
∙
11/04/2021
Average Sensitivity of Dynamic Programming
When processing data with uncertainty, it is desirable that the output o...
research
∙
06/07/2021
Local Algorithms for Estimating Effective Resistance
Effective resistance is an important metric that measures the similarity...
research
∙
06/04/2021
Spectral Hypergraph Sparsifiers of Nearly Linear Size
Graph sparsification has been studied extensively over the past two deca...
research
∙
05/20/2021
Online Risk-Averse Submodular Maximization
We present a polynomial-time online algorithm for maximizing the conditi...
research
∙
01/25/2021
RelWalk A Latent Variable Model Approach to Knowledge Graph Embedding
Embedding entities and relations of a knowledge graph in a low-dimension...
research
∙
11/12/2020
Towards Tight Bounds for Spectral Sparsification of Hypergraphs
Cut and spectral sparsification of graphs have numerous applications, in...
research
∙
10/08/2020
Sensitivity Analysis of Submodular Function Maximization
We study the recently introduced idea of worst-case sensitivity for mono...
research
∙
09/09/2020
Sensitivity Analysis of the Maximum Matching Problem
We consider the sensitivity of algorithms for the maximum matching probl...
research
∙
07/15/2020
Downsampling for Testing and Learning in Product Distributions
We study the domain reduction problem of eliminating dependence on n fro...
research
∙
06/28/2020
Fast and Private Submodular and k-Submodular Functions Maximization with Matroid Constraints
The problem of maximizing nonnegative monotone submodular functions unde...
research
∙
06/15/2020
Hypergraph Clustering Based on PageRank
A hypergraph is a useful combinatorial object to model ternary or higher...
research
∙
06/07/2020
Average Sensitivity of Spectral Clustering
Spectral clustering is one of the most popular clustering methods for fi...
research
∙
04/30/2020
Weakly Submodular Function Maximization Using Local Submodularity Ratio
Weak submodularity is a natural relaxation of the diminishing return pro...
research
∙
02/14/2020
Statistical Learning with Conditional Value at Risk
We propose a risk-averse statistical learning framework wherein the perf...
research
∙
02/13/2020
Approximability of Monotone Submodular Function Maximization under Cardinality and Matroid Constraints in the Streaming Model
Maximizing a monotone submodular function under various constraints is a...
research
∙
09/08/2019
Distribution-Free Testing of Linear Functions on R^n
We study the problem of testing whether a function f:R^n->R is linear (i...
research
∙
04/05/2019
Average Sensitivity of Graph Algorithms
In modern applications of graphs algorithms, where the graphs of interes...
research
∙
01/28/2019
On Random Subsampling of Gaussian Process Regression: A Graphon-Based Analysis
In this paper, we study random subsampling of Gaussian process regressio...
research
∙
11/05/2018
Limits of Ordered Graphs and Images
The emerging theory of graph limits exhibits an interesting analytic per...
research
∙
09/13/2018
Canonical and Compact Point Cloud Representation for Shape Classification
We present a novel compact point cloud representation that is inherently...
research
∙
09/12/2018
Finding Cheeger Cuts in Hypergraphs via Heat Equation
Cheeger's inequality states that a tightly connected subset can be extra...
research
∙
07/13/2018
Spectral Sparsification of Hypergraphs
For an undirected/directed hypergraph G=(V,E), its Laplacian L_GR^V→R^V ...
research
∙
06/27/2018
Sublinear-Time Quadratic Minimization via Spectral Decomposition of Matrices
We design a sublinear-time approximation algorithm for quadratic functio...
research
∙
03/29/2018
Polynomial-Time Algorithms for Submodular Laplacian Systems
Let G=(V,E) be an undirected graph, L_G∈R^V × V be the associated Laplac...
research
∙
02/26/2018
Guaranteed Sufficient Decrease for Stochastic Variance Reduced Gradient Optimization
In this paper, we propose a novel sufficient decrease technique for stoc...
research
∙
02/16/2018
Spectral Normalization for Generative Adversarial Networks
One of the challenges in the study of generative adversarial networks is...
research
∙
09/05/2017
Using k-way Co-occurrences for Learning Word Embeddings
Co-occurrences between two words provide useful insights into the semant...
research
∙
05/31/2017
Spectral Norm Regularization for Improving the Generalizability of Deep Learning
We investigate the generalizability of deep learning based on the sensit...
research
∙
03/20/2017
Guaranteed Sufficient Decrease for Variance Reduced Stochastic Gradient Descent
In this paper, we propose a novel sufficient decrease technique for vari...
research
∙
08/25/2016
Minimizing Quadratic Functions in Constant Time
A sampling-based optimization method for quadratic functions is proposed...
research
∙
12/07/2014
