VLDB 2026 Research / reviewers in the wild / expert
Keiji Matsumoto
dblp:73/479
· DBLP profile ↗
13ranked-venue papers
1as first author
1since 2021 · last 2024
0000-0002-9957-8042ORCID · corroborated
Domains — the database's venue-derived domains; a paper can count in several
Theory of computation · 9Applied, interdisciplinary, general and emerging computing · 2 · 1 first-authorSystems, architecture and hardware · 1Software engineering, systems software and programming languages · 1 · 1 since 2021
Expertise — from the expertise taxonomy: the topics of the expert's papers under the CCF categories. A weight counts papers with recency: 1 for a paper about the topic, 0.3 when the topic is its context, halved every five years.
| Theoretical computer science
5 papers |
Quantum computing and quantum information · 33% Mathematical optimization · 32% Computational complexity · 24% |
Topics — the 15 heaviest of 15, each with the papers that count most for it
| Topic | Weight | Papers | Last | Evidence papers |
|---|---|---|---|---|
Mathematical optimization
integer programming |
0.2 | 3 | 2011 | Entangled Games Are Hard to Approximate · SIAM J. Comput. 2011 Using Entanglement in Quantum Multi-prover Interactive Proofs · CCC 2008 Oracularization and Two-Prover One-Round Interactive Proofs against Nonlocal Strategies · CCC 2009 |
Computational complexity
hardness of approximation |
0.2 | 2 | 2011 | Entangled Games Are Hard to Approximate · SIAM J. Comput. 2011 Entangled Games are Hard to Approximate · FOCS 2008 |
Quantum computing and quantum information › quantum games
nonlocal games |
0.2 | 2 | 2011 | Entangled Games Are Hard to Approximate · SIAM J. Comput. 2011 Entangled Games are Hard to Approximate · FOCS 2008 |
Mathematical optimization › integer programming
quantum interactive proofs |
0.2 | 2 | 2009 | Oracularization and Two-Prover One-Round Interactive Proofs against Nonlocal Strategies · CCC 2009 Using Entanglement in Quantum Multi-prover Interactive Proofs · CCC 2008 |
Distributed computing theory › distributed algorithms
anonymous networks |
0.1 | 1 | 2009 | Brief announcement: exactly electing a unique leader is not harder than computing symmetric functions on anonymous quantum networks · PODC 2009 |
Distributed computing theory
leader election |
0.1 | 1 | 2009 | Brief announcement: exactly electing a unique leader is not harder than computing symmetric functions on anonymous quantum networks · PODC 2009 |
Mathematical optimization › integer programming
multi-prover interactive proofs |
0.1 | 1 | 2009 | Oracularization and Two-Prover One-Round Interactive Proofs against Nonlocal Strategies · CCC 2009 |
Quantum computing and quantum information › quantum network
quantum distributed computing |
0.1 | 1 | 2009 | Brief announcement: exactly electing a unique leader is not harder than computing symmetric functions on anonymous quantum networks · PODC 2009 |
Computational complexity › boolean function analysis
symmetric functions |
0.1 | 1 | 2009 | Brief announcement: exactly electing a unique leader is not harder than computing symmetric functions on anonymous quantum networks · PODC 2009 |
Computational complexity › probabilistically checkable proofs
parallel repetition |
0.1 | 1 | 2008 | Using Entanglement in Quantum Multi-prover Interactive Proofs · CCC 2008 |
Quantum computing and quantum information
quantum entanglement |
0.1 | 1 | 2008 | Using Entanglement in Quantum Multi-prover Interactive Proofs · CCC 2008 |
Quantum computing and quantum information
quantum games |
0.1 | 1 | 2008 | Entangled Games are Hard to Approximate · FOCS 2008 |
Quantum computing and quantum information › quantum complexity theory
quantum multi-prover interactive proof |
0.1 | 1 | 2008 | Using Entanglement in Quantum Multi-prover Interactive Proofs · CCC 2008 |
Computational complexity › complexity classes
polynomial hierarchy |
0.0 | 1 | 2009 | Oracularization and Two-Prover One-Round Interactive Proofs against Nonlocal Strategies · CCC 2009 |
Mathematical optimization
semidefinite programming |
0.0 | 1 | 2008 | Entangled Games are Hard to Approximate · FOCS 2008 |
Methods — techniques the papers use, named apart from their topics
semidefinite programming · 0.1rounding · 0.1inapproximability reduction · 0.1quantum algorithm design · 0.1oracularization · 0.1no-signaling strategies · 0.1complexity analysis · 0.1public-coin protocol · 0.1inapproximability bounds · 0.1entanglement · 0.1
| Year | Publication | Venue | Position |
|---|---|---|---|
| 2024 | Quantitative Analysis of Conversational Response Nuances Using Visual Analog Scale, Data Visualization, and ClusteringabstractThe quantification and analysis of conversational nuances is a complex and demanding task in the fields of natural language processing and human-computer interaction. In this paper, a novel method for measuring and examining subtle differences in conversational responses is proposed, utilizing the Visual Analog Scale (VAS). Participants were presented with a hypothetical chat scenario and asked to rate their willingness to attend an event based on six distinct reply options using the VAS. The collected data were analyzed using descriptive statistics, data visualization techniques such as violin plots, box plots, bee swarm plots, and hierarchical clustering. The study uncovered significant disparities in participants' responses, as certain answer options yielded greater levels of commitment than others. Using cluster analysis, distinct groups of participants were delineated based on their response tendencies. The integration of VAS, informative visualization techniques, and clustering facilitated a comprehensive, quantitative comprehension of the intricate variations in conversational replies, even with a small sample size. Naruki Shirahama, Shinichi Kondo, Keiji Matsumoto, Kenji Moriya, Naofumi Nakaya, Kazuhiro Koshi, Satoshi Watanabe |
SERA | 3 |
| 2017 | Internet of the body and cognitive companion: Enabling high-quality monitoring of patients at homeabstractWearables that continuously acquire vital and other medically relevant parameters facilitate treatment optimizations for individual patients and reduce the duration of hospitalizations - thus improving the patients' quality of life. To accomplish this, we demonstrate a scalable architecture that connects wearables through a hub to the cloud, combines edge and cloud computing to provide optimal user interaction, and allows analytics on multi-stream data from those connected devices. Rahel Straessle, Yuksel Temiz, Sebastian Gerke, Jonas R. M. Weiss, Arvind Sridhar, Stephan Paredes, Thomas Brunschwiler, Emanuel Loertscher, Neil Ebejer, Bruno Michel, Theodore G. van Kessel, Ismael Faro, Sufi Zafar, Frank Libsch, Marc A. Taubenblatt, Keiji Matsumoto |
Healthcom | 16 |
| 2011 | Entangled Games Are Hard to ApproximateabstractWe establish the first hardness results for the problem of computing the value of one-round games played by a verifier and a team of provers who can share quantum entanglement. In particular, we show that it is NP-hard to approximate within an inverse polynomial the value of a one-round game with (i) a quantum verifier and two entangled provers or (ii) a classical verifier and three entangled provers. Previously it was not even known if computing the value exactly is NP-hard. We also describe a mathematical conjecture, which, if true, would imply hardness of approximation of entangled-prover games to within a constant. Using our techniques we also show that every language in PSPACE has a two-prover one-round interactive proof system with perfect completeness and soundness $1-1/\,\mathrm{poly}$ even against entangled provers. We start our proof by describing two ways to modify classical multiprover games to make them resistant to entangled provers. We then show that a strategy for the modified game that uses entanglement can be “rounded” to one that does not. The results then follow from classical inapproximability bounds. Our work implies that, unless $\mathrm{P}=\mathrm{NP}$, the values of entangled-prover games cannot be computed by semidefinite programs that are polynomial in the size of the verifier's system, a method that has been successful for more restricted quantum games. Julia Kempe, Hirotada Kobayashi, Keiji Matsumoto, Ben Toner, Thomas Vidick |
SIAM J. Comput. | 3 |
| 2009 | Oracularization and Two-Prover One-Round Interactive Proofs against Nonlocal StrategiesabstractThis paper presents three results on the power of two-prover one-round interactive proof systems based on oracularization under the existence of prior entanglement between dishonest provers. It is proved that the two-prover one-round interactive proof system for PSPACE by Cai, Condon, and Lipton [JCSS 48:183-193, 1994] still achieves exponentially small soundness error in the existence of prior entanglement between dishonest provers (and more strongly, even if dishonest provers are allowed to use arbitrary no-signaling strategies). It follows that, unless the polynomial-time hierarchy collapses to the second level, two-prover systems are still advantageous to single-prover systems even when only malicious provers can use quantum information. It is also shown that a "dummy" question may be helpful when constructing an entanglement-resistant multi-prover system via oracularization. This affirmatively settles a question posed by Kempe et al. [FOCS 2008, pp. 447-456] and every language in NEXP is proved to have a two-prover one-round interactive proof system even against entangled provers, albeit with exponentially small gap between completeness and soundness. In other words, it is NP-hard to approximate within an inverse-polynomial the value of a classical two-prover one-round game against entangled provers. Finally, both for the above proof system for NEXP and for the quantum two-prover one-round proof system for NEXP proposed by Kempe et al., it is proved that exponentially small completeness-soundness gaps are best achievable unless soundness analysis uses the structure of the underlying system with unentangled provers. Tsuyoshi Ito, Hirotada Kobayashi, Keiji Matsumoto |
CCC | 3 |
| 2009 | Brief announcement: exactly electing a unique leader is not harder than computing symmetric functions on anonymous quantum networksabstractThis paper proves that, if quantum communication and computation are available and the number of parties is given, the leader election problem can exactly (i.e., without error in bounded time) be solved with at most the same complexity up to a constant factor as that of computing certain symmetric functions on an anonymous network of any unknown topology. Together with a novel quantum algorithm that computes a certain symmetric function, this characterization yields a quantum leader election algorithm that is more efficient than existing algorithms. Hirotada Kobayashi, Keiji Matsumoto, Seiichiro Tani |
PODC | 2 |
| 2009 | Using Entanglement in Quantum Multi-Prover Interactive Proofs
Julia Kempe, Hirotada Kobayashi, Keiji Matsumoto, Thomas Vidick |
Comput. Complex. | 3 |
| 2008 | Using Entanglement in Quantum Multi-prover Interactive ProofsabstractThe central question in quantum multi-prover interactive proof systems is whether or not entanglement shared among provers affects the verification power of the proof system. We study for the first time positive aspects of prior entanglement and show how it can be used to parallelize any multi- prover quantum interactive proof system to a one-round system with perfect completeness, soundness bounded away from 1 by an inverse polynomial in the input size, and one extra proven Alternatively, we can also parallelize to a three-turn system with the same number of provers, where the verifier only broadcasts the outcome of a coin flip. This "public-coin" property is somewhat surprising, since in the classical case public-coin multi-prover interactive proofs are equivalent to single prover ones. Julia Kempe, Hirotada Kobayashi, Keiji Matsumoto, Thomas Vidick |
CCC | 3 |
| 2008 | Entangled Games are Hard to ApproximateabstractWe establish the first hardness results for the problem of computing the value of one-round games played by a referee and a team of players who can share quantum entanglement. In particular, we show that it is NP-hard to approximate within an inverse polynomial the value of a one-round game with (i) quantum referee and two entangled players or (ii) classical referee and three entangled players. Previously it was not even known if computing the value exactly is NP-hard. We also describe a mathematical conjecture, which, if true, would imply hardness of approximation to within a constant.We start our proof by describing two ways to modify classical multi-player games to make them resistant to entangled players. We then show that a strategy for the modified game that uses entanglement can be "rounded'' to one that does not. The results then follow from classical inapproximability bounds. Our work implies that, unless P = NP, the values of entangled-player games cannot be computed by semidefinite programs that are polynomial in the size of the referee's system, a method that has been successful for more restricted quantum games. Julia Kempe, Hirotada Kobayashi, Keiji Matsumoto, Ben Toner, Thomas Vidick |
FOCS | 3 |
| 2005 | Exact Quantum Algorithms for the Leader Election Problem
Seiichiro Tani, Hirotada Kobayashi, Keiji Matsumoto |
STACS | 3 |
| 2004 | Universal distortion-free entanglement concentrationabstractThis paper proposes a universal distortion-free entanglement concentration protocol. The proposed protocol uses only local operations and no classical communication, but still achieves optimality in such strong senses Keiji Matsumoto, Masahito Hayashi |
ISIT | 1 |
| 2003 | Quantum Merlin-Arthur Proof Systems: Are Multiple Merlins More Helpful to Arthur?
Hirotada Kobayashi, Keiji Matsumoto, Tomoyuki Yamakami |
ISAAC | 2 |
| 2003 | Quantum multi-prover interactive proof systems with limited prior entanglement
Hirotada Kobayashi, Keiji Matsumoto |
J. Comput. Syst. Sci. | 2 |
| 2002 | Quantum Multi-prover Interactive Proof Systems with Limited Prior Entanglement
Hirotada Kobayashi, Keiji Matsumoto |
ISAAC | 2 |