33 citations · 48 across the 11 of their papers we have counts for
13 papers
The Robustness of LWPP and WPP, with an Application to Graph Reconstruction
Edith Hemaspaandra, Lane A. Hemaspaandra, Holger Spakowski +1
We show that the counting class LWPP [FFK94] remains unchanged even if one allows a polynomial number of gap values rather than one. On the other hand, we show that it is impossibl…
Generalized Shortest Path Kernel on Graphs
Linus Hermansson, Fredrik D. Johansson, Osamu Watanabe
We consider the problem of classifying graphs using graph kernels. We define a new graph kernel, called the generalized shortest path kernel, based on the number and length of shor…
Peeling Algorithm on Random Hypergraphs with Superlinear Number of Hyperedges
Ryuhei Mori, Osamu Watanabe
When we try to solve a system of linear equations, we can consider a simple iterative algorithm in which an equation including only one variable is chosen at each step, and the var…
Random Almost-Popular Matchings
Suthee Ruangwises, Osamu Watanabe
For a set of people and a set of items, with each person having a preference list that ranks all items from most wanted to least wanted, we consider the problem of…
Polynomial size linear programs for problems in P
David Avis, David Bremner, Hans Raj Tiwary +1
A perfect matching in an undirected graph is a set of vertex disjoint edges from that include all vertices in . The perfect matching problem is to decide if ha…
Linear Programming Relaxations for Goldreich's Generators over Non-Binary Alphabets
Ryuhei Mori, Takeshi Koshiba, Osamu Watanabe +1
Goldreich suggested candidates of one-way functions and pseudorandom generators included in . It is known that randomly generated Goldreich's generator using …