Committee |
Date Time |
Place |
Paper Title / Authors |
Abstract |
Paper # |
COMP |
2023-03-02 15:15 |
Tokyo |
Ochanomizu University |
When Input Integers are Given in the Unary Numeral Representation
-- (Preliminary Report) -- Tomoyuki Yamakami (U of Fukui) COMP2022-37 |
Many NP-complete problems take integers as part of their input instances. These input integers are given in general in t... [more] |
COMP2022-37 pp.21-27 |
WBS, IT, ISEC |
2021-03-04 11:45 |
Online |
Online |
Streaming Data Compression and Decompression by One-Way Quantum Finite-State Automata, Leading to Quantum Finite-State Deep and Shallow Information (Preliminary Report) Tomoyuki Yamakami (U of Fukui) IT2020-117 ISEC2020-47 WBS2020-36 |
The logical depth of a piece of data has served as a complexity measure to
describe the amount of “useful” and "non-ran... [more] |
IT2020-117 ISEC2020-47 WBS2020-36 pp.31-36 |
COMP, IPSJ-AL |
2020-09-02 11:30 |
Online |
Online |
What Restrictions Naturally Allow Well-Known NP-Complete Problems to Yield NL-Completeness and the Linear Space Hypothesis? Tomoyuki Yamakami (U of Fukui) COMP2020-10 |
Many practical combinatorial problems have been shown to be NP-complete or NP-hard. To cope with further real-life situa... [more] |
COMP2020-10 pp.33-40 |
COMP |
2020-03-01 16:25 |
Tokyo |
The University of Electro-Communications (Cancelled but technical report was issued) |
Synchronizing Pushdown Automata and Reset Words Eitatsu Mikami, Tomoyuki Yamakami (Univ. Fukui) COMP2019-54 |
[more] |
COMP2019-54 pp.57-63 |
COMP |
2019-12-13 16:25 |
Gunma |
Ikaho Seminar House, Gunma University |
Limited Deterministic Automata and Pumping Lemma Kosei Yoshida, Tomoyuki Yamakami (U of Fukui) COMP2019-41 |
This pape, introduced a pumping lemma for languages recognizable by limited deterministic automata. We use this lemma to... [more] |
COMP2019-41 pp.85-92 |
QIT (2nd) |
2018-11-26 09:50 |
Tokyo |
The University of Tokyo |
Non-Uniform State Complexity of Quantum Finite Automata and Quantum Polynomial-Time Logarithmic-Space Computation with Quantum Advice
-- (Preliminary Report) -- Tomoyuki Yamakami (U of Fukui) |
The state complexity of a finite(-state) automaton intuitively measures the size of the description of the automaton. Sa... [more] |
|
COMP |
2014-10-08 10:50 |
Tokyo |
Chuo University |
The State Complexity of Two-Way Quantum Finite Automata Marcos Villagra, Tomoyuki Yamakami (Univ. of Fukui) COMP2014-26 |
[more] |
COMP2014-26 pp.5-8 |
COMP |
2014-09-02 14:45 |
Aichi |
Toyohashi University of Technology |
The World of Combinatorial Fuzzy Problems and the Efficiency of Fuzzy Approximation Algorithms
-- Preliminary Report -- Tomoyuki Yamakami (Univ. of Fukui) COMP2014-20 |
We re-examine a practical aspect of combinatorial fuzzy problems of various types, including search, counting, optimizat... [more] |
COMP2014-20 pp.35-42 |
COMP |
2013-10-18 15:50 |
Aichi |
Nagoya Institute of Technology |
Constant-Space Zero-Knowledge Proofs Systems with One-Way Quantum Verifiers
-- Preliminary Report -- Marcos Villagra, Tomoyuki Yamakami (Univ. of Fukui) COMP2013-36 |
We discuss the notion of quantum zero-knowledge proof systems whose memory-limited verifiers
receive a stream of classi... [more] |
COMP2013-36 pp.23-24 |
COMP |
2013-09-03 11:20 |
Tottori |
|
Oracle Pushdown Automata, Nondeterministic Reducibilities, and the Hierarchy over the Family of Context-Free Languages
-- (Preliminary Version) -- Tomoyuki Yamakami (Univ. of Fukui) COMP2013-27 |
We impose various oracle mechanisms on nondeterministic pushdown automata, which naturally induce nondeterministic reduc... [more] |
COMP2013-27 pp.17-24 |
COMP |
2009-09-14 10:40 |
Tottori |
Tottori University of Environmental Studies |
The Roles of Advice to One-Tape Linear-Time Turing Machines and Finite Automata Tomoyuki Yamakami (Univ. of Fukui.) COMP2009-25 |
We discuss the power and limitation of various "advice," when it is given particularly to weak computational models of o... [more] |
COMP2009-25 pp.1-8 |
COMP |
2005-03-18 09:25 |
Tokyo |
Tokyo Institute of Technology |
A General Construction of Hard-Core Predicates for Any Quantum One-Way Function Akinori Kawachi (Tokyo Inst. Tech.), Tomoyuki Yamakami (Trent Univ.) |
We propose a general construction of hard-core predicates for any quantum one-way function in this paper. Our constructi... [more] |
COMP2004-74 pp.9-16 |