63 citations · 220 across the 18 of their papers we have counts for
18 papers
The Ultimate Signs of Second-Order Holonomic Sequences
Fugen Hagihara, Akitoshi Kawamura
A real-valued sequence is said to be second-order holonomic if it satisfies a linear recurrence for…
Representation Theory of Compact Metric Spaces and Computational Complexity of Continuous Data
Akitoshi Kawamura, Donghyun Lim, Svetlana Selivanova +1
Choosing an encoding over binary strings for input/output to/by a Turing Machine is usually straightforward and/or inessential for discrete data (like graphs), but delicate -- heav…
Invitation to Real Complexity Theory: Algorithmic Foundations to Reliable Numerics with Bit-Costs
Akitoshi Kawamura, Martin Ziegler
While concepts and tools from Theoretical Computer Science are regularly applied to, and significantly support, software development for discrete problems, Numerical Engineering la…
Polynomial running times for polynomial-time oracle machines
Akitoshi Kawamura, Florian Steinberg
This paper introduces a more restrictive notion of feasibility of functionals on Baire space than the established one from second-order complexity theory. Thereby making it possibl…
Weight Balancing on Boundaries
Luis Barba, Otfried Cheong, Michael Gene Dobbins +8
Given a polygonal region containing a target point (which we assume is the origin), it is not hard to see that there are two points on the perimeter that are antipodal, that is, wh…
Simple strategies versus optimal schedules in multi-agent patrolling
Akitoshi Kawamura, Makoto Soejima
Suppose that a set of mobile agents, each with a predefined maximum speed, want to patrol a fence together so as to minimize the longest time interval during which a point on the f…
Fence patrolling by mobile agents with distinct speeds
Akitoshi Kawamura, Yusuke Kobayashi
Suppose we want to patrol a fence (line segment) using k mobile agents with given speeds v_1, ..., v_k so that every point on the fence is visited by an agent at least once in ever…
A lower bound on opaque sets
Akitoshi Kawamura, Sonoko Moriyama, Yota Otachi +1
It is proved that the total length of any set of countably many rectifiable curves, whose union meets all straight lines that intersect the unit square U, is at least 2.00002. This…
Function spaces for second-order polynomial time
Akitoshi Kawamura, Arno Pauly
In the context of second-order polynomial-time computability, we prove that there is no general function space construction. We proceed to identify restrictions on the domain or th…
Computational Complexity of Smooth Differential Equations
Akitoshi Kawamura, Hiroyuki Ota, Carsten Rösnick +1
The computational complexity of the solutions to the ordinary differential equation , under various assumptions on the function has been invest…
Morpion Solitaire 5D: a new upper bound of 121 on the maximum score
Akitoshi Kawamura, Takuma Okamoto, Yuichi Tatsu +2
Morpion Solitaire is a pencil-and-paper game for a single player. A move in this game consists of putting a cross at a lattice point and then drawing a line segment that passes thr…
Complexity Theory for Operators in Analysis
Akitoshi Kawamura, Stephen Cook
We propose an extension of the framework for discussing the computational complexity of problems involving uncountably many objects, such as real numbers, sets and functions, that…
Parameterized Uniform Complexity in Numerics: from Smooth to Analytic, from NP-hard to Polytime
Akitoshi Kawamura, Norbert Th. Müller, Carsten Rösnick +1
The synthesis of classical Computational Complexity Theory with Recursive Analysis provides a quantitative foundation to reliable numerics. Here the operators of maximization, inte…
Generalized Semimagic Squares for Digital Halftoning
Akitoshi Kawamura
Completing Aronov et al.'s study on zero-discrepancy matrices for digital halftoning, we determine all (m, n, k, l) for which it is possible to put mn consecutive integers on an m-…
Lipschitz Continuous Ordinary Differential Equations are Polynomial-Space Complete
Akitoshi Kawamura
In answer to Ko's question raised in 1983, we show that an initial value problem given by a polynomial-time computable, Lipschitz continuous function can have a polynomial-space co…
Distance k-Sectors Exist
Keiko Imai, Akitoshi Kawamura, Jiří Matoušek +2
The bisector of two nonempty sets P and Q in a metric space is the set of all points with equal distance to P and to Q. A distance k-sector of P and Q, where k is an integer, is a…
Zone Diagrams in Euclidean Spaces and in Other Normed Spaces
Akitoshi Kawamura, Jiří Matoušek, Takeshi Tokuyama
Zone diagram is a variation on the classical concept of a Voronoi diagram. Given n sites in a metric space that compete for territory, the zone diagram is an equilibrium state in t…
Differential Recursion and Differentially Algebraic Functions
Akitoshi Kawamura
Moore introduced a class of real-valued "recursive" functions by analogy with Kleene's formulation of the standard recursive functions. While his concise definition inspired a new…