Hajime Tanaka
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Hajime Tanaka has a total of 28 co-authors. Here are the top co-authors by number of shared publications:
- Etsuko Bannai
Itoshima-shi, Japan
5 shared publications - Eiichi Bannai
Faculty of Mathematics, Kyushu University (emeritus)
4 shared publications - Norihide Tokushige
College of Education, Ryukyu University, Nishihara, Japan
4 shared publications Chin-Yen Lee
Department of Mathematics, National Central University
2 shared publications- Ferdinand Ihringer
Univ Ghent, Dept Math Anal Logic & Discrete Math, Ghent, Belgium
2 shared publications - John Vincent S. Morales
Department of Mathematics and Statistics, College of Science, De La Salle University, Manila, Philippines
2 shared publications
Latest Publications
- Open Access
Burning numbers via eigenpolytopes -- Hamming graphs, Johnson graphs, and halved cubes
We give lower and upper bounds on the burning number of Hamming graphs, Johnson graphs, and halved cube graphs. For the lower bounds, we use the fact that $1$-skeletons of the eigenpolytopes of these graphs are isomorphic to the original graphs. Then, we present a dynamic search algorithm performed on the eigenpolytope to find an unburned vertex. This idea was originally used by Alon (Discrete Appl.\ Math.,\ 1992), who determined the burning number of the hypercube graphs.
Open AccessBurning numbers via eigenpolytopes -- Hamming graphs, Johnson graphs, and halved cubes
We give lower and upper bounds on the burning number of Hamming graphs, Johnson graphs, and halved cube graphs. For the lower bounds, we use the fact that $1$-skeletons of the eigenpolytopes of these graphs are isomorphic to the original graphs. Then, we present a dynamic search algorithm performed on the eigenpolytope to find an unburned vertex. This idea was originally used by Alon (Discrete Appl.\ Math.,\ 1992), who determined the burning number of the hypercube graphs.
- 29 March 2025
- Published by Elsevier in European Journal of Combinatorics
- Vol. 127
Extremal problems for intersecting families of subspaces with a measure
- 29 March 2025
- Published by Elsevier in European Journal of Combinatorics
- Vol. 127
Extremal problems for intersecting families of subspaces with a measure
- Open Access
A semidefinite programming approach to cross $2$-intersecting families
Let $k\geq 2$ and $n\geq 3(k-1)$. Let $\mathcal{F}$ and $\mathcal{G}$ be families of $k$-element subsets of an $n$-element set. Suppose that $|F\cap G|\geq 2$ for all $F\in\mathcal{F}$ and $G\in\mathcal{G}$. We show that $|\mathcal{F}||\mathcal{G}|\leq\binom{n-2}{k-2}^2$, and determine the extremal configurations. This settles the last unsolved case of a recent result by Zhang and Wu (J. Combin. Theory Ser. B, 2025). We also obtain the corresponding result in the product measure setting. Our proof is done by solving semidefinite programming problems.Open AccessA semidefinite programming approach to cross $2$-intersecting families
Let $k\geq 2$ and $n\geq 3(k-1)$. Let $\mathcal{F}$ and $\mathcal{G}$ be families of $k$-element subsets of an $n$-element set. Suppose that $|F\cap G|\geq 2$ for all $F\in\mathcal{F}$ and $G\in\mathcal{G}$. We show that $|\mathcal{F}||\mathcal{G}|\leq\binom{n-2}{k-2}^2$, and determine the extremal configurations. This settles the last unsolved case of a recent result by Zhang and Wu (J. Combin. Theory Ser. B, 2025). We also obtain the corresponding result in the product measure setting. Our proof is done by solving semidefinite programming problems. - Open Access
- 18 December 2024
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Quantum Computing
- Vol. 5 (4) , 1-20
Multimarked Spatial Search by Continuous-Time Quantum Walk
The quantum-walk-based spatial search problem aims to find a marked vertex using a quantum walk on a graph with marked vertices. We describe a framework for determining the computational complexity of spatial search by continuous-time quantum walk on arbitrary graphs by providing a recipe for finding the optimal running time and the success probability of the algorithm. The quantum walk is driven by a Hamiltonian derived from the adjacency matrix of the graph modified by the presence of the marked vertices. The success of our framework depends on the knowledge of the eigenvalues and eigenvectors of the adjacency matrix. The spectrum of the Hamiltonian is subsequently obtained from the roots of the determinant of a real symmetric matrix M , the dimensions of which depend on the number of marked vertices. The eigenvectors are determined from a basis of the kernel of M . We show each step of the framework by solving the spatial searching problem on the Johnson graphs with a fixed diameter and with two marked vertices. Our calculations show that the optimal running time is \(O(\sqrt {N})\) with an asymptotic probability of 1+ o (1), where N is the number of vertices.- 18 December 2024
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Quantum Computing
- Vol. 5 (4) , 1-20
Open AccessMultimarked Spatial Search by Continuous-Time Quantum Walk
The quantum-walk-based spatial search problem aims to find a marked vertex using a quantum walk on a graph with marked vertices. We describe a framework for determining the computational complexity of spatial search by continuous-time quantum walk on arbitrary graphs by providing a recipe for finding the optimal running time and the success probability of the algorithm. The quantum walk is driven by a Hamiltonian derived from the adjacency matrix of the graph modified by the presence of the marked vertices. The success of our framework depends on the knowledge of the eigenvalues and eigenvectors of the adjacency matrix. The spectrum of the Hamiltonian is subsequently obtained from the roots of the determinant of a real symmetric matrix M , the dimensions of which depend on the number of marked vertices. The eigenvectors are determined from a basis of the kernel of M . We show each step of the framework by solving the spatial searching problem on the Johnson graphs with a fixed diameter and with two marked vertices. Our calculations show that the optimal running time is \(O(\sqrt {N})\) with an asymptotic probability of 1+ o (1), where N is the number of vertices. - Open Access
- 24 October 2024
- Published by The Institute for Research and Community Services (LPPM) ITB in Electronic Journal of Graph Theory and Applications
- Vol. 12 (2) , 329-341
The real equiangular tight frames obtained from rank 3 graphs
The real equiangular tight frames obtained from rank 3 graphs
- 24 October 2024
- Published by The Institute for Research and Community Services (LPPM) ITB in Electronic Journal of Graph Theory and Applications
- Vol. 12 (2) , 329-341
Open AccessThe real equiangular tight frames obtained from rank 3 graphs
The real equiangular tight frames obtained from rank 3 graphs
- Open Access
- 9 April 2024
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Graphics
- Vol. 43 (3) , 1-18
Online Neural Path Guiding with Normalized Anisotropic Spherical Gaussians
Importance sampling techniques significantly reduce variance in physically based rendering. In this article, we propose a novel online framework to learn the spatial-varying distribution of the full product of the rendering equation, with a single small neural network using stochastic ray samples. The learned distributions can be used to efficiently sample the full product of incident light. To accomplish this, we introduce a novel closed-form density model, called the Normalized Anisotropic Spherical Gaussian mixture, that can model a complex light field with a small number of parameters and that can be directly sampled. Our framework progressively renders and learns the distribution, without requiring any warm-up phases. With the compact and expressive representation of our density model, our framework can be implemented entirely on the GPU, allowing it to produce high-quality images with limited computational resources. The results show that our framework outperforms existing neural path guiding approaches and achieves comparable or even better performance than state-of-the-art online statistical path guiding techniques.
- 9 April 2024
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Graphics
- Vol. 43 (3) , 1-18
Open AccessOnline Neural Path Guiding with Normalized Anisotropic Spherical Gaussians
Importance sampling techniques significantly reduce variance in physically based rendering. In this article, we propose a novel online framework to learn the spatial-varying distribution of the full product of the rendering equation, with a single small neural network using stochastic ray samples. The learned distributions can be used to efficiently sample the full product of incident light. To accomplish this, we introduce a novel closed-form density model, called the Normalized Anisotropic Spherical Gaussian mixture, that can model a complex light field with a small number of parameters and that can be directly sampled. Our framework progressively renders and learns the distribution, without requiring any warm-up phases. With the compact and expressive representation of our density model, our framework can be implemented entirely on the GPU, allowing it to produce high-quality images with limited computational resources. The results show that our framework outperforms existing neural path guiding approaches and achieves comparable or even better performance than state-of-the-art online statistical path guiding techniques.
- Open AccessThe real equiangular tight frames obtained from rank $3$ graphsWe present all nontrivial real equiangular tight frames $\{\varphi_m\}_{m=1}^M$ in $\mathbb{R}^N$ obtained as spherical embeddings of primitive rank $3$ graphs on $M$ vertices, and those such that one of their associated $M$ strongly regular graphs on $M-1$ vertices is a primitive rank $3$ graph.Open AccessThe real equiangular tight frames obtained from rank $3$ graphsWe present all nontrivial real equiangular tight frames $\{\varphi_m\}_{m=1}^M$ in $\mathbb{R}^N$ obtained as spherical embeddings of primitive rank $3$ graphs on $M$ vertices, and those such that one of their associated $M$ strongly regular graphs on $M-1$ vertices is a primitive rank $3$ graph.
- 21 April 2023
- Published by Elsevier in Linear Algebra and its Applications
- Vol. 671, 59-66
Characterizing graphs with fully positive semidefinite Q-matrices
- 21 April 2023
- Published by Elsevier in Linear Algebra and its Applications
- Vol. 671, 59-66
Characterizing graphs with fully positive semidefinite Q-matrices
- Open Access
Characterizing graphs with fully positive semidefinite $Q$-matrices
For $q\in\mathbb{R}$, the $Q$-matrix $Q=Q_q$ of a connected simple graph $G=(V,E)$ is $Q_q=(q^{\partial(x,y)})_{x,y\in V}$, where $\partial$ denotes the path-length distance. Describing the set $\pi(G)$ consisting of those $q\in \mathbb{R}$ for which $Q_q$ is positive semidefinite is fundamental in asymptotic spectral analysis of graphs from the viewpoint of quantum probability theory. Assume that $G$ has at least two vertices. Then $\pi(G)$ is easily seen to be a nonempty closed subset of the interval $[-1,1]$. In this note, we show that $\pi(G)=[-1,1]$ if and only if $G$ is isometrically embeddable into a hypercube (infinite-dimensional if $G$ is infinite) if and only if $G$ is bipartite and does not possess certain five-vertex configurations, an example of which is an induced $K_{2,3}$.Open AccessCharacterizing graphs with fully positive semidefinite $Q$-matrices
For $q\in\mathbb{R}$, the $Q$-matrix $Q=Q_q$ of a connected simple graph $G=(V,E)$ is $Q_q=(q^{\partial(x,y)})_{x,y\in V}$, where $\partial$ denotes the path-length distance. Describing the set $\pi(G)$ consisting of those $q\in \mathbb{R}$ for which $Q_q$ is positive semidefinite is fundamental in asymptotic spectral analysis of graphs from the viewpoint of quantum probability theory. Assume that $G$ has at least two vertices. Then $\pi(G)$ is easily seen to be a nonempty closed subset of the interval $[-1,1]$. In this note, we show that $\pi(G)=[-1,1]$ if and only if $G$ is isometrically embeddable into a hypercube (infinite-dimensional if $G$ is infinite) if and only if $G$ is bipartite and does not possess certain five-vertex configurations, an example of which is an induced $K_{2,3}$. - Open Access
- 1 June 2022
- Published by IOP Publishing in Journal of Physics A: Mathematical and Theoretical
- Vol. 55 (25) , 255304
Spatial search on Johnson graphs by discrete-time quantum walk
The spatial search problem aims to find a marked vertex of a finite graph using a dynamic with two constraints: (1) the walker has no compass and (2) the walker can check whether a vertex is marked only after reaching it. This problem is a generalization of unsorted database search and has many applications to algorithms. Classical algorithms that solve the spatial search problem are based on random walks and the computational complexity is determined by the hitting time. On the other hand, quantum algorithms are based on quantum walks and the computational complexity is determined not only by the number of steps to reach a marked vertex, but also by the success probability, since we need to perform a measurement at the end of the algorithm to determine the walker’s position. In this work, we address the spatial search problem on Johnson graphs using the coined quantum walk model. Since Johnson graphs are vertex- and distance-transitive, we have found an invariant subspace of the Hilbert space, which aids in the calculation of the computational complexity. We have shown that, for every fixed diameter, the asymptotic success probability is 1/2 after taking π N / ( 2 2 ) steps, where N is the number of vertices of the Johnson graph.
- 1 June 2022
- Published by IOP Publishing in Journal of Physics A: Mathematical and Theoretical
- Vol. 55 (25) , 255304
Open AccessSpatial search on Johnson graphs by discrete-time quantum walk
The spatial search problem aims to find a marked vertex of a finite graph using a dynamic with two constraints: (1) the walker has no compass and (2) the walker can check whether a vertex is marked only after reaching it. This problem is a generalization of unsorted database search and has many applications to algorithms. Classical algorithms that solve the spatial search problem are based on random walks and the computational complexity is determined by the hitting time. On the other hand, quantum algorithms are based on quantum walks and the computational complexity is determined not only by the number of steps to reach a marked vertex, but also by the success probability, since we need to perform a measurement at the end of the algorithm to determine the walker’s position. In this work, we address the spatial search problem on Johnson graphs using the coined quantum walk model. Since Johnson graphs are vertex- and distance-transitive, we have found an invariant subspace of the Hilbert space, which aids in the calculation of the computational complexity. We have shown that, for every fixed diameter, the asymptotic success probability is 1/2 after taking π N / ( 2 2 ) steps, where N is the number of vertices of the Johnson graph.