1 citations · 2 across the 4 of their papers we have counts for
4 papers
The Space Complexity of Generating Tent Codes
Naoaki Okada, Shuji Kijima
This paper is motivated by a question whether it is possible to calculate a chaotic sequence efficiently, e.g., is it possible to get the -th bit of a bit sequence generated by…
An analysis of load-balancing algorithms on edge-Markovian evolving graphs
Takeharu Shiraga, Shuji Kijima
Analysis of algorithms on time-varying networks (often called evolving graphs) is a modern challenge in theoretical computer science. The edge-Markovian is a relatively simple and…
An FPTAS for the Volume of a -polytope ---It is Hard to Compute The Volume of The Intersection of Two Cross-polytopes
Ei Ando, Shuji Kijima
Given an -dimensional convex body by a membership oracle in general, it is known that any polynomial-time deterministic algorithm cannot approximate its volume within ratio $(n/…
Extended Formulations for Sparsity Matroids
Satoru Iwata, Naoyuki Kamiyama, Naoki Katoh +2
We show the existence of a polynomial-size extended formulation for the base polytope of a -sparsity matroid. For an undirected graph , the size of the formulati…