Keiji Matsumoto

dblp:73/479 · DBLP profile ↗
← Back
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

TopicWeightPapersLastEvidence papers
Mathematical optimization
integer programming
0.232011
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.222011
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.222011
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.222009
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.112009
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.112009
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.112009
Oracularization and Two-Prover One-Round Interactive Proofs against Nonlocal Strategies · CCC 2009
Quantum computing and quantum information › quantum network
quantum distributed computing
0.112009
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.112009
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.112008
Using Entanglement in Quantum Multi-prover Interactive Proofs · CCC 2008
Quantum computing and quantum information
quantum entanglement
0.112008
Using Entanglement in Quantum Multi-prover Interactive Proofs · CCC 2008
Quantum computing and quantum information
quantum games
0.112008
Entangled Games are Hard to Approximate · FOCS 2008
Quantum computing and quantum information › quantum complexity theory
quantum multi-prover interactive proof
0.112008
Using Entanglement in Quantum Multi-prover Interactive Proofs · CCC 2008
Computational complexity › complexity classes
polynomial hierarchy
0.012009
Oracularization and Two-Prover One-Round Interactive Proofs against Nonlocal Strategies · CCC 2009
Mathematical optimization
semidefinite programming
0.012008
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
YearPublicationVenuePosition
2024 Quantitative Analysis of Conversational Response Nuances Using Visual Analog Scale, Data Visualization, and Clustering
abstract
The 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
SERA3
2017 Internet of the body and cognitive companion: Enabling high-quality monitoring of patients at home
abstract
Wearables 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
Healthcom16
2011 Entangled Games Are Hard to Approximate
abstract
We 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 Strategies
abstract
This 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
CCC3
2009 Brief announcement: exactly electing a unique leader is not harder than computing symmetric functions on anonymous quantum networks
abstract
This 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
PODC2
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 Proofs
abstract
The 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
CCC3
2008 Entangled Games are Hard to Approximate
abstract
We 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
FOCS3
2005 Exact Quantum Algorithms for the Leader Election Problem
Seiichiro Tani, Hirotada Kobayashi, Keiji Matsumoto
STACS3
2004 Universal distortion-free entanglement concentration
abstract
This 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
ISIT1
2003 Quantum Merlin-Arthur Proof Systems: Are Multiple Merlins More Helpful to Arthur?
Hirotada Kobayashi, Keiji Matsumoto, Tomoyuki Yamakami
ISAAC2
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
ISAAC2