Yuichi Yoshida

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

0 Augusto Modanese, et al. ∙

research

∙ 07/17/2023

Lipschitz Continuous Algorithms for Covering Problems

Combinatorial algorithms are widely used for decision-making and knowled...

0 Soh Kumabe, et al. ∙

research

∙ 06/14/2023

The Secretary Problem with Predictions

The value maximization version of the secretary problem is the problem o...

0 Kaito Fujii, et al. ∙

research

∙ 06/12/2023

General Transformation for Consistent Online Approximation Algorithms

We introduce a transformation framework that can be utilized to develop ...

0 Jing Dong, et al. ∙

research

∙ 11/09/2022

Lipschitz Continuous Algorithms for Graph Problems

It has been widely observed in the machine learning community that a sma...

0 Soh Kumabe, et al. ∙

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

0 Pan Peng, et al. ∙

research

∙ 04/18/2022

Low Degree Testing over the Reals

We study the problem of testing whether a function f: ℝ^n →ℝ is a polyno...

0 Vipul Arora, et al. ∙

research

∙ 01/18/2022

Sparsification of Decomposable Submodular Functions

Submodular functions are at the core of many machine learning and data m...

0 Akbar Rafiey, et al. ∙

research

∙ 11/04/2021

Average Sensitivity of Dynamic Programming

When processing data with uncertainty, it is desirable that the output o...

0 Soh Kumabe, et al. ∙

research

∙ 06/07/2021

Local Algorithms for Estimating Effective Resistance

Effective resistance is an important metric that measures the similarity...

0 Pan Peng, et al. ∙

research

∙ 06/04/2021

Spectral Hypergraph Sparsifiers of Nearly Linear Size

Graph sparsification has been studied extensively over the past two deca...

0 Michael Kapralov, et al. ∙

research

∙ 05/20/2021

Online Risk-Averse Submodular Maximization

We present a polynomial-time online algorithm for maximizing the conditi...

0 Tasuku Soma, et al. ∙

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

13 Danushka Bollegala, et al. ∙

research

∙ 11/12/2020

Towards Tight Bounds for Spectral Sparsification of Hypergraphs

Cut and spectral sparsification of graphs have numerous applications, in...

0 Michael Kapralov, et al. ∙

research

∙ 10/08/2020

Sensitivity Analysis of Submodular Function Maximization

We study the recently introduced idea of worst-case sensitivity for mono...

0 Conor McMeel, et al. ∙

research

∙ 09/09/2020

Sensitivity Analysis of the Maximum Matching Problem

We consider the sensitivity of algorithms for the maximum matching probl...

0 Yuichi Yoshida, et al. ∙

research

∙ 07/15/2020

Downsampling for Testing and Learning in Product Distributions

We study the domain reduction problem of eliminating dependence on n fro...

0 Nathaniel Harms, et al. ∙

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

0 Akbar Rafiey, et al. ∙

research

∙ 06/15/2020

Hypergraph Clustering Based on PageRank

A hypergraph is a useful combinatorial object to model ternary or higher...

0 Yuuki Takai, et al. ∙

research

∙ 06/07/2020

Average Sensitivity of Spectral Clustering

Spectral clustering is one of the most popular clustering methods for fi...

0 Pan Peng, et al. ∙

research

∙ 04/30/2020

Weakly Submodular Function Maximization Using Local Submodularity Ratio

Weak submodularity is a natural relaxation of the diminishing return pro...

0 Richard Santiago, et al. ∙

research

∙ 02/14/2020

Statistical Learning with Conditional Value at Risk

We propose a risk-averse statistical learning framework wherein the perf...

0 Tasuku Soma, et al. ∙

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

0 Chien-Chung Huang, et al. ∙

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

0 Noah Fleming, et al. ∙

research

∙ 04/05/2019

Average Sensitivity of Graph Algorithms

In modern applications of graphs algorithms, where the graphs of interes...

0 Nithin Varma, et al. ∙

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

16 Kohei Hayashi, et al. ∙

research

∙ 11/05/2018

Limits of Ordered Graphs and Images

The emerging theory of graph limits exhibits an interesting analytic per...

0 Omri Ben-Eliezer, et al. ∙

research

∙ 09/13/2018

Canonical and Compact Point Cloud Representation for Shape Classification

We present a novel compact point cloud representation that is inherently...

0 Kent Fujiwara, et al. ∙

research

∙ 09/12/2018

Finding Cheeger Cuts in Hypergraphs via Heat Equation

Cheeger's inequality states that a tightly connected subset can be extra...

0 Masahiro Ikeda, et al. ∙

research

∙ 07/13/2018

Spectral Sparsification of Hypergraphs

For an undirected/directed hypergraph G=(V,E), its Laplacian L_GR^V→R^V ...

0 Tasuku Soma, et al. ∙

research

∙ 06/27/2018

Sublinear-Time Quadratic Minimization via Spectral Decomposition of Matrices

We design a sublinear-time approximation algorithm for quadratic functio...

0 Amit Levi, et al. ∙

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

0 Kaito Fujii, et al. ∙

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

0 Fanhua Shang, et al. ∙

research

∙ 02/16/2018

Spectral Normalization for Generative Adversarial Networks

One of the challenges in the study of generative adversarial networks is...

0 Takeru Miyato, et al. ∙

research

∙ 09/05/2017

Using k-way Co-occurrences for Learning Word Embeddings

Co-occurrences between two words provide useful insights into the semant...

0 Danushka Bollegala, et al. ∙

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

0 Yuichi Yoshida, et al. ∙

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

0 Fanhua Shang, et al. ∙

research

∙ 08/25/2016

Minimizing Quadratic Functions in Constant Time

A sampling-based optimization method for quadratic functions is proposed...

0 Kohei Hayashi, et al. ∙

research

∙ 12/07/2014

Learning Word Representations from Relational Graphs

Attributes of words and relations between two words are central to numer...

0 Danushka Bollegala, et al. ∙

Yuichi Yoshida

Featured Co-authors