Committee 
Date Time 
Place 
Paper Title / Authors 
Abstract 
Paper # 
COMP 
20230302 15:15 
Tokyo 
Ochanomizu University 
When Input Integers are Given in the Unary Numeral Representation
 (Preliminary Report)  Tomoyuki Yamakami (U of Fukui) COMP202237 
Many NPcomplete problems take integers as part of their input instances. These input integers are given in general in t... [more] 
COMP202237 pp.2127 
WBS, IT, ISEC 
20210304 11:45 
Online 
Online 
Streaming Data Compression and Decompression by OneWay Quantum FiniteState Automata, Leading to Quantum FiniteState Deep and Shallow Information (Preliminary Report) Tomoyuki Yamakami (U of Fukui) IT2020117 ISEC202047 WBS202036 
The logical depth of a piece of data has served as a complexity measure to
describe the amount of “useful” and "nonran... [more] 
IT2020117 ISEC202047 WBS202036 pp.3136 
COMP, IPSJAL 
20200902 11:30 
Online 
Online 
What Restrictions Naturally Allow WellKnown NPComplete Problems to Yield NLCompleteness and the Linear Space Hypothesis? Tomoyuki Yamakami (U of Fukui) COMP202010 
Many practical combinatorial problems have been shown to be NPcomplete or NPhard. To cope with further reallife situa... [more] 
COMP202010 pp.3340 
COMP 
20200301 16:25 
Tokyo 
The University of ElectroCommunications (Cancelled but technical report was issued) 
Synchronizing Pushdown Automata and Reset Words Eitatsu Mikami, Tomoyuki Yamakami (Univ. Fukui) COMP201954 
[more] 
COMP201954 pp.5763 
COMP 
20191213 16:25 
Gunma 
Ikaho Seminar House, Gunma University 
Limited Deterministic Automata and Pumping Lemma Kosei Yoshida, Tomoyuki Yamakami (U of Fukui) COMP201941 
This pape, introduced a pumping lemma for languages recognizable by limited deterministic automata. We use this lemma to... [more] 
COMP201941 pp.8592 
QIT (2nd) 
20181126 09:50 
Tokyo 
The University of Tokyo 
NonUniform State Complexity of Quantum Finite Automata and Quantum PolynomialTime LogarithmicSpace 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 
20141008 10:50 
Tokyo 
Chuo University 
The State Complexity of TwoWay Quantum Finite Automata Marcos Villagra, Tomoyuki Yamakami (Univ. of Fukui) COMP201426 
[more] 
COMP201426 pp.58 
COMP 
20140902 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) COMP201420 
We reexamine a practical aspect of combinatorial fuzzy problems of various types, including search, counting, optimizat... [more] 
COMP201420 pp.3542 
COMP 
20131018 15:50 
Aichi 
Nagoya Institute of Technology 
ConstantSpace ZeroKnowledge Proofs Systems with OneWay Quantum Verifiers
 Preliminary Report  Marcos Villagra, Tomoyuki Yamakami (Univ. of Fukui) COMP201336 
We discuss the notion of quantum zeroknowledge proof systems whose memorylimited verifiers
receive a stream of classi... [more] 
COMP201336 pp.2324 
COMP 
20130903 11:20 
Tottori 

Oracle Pushdown Automata, Nondeterministic Reducibilities, and the Hierarchy over the Family of ContextFree Languages
 (Preliminary Version)  Tomoyuki Yamakami (Univ. of Fukui) COMP201327 
We impose various oracle mechanisms on nondeterministic pushdown automata, which naturally induce nondeterministic reduc... [more] 
COMP201327 pp.1724 
COMP 
20090914 10:40 
Tottori 
Tottori University of Environmental Studies 
The Roles of Advice to OneTape LinearTime Turing Machines and Finite Automata Tomoyuki Yamakami (Univ. of Fukui.) COMP200925 
We discuss the power and limitation of various "advice," when it is given particularly to weak computational models of o... [more] 
COMP200925 pp.18 
COMP 
20050318 09:25 
Tokyo 
Tokyo Institute of Technology 
A General Construction of HardCore Predicates for Any Quantum OneWay Function Akinori Kawachi (Tokyo Inst. Tech.), Tomoyuki Yamakami (Trent Univ.) 
We propose a general construction of hardcore predicates for any quantum oneway function in this paper. Our constructi... [more] 
COMP200474 pp.916 