Osamu Watanabe
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Osamu Watanabe has a total of 130 co-authors. Here are the top co-authors by number of shared publications:
- Ricard Gavaldà
Universitat Politecnica de Catalunya, Barcelona, Spain
10 shared publications Carlos Domingo
Tokyo Institute of Technology
4 shared publicationsJin-Yi Cai
Computer Science Department, University of Wisconsin, Madison, WI 53706
4 shared publicationsJosé L. Balcázar
Univ. Politècnica de Catalunya Campus Nord
4 shared publicationsJohannes Köbler
3 shared publications- Josep Díaz
Universitat Politecnica de Catalunya
3 shared publications
Latest Publications
- Open Access
- 31 May 2023
- Published by Ali Institute of Research and Publication in Journal of Information Systems and Technology Research
- Vol. 2 (2) , 91-101
Analysis of Mobile-Based Archive Management Information System Design
Information technology has become a very common thing in today's society, therefore with the existence of fast and easy information technology it is expected to be able to process the desired information. At this time the existence of information systems presents a new innovation. The rapid development of information technology has penetrated into various sectors including offices. In the digital era, people are increasingly aware that communication technology is an important tool in dealing with the increasingly rapid flow of information. Information has developed and arrived in the digital era, one of which is information processing which has developed from conventional to digitally managed. As a memory center for organizations or agencies, letters are something important and need to be stored properly. But storage is still done conventionally, it will be difficult when you want to do a search. This study aims to design a mail archive information system using qualitative methods as a research method, UML as a system design that will facilitate the flow of research in designing systems and using a waterfall as a system development method. The results of this study are in the form of a design for a mail archive information system which is expected to be able to solve this problem.
- 31 May 2023
- Published by Ali Institute of Research and Publication in Journal of Information Systems and Technology Research
- Vol. 2 (2) , 91-101
Open AccessAnalysis of Mobile-Based Archive Management Information System Design
Information technology has become a very common thing in today's society, therefore with the existence of fast and easy information technology it is expected to be able to process the desired information. At this time the existence of information systems presents a new innovation. The rapid development of information technology has penetrated into various sectors including offices. In the digital era, people are increasingly aware that communication technology is an important tool in dealing with the increasingly rapid flow of information. Information has developed and arrived in the digital era, one of which is information processing which has developed from conventional to digitally managed. As a memory center for organizations or agencies, letters are something important and need to be stored properly. But storage is still done conventionally, it will be difficult when you want to do a search. This study aims to design a mail archive information system using qualitative methods as a research method, UML as a system design that will facilitate the flow of research in designing systems and using a waterfall as a system development method. The results of this study are in the form of a design for a mail archive information system which is expected to be able to solve this problem.
- 1 March 2022
- Published by Institute of Electronics, Information and Communications Engineers (IEICE) in IEICE Transactions on Information and Systems
- Vol. E105.D (3) , 481-490
An Improvement of the Biased-PPSZ Algorithm for the 3SAT Problem
Hansen, Kaplan, Zamir and Zwick (STOC 2019) introduced a systematic way to use “bias” for predicting an assignment to a Boolean variable in the process of PPSZ and showed that their biased PPSZ algorithm achieves a relatively large success probability improvement of PPSZ for Unique 3SAT. We propose an additional way to use “bias” and show by numerical analysis that the improvement gets increased further.
- 1 March 2022
- Published by Institute of Electronics, Information and Communications Engineers (IEICE) in IEICE Transactions on Information and Systems
- Vol. E105.D (3) , 481-490
An Improvement of the Biased-PPSZ Algorithm for the 3SAT Problem
Hansen, Kaplan, Zamir and Zwick (STOC 2019) introduced a systematic way to use “bias” for predicting an assignment to a Boolean variable in the process of PPSZ and showed that their biased PPSZ algorithm achieves a relatively large success probability improvement of PPSZ for Unique 3SAT. We propose an additional way to use “bias” and show by numerical analysis that the improvement gets increased further.
- Open Access
- 1 December 2020
- Published by FSAEIHE South Ural State University (National Research University) in Supercomputing Frontiers and Innovations
- Vol. 7 (4) , 4-15
Effects of Using a Memory Stalled Core for Handling MPI Communication Overlapping in the SOR Solver on SX-ACE and SX-Aurora TSUBASA
Modern high-performance computing (HPC) systems consist of a large number of nodes featuring multi-core processors. Many computational fluid dynamics (CFD) codes utilize a Message Passing Interface (MPI) to exploit the potential of such systems. In general, the MPI communication costs increase as the number of MPI processes increases. In this paper, we discuss performance of the code in which a core is used as a dedicated communication core when the core cannot contribute to the performance improvement due to memory-bandwidth limitations. By using the dedicated communication core, the communication operations are overlapped with computation operations, thus enabling highly efficient computation by exploiting the limited memory bandwidth and idle cores. The performance evaluation shows that this code can hide the MPI communication times of 90% on the supercomputer SX-ACE system and 80% on the supercomputer SX-Aurora TSUBASA system, and the performance of the successive over-relaxation (SOR) method is improved by 32% on SX-ACE and 20% on SX-Aurora TSUBASA.
- 1 December 2020
- Published by FSAEIHE South Ural State University (National Research University) in Supercomputing Frontiers and Innovations
- Vol. 7 (4) , 4-15
Open AccessEffects of Using a Memory Stalled Core for Handling MPI Communication Overlapping in the SOR Solver on SX-ACE and SX-Aurora TSUBASA
Modern high-performance computing (HPC) systems consist of a large number of nodes featuring multi-core processors. Many computational fluid dynamics (CFD) codes utilize a Message Passing Interface (MPI) to exploit the potential of such systems. In general, the MPI communication costs increase as the number of MPI processes increases. In this paper, we discuss performance of the code in which a core is used as a dedicated communication core when the core cannot contribute to the performance improvement due to memory-bandwidth limitations. By using the dedicated communication core, the communication operations are overlapped with computation operations, thus enabling highly efficient computation by exploiting the limited memory bandwidth and idle cores. The performance evaluation shows that this code can hide the MPI communication times of 90% on the supercomputer SX-ACE system and 80% on the supercomputer SX-Aurora TSUBASA system, and the performance of the successive over-relaxation (SOR) method is improved by 32% on SX-ACE and 20% on SX-Aurora TSUBASA.
- 29 October 2020
- Published by Springer Nature in computational complexity
- Vol. 29 (2) , 1-49
The Robustness of LWPP and WPP, with an Application to Graph Reconstruction
- 29 October 2020
- Published by Springer Nature in computational complexity
- Vol. 29 (2) , 1-49
The Robustness of LWPP and WPP, with an Application to Graph Reconstruction
- 21 February 2020
- Published by Springer Nature in Lecture Notes in Computer Science
- p. 67-79
On Nonadaptive Reductions to the Set of Random Strings and Its Dense Subsets
- 21 February 2020
- Published by Springer Nature in Lecture Notes in Computer Science
- p. 67-79
On Nonadaptive Reductions to the Set of Random Strings and Its Dense Subsets
- 20 February 2020
- Published by Springer Nature
- p. 15-21
Space Efficient Separator Algorithms for Planar Graphs
- 20 February 2020
- Published by Springer Nature
- p. 15-21
Space Efficient Separator Algorithms for Planar Graphs
- 1 September 2019
- Published by Institute of Electronics, Information and Communications Engineers (IEICE) in IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences
- Vol. E102.A (9) , 1007-1016
A Space-Efficient Separator Algorithm for Planar Graphs
Miller [9] proposed a linear-time algorithm for computing small separators for 2-connected planar graphs. We explain his algorithm and present a way to modify it to a space efficient version. Our algorithm can be regarded as a log-space reduction from the separator construction to the breadth first search tree construction.
- 1 September 2019
- Published by Institute of Electronics, Information and Communications Engineers (IEICE) in IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences
- Vol. E102.A (9) , 1007-1016
A Space-Efficient Separator Algorithm for Planar Graphs
Miller [9] proposed a linear-time algorithm for computing small separators for 2-connected planar graphs. We explain his algorithm and present a way to modify it to a space efficient version. Our algorithm can be regarded as a log-space reduction from the separator construction to the breadth first search tree construction.
- 1 July 2019
- Published by Elsevier in Discrete Applied Mathematics
- Vol. 265, 22-39
Polynomial size linear programs for problems in P
- 1 July 2019
- Published by Elsevier in Discrete Applied Mathematics
- Vol. 265, 22-39
Polynomial size linear programs for problems in P
- 29 November 2018
- Published by Elsevier in Theoretical Computer Science
- Vol. 806, 70-80
An improvement of the algorithm of Hertli for the unique 3SAT problem
- 29 November 2018
- Published by Elsevier in Theoretical Computer Science
- Vol. 806, 70-80
An improvement of the algorithm of Hertli for the unique 3SAT problem
- Open Access
Polynomial size linear programs for problems in P
A perfect matching in an undirected graph $G=(V,E)$ is a set of vertex disjoint edges from $E$ that include all vertices in $V$. The perfect matching problem is to decide if $G$ has such a matching. Recently Rothvo{\ss} proved the striking result that the Edmonds' matching polytope has exponential extension complexity. Here for each $n=|V|$ we describe a perfect matching polytope that is different from Edmonds' polytope and define a weaker notion of extended formulation. We show that the new polytope has a weak extended formulation (WEF) $Q$ of polynomial size. For each graph $G$ with $n$ vertices we can readily construct an objective function so that solving the resulting linear program over $Q$ decides whether or not $G$ has a perfect matching. The construction is uniform in the sense that, for each $n$, a single polytope is defined for the class of all graphs with $n$ nodes. The method extends to solve poly time optimization problems, such as the weighted matching problem. In this case a logarithmic (in the weight of the optimum solution) number of optimizations are made over the constructed WEF. The method described in the paper involves construction of a compiler that converts an algorithm given in a prescribed pseudocode into a polytope. It can therefore be used to construct a polytope for any decision problem in {\bf P} which can be solved by a given algorithm. Compared with earlier results of Dobkin-Lipton-Reiss and Valiant our method allows the construction of explicit linear programs directly from algorithms written for a standard register model, without intermediate transformations. We apply our results to obtain polynomial upper bounds on the non-negative rank of certain slack matrices related to membership testing of languages in {\bf P/Poly}.Open AccessPolynomial size linear programs for problems in P
A perfect matching in an undirected graph $G=(V,E)$ is a set of vertex disjoint edges from $E$ that include all vertices in $V$. The perfect matching problem is to decide if $G$ has such a matching. Recently Rothvo{\ss} proved the striking result that the Edmonds' matching polytope has exponential extension complexity. Here for each $n=|V|$ we describe a perfect matching polytope that is different from Edmonds' polytope and define a weaker notion of extended formulation. We show that the new polytope has a weak extended formulation (WEF) $Q$ of polynomial size. For each graph $G$ with $n$ vertices we can readily construct an objective function so that solving the resulting linear program over $Q$ decides whether or not $G$ has a perfect matching. The construction is uniform in the sense that, for each $n$, a single polytope is defined for the class of all graphs with $n$ nodes. The method extends to solve poly time optimization problems, such as the weighted matching problem. In this case a logarithmic (in the weight of the optimum solution) number of optimizations are made over the constructed WEF. The method described in the paper involves construction of a compiler that converts an algorithm given in a prescribed pseudocode into a polytope. It can therefore be used to construct a polytope for any decision problem in {\bf P} which can be solved by a given algorithm. Compared with earlier results of Dobkin-Lipton-Reiss and Valiant our method allows the construction of explicit linear programs directly from algorithms written for a standard register model, without intermediate transformations. We apply our results to obtain polynomial upper bounds on the non-negative rank of certain slack matrices related to membership testing of languages in {\bf P/Poly}.