Source author record

Hiro Ito

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Data Structures and Algorithms Computational Complexity Computational Geometry Computer Science and Game Theory math.CO

Catalog footprint

Research overview

6works

5topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2016arXiv

Single-Player and Two-Player Buttons & Scissors Games

We study the computational complexity of the Buttons \& Scissors game and obtain sharp thresholds with respect to several parameters. Specifically we show that the game is NP-complete for $C = 2$ colors but polytime solvable for $C = 1$ . Similarly the game is NP-complete if every color is used by at most $F = 4$ buttons but polytime solvable for $F \leq 3$ . We also consider restrictions on the board size, cut directions, and cut sizes. Finally, we introduce several natural two-player versions of the game and show that they are PSPACE-complete.

preprint2015arXiv

Every property is testable on a natural class of scale-free multigraphs

In this paper, we introduce a natural class of multigraphs called hierarchical-scale-free (HSF) multigraphs, and consider constant-time testability on the class. We show that a very wide subclass, specifically, that in which the power-law exponent is greater than two, of HSF is hyperfinite. Based on this result, an algorithm for a deterministic partitioning oracle can be constructed. We conclude by showing that every property is constant-time testable on the above subclass of HSF. This algorithm utilizes findings by Newman and Sohler of STOC'11. However, their algorithm is based on the bounded-degree model, while it is known that actual scale-free networks usually include hubs, which have a very large degree. HSF is based on scale-free properties and includes such hubs. This is the first universal result of constant-time testability on the general graph model, and it has the potential to be applicable on a very wide range of scale-free networks.

preprint2015arXiv

How to solve the cake-cutting problem in sublinear time

In this paper, we show algorithms for solving the cake-cutting problem in sublinear-time. More specifically, we preassign (simple) fair portions to o(n) players in o(n)-time, and minimize the damage to the rest of the players. All currently known algorithms require Omega(n)-time, even when assigning a portion to just one player, and it is nontrivial to revise these algorithms to run in $o(n)$ -time since many of the remaining players, who have not been asked any queries, may not be satisfied with the remaining cake. To challenge this problem, we begin by providing a framework for solving the cake-cutting problem in sublinear-time. Generally speaking, solving a problem in sublinear-time requires the use of approximations. However, in our framework, we introduce the concept of "eps n-victims," which means that eps n players (victims) may not get fair portions, where 0< eps =< 1 is an arbitrary constant. In our framework, an algorithm consists of the following two parts: In the first (Preassigning) part, it distributes fair portions to r < n players in o(n)-time. In the second (Completion) part, it distributes fair portions to the remaining n-r players except for the eps n victims in poly}(n)-time. There are two variations on the r players in the first part. Specifically, whether they can or cannot be designated. We will then present algorithms in this framework. In particular, an O(r/eps)-time algorithm for r =< eps n/127 undesignated players with eps n-victims, and an O~(r^2/eps)-time algorithm for r =< eps e^{sqrt{ln{n}}/{7}} designated players and eps =< 1/e with eps n-victims are presented.

preprint2014arXiv

Folding a Paper Strip to Minimize Thickness

In this paper, we study how to fold a specified origami crease pattern in order to minimize the impact of paper thickness. Specifically, origami designs are often expressed by a mountain-valley pattern (plane graph of creases with relative fold orientations), but in general this specification is consistent with exponentially many possible folded states. We analyze the complexity of finding the best consistent folded state according to two metrics: minimizing the total number of layers in the folded state (so that a "flat folding" is indeed close to flat), and minimizing the total amount of paper required to execute the folding (where "thicker" creases consume more paper). We prove both problems strongly NP-complete even for 1D folding. On the other hand, we prove the first problem fixed-parameter tractable in 1D with respect to the number of layers.

preprint2013arXiv

Cannibal Animal Games: a new variant of Tic-Tac-Toe

This paper presents a new partial two-player game, called the \emph{cannibal animal game}, which is a variant of Tic-Tac-Toe. The game is played on the infinite grid, where in each round a player chooses and occupies free cells. The first player Alice can occupy a cell in each turn and wins if she occupies a set of cells, the union of a subset of which is a translated, reflected and/or rotated copy of a previously agreed upon polyomino $P$ (called an \emph{animal}). The objective of the second player Bob is to prevent Alice from creating her animal by occupying in each round a translated, reflected and/or rotated copy of $P$ . An animal is a \emph{cannibal} if Bob has a winning strategy, and a \emph{non-cannibal} otherwise. This paper presents some new tools, such as the \emph{bounding strategy} and the \emph{punching lemma}, to classify animals into cannibals or non-cannibals. We also show that the \emph{pairing strategy} works for this problem.

preprint2011arXiv

Constant-Time Algorithms for Sparsity Matroids

A graph $G=(V,E)$ is called $(k,\ell)$ -full if $G$ contains a subgraph $H=(V,F)$ of $k|V|-\ell$ edges such that, for any non-empty $F' \subseteq F$ , $|F'| \leq k|V(F')| - \ell$ holds. Here, $V(F')$ denotes the set of vertices incident to $F'$ . It is known that the family of edge sets of $(k,\ell)$ -full graphs forms a family of matroid, known as the sparsity matroid of $G$ . In this paper, we give a constant-time approximation algorithm for the rank of the sparsity matroid of a degree-bounded undirected graph. This leads to a constant-time tester for $(k,\ell)$ -fullness in the bounded-degree model, (i.e., we can decide with high probability whether an input graph satisfies a property $P$ or far from $P$ ). Depending on the values of $k$ and $\ell$ , it can test various properties of a graph such as connectivity, rigidity, and how many spanning trees can be packed. Based on this result, we also propose a constant-time tester for $(k,\ell)$ -edge-connected-orientability in the bounded-degree model, where an undirected graph $G$ is called $(k,\ell)$ -edge-connected-orientable if there exists an orientation $\vec{G}$ of $G$ with a vertex $r \in V$ such that $\vec{G}$ contains $k$ arc-disjoint dipaths from $r$ to each vertex $v \in V$ and $\ell$ arc-disjoint dipaths from each vertex $v \in V$ to $r$ . A tester is called a one-sided error tester for $P$ if it always accepts a graph satisfying $P$ . We show, for $k \geq 2$ and (proper) $\ell \geq 0$ , any one-sided error tester for $(k,\ell)$ -fullness and $(k,\ell)$ -edge-connected-orientability requires $Ω(n)$ queries.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.