
Local Algorithms for Estimating Effective Resistance
Effective resistance is an important metric that measures the similarity...
read it

Spectral Hypergraph Sparsifiers of Nearly Linear Size
Graph sparsification has been studied extensively over the past two deca...
read it

Online RiskAverse Submodular Maximization
We present a polynomialtime online algorithm for maximizing the conditi...
read it

RelWalk A Latent Variable Model Approach to Knowledge Graph Embedding
Embedding entities and relations of a knowledge graph in a lowdimension...
read it

Towards Tight Bounds for Spectral Sparsification of Hypergraphs
Cut and spectral sparsification of graphs have numerous applications, in...
read it

Sensitivity Analysis of Submodular Function Maximization
We study the recently introduced idea of worstcase sensitivity for mono...
read it

Sensitivity Analysis of the Maximum Matching Problem
We consider the sensitivity of algorithms for the maximum matching probl...
read it

Downsampling for Testing and Learning in Product Distributions
We study the domain reduction problem of eliminating dependence on n fro...
read it

Fast and Private Submodular and kSubmodular Functions Maximization with Matroid Constraints
The problem of maximizing nonnegative monotone submodular functions unde...
read it

Hypergraph Clustering Based on PageRank
A hypergraph is a useful combinatorial object to model ternary or higher...
read it

Average Sensitivity of Spectral Clustering
Spectral clustering is one of the most popular clustering methods for fi...
read it

Weakly Submodular Function Maximization Using Local Submodularity Ratio
Weak submodularity is a natural relaxation of the diminishing return pro...
read it

Statistical Learning with Conditional Value at Risk
We propose a riskaverse statistical learning framework wherein the perf...
read it

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

DistributionFree Testing of Linear Functions on R^n
We study the problem of testing whether a function f:R^n>R is linear (i...
read it

Average Sensitivity of Graph Algorithms
In modern applications of graphs algorithms, where the graphs of interes...
read it

On Random Subsampling of Gaussian Process Regression: A GraphonBased Analysis
In this paper, we study random subsampling of Gaussian process regressio...
read it

Limits of Ordered Graphs and Images
The emerging theory of graph limits exhibits an interesting analytic per...
read it

Canonical and Compact Point Cloud Representation for Shape Classification
We present a novel compact point cloud representation that is inherently...
read it

Finding Cheeger Cuts in Hypergraphs via Heat Equation
Cheeger's inequality states that a tightly connected subset can be extra...
read it

Spectral Sparsification of Hypergraphs
For an undirected/directed hypergraph G=(V,E), its Laplacian L_GR^V→R^V ...
read it

SublinearTime Quadratic Minimization via Spectral Decomposition of Matrices
We design a sublineartime approximation algorithm for quadratic functio...
read it

PolynomialTime Algorithms for Submodular Laplacian Systems
Let G=(V,E) be an undirected graph, L_G∈R^V × V be the associated Laplac...
read it

Guaranteed Sufficient Decrease for Stochastic Variance Reduced Gradient Optimization
In this paper, we propose a novel sufficient decrease technique for stoc...
read it

Spectral Normalization for Generative Adversarial Networks
One of the challenges in the study of generative adversarial networks is...
read it

Using kway Cooccurrences for Learning Word Embeddings
Cooccurrences between two words provide useful insights into the semant...
read it

Spectral Norm Regularization for Improving the Generalizability of Deep Learning
We investigate the generalizability of deep learning based on the sensit...
read it

Guaranteed Sufficient Decrease for Variance Reduced Stochastic Gradient Descent
In this paper, we propose a novel sufficient decrease technique for vari...
read it

Minimizing Quadratic Functions in Constant Time
A samplingbased optimization method for quadratic functions is proposed...
read it

Learning Word Representations from Relational Graphs
Attributes of words and relations between two words are central to numer...
read it
Yuichi Yoshida
is this you? claim profile