| IEICE Technical Committee Submission System Conference Schedule |
Online Proceedings [Sign in] Tech. Rep. Archives |
All Technical Committee Conferences (Searched in: All Years)
| Committee | Date Time | Place | Paper Title / Authors | Abstract | Paper # | |
| COMP | 2023-10-24 14:05 |
Aichi | Nagoya Univ. Venture Business Lab. | Solving Distance-constrained Labeling Problems for Small Diameter Graphs via TSP Tesshu Hanaka (Kyushu Univ.), Hirotaka Ono, Kosuke Sugiyama (Nagoya Univ.)  COMP2023-12 |
For an undirected graph $G=(V,E)$ and a $k$-nonnegative integer vector $bp=(p_1,ldots,p_k)$, a mapping $lcolon Vto mathb... [more] | COMP2023-12 pp.9-11 |
| COMP, IPSJ-AL | 2023-05-11 10:00 |
Hokkaido | Hokkaido University | A computational complexity assumption necessary for pseudorandom quantum states generators Yuki Shirakawa (Kyoto Univ.) COMP2023-2 |
Pseudorandom quantum states generators (PRSGs) are efficient quantum algorithms that output quantum states which are com... [more] | COMP2023-2 pp.2-7 |
| COMP, IPSJ-AL | 2022-05-19 15:40 |
Online | Online | On Time Complexity of Distributed Minimum Spanning Tree Construction in the broadcast-CONGEST model for Restricted Graph Classes Narumi Shigekiyo, Toshimitsu Masuzawa, Taisuke Izumi (Osaka Univ.) COMP2022-5 |
Broadcast-CONGEST is a variant of CONGEST, the standard computational model for distributed graph algorithms, with the r... [more] | COMP2022-5 pp.33-38 |
| QIT (2nd) |
2019-11-19 11:50 |
Tokyo | Gakushuin University | Fine-grained quantum supremacy based on Orthogonal Vectors, 3-SUM and All-Pairs Shortest Paths Ryu Hayakawa, Tomoyuki Morimae (Kyoto Univ.), Suguru Tamaki (Hyogo Univ.) |
Fine-grained quantum supremacy is a study of excluding possibilities of superpolynomial time classical simulations of qu... [more] | |
| QIT (2nd) |
2019-11-18 13:50 |
Tokyo | Gakushuin University | [Poster Presentation]
Quantum Communication Complexity of Distribution Testing Aleksandrs Belovs (Univ. of Latvia), Arturo Castellanos (Kyoto Univ.), Francois Le Gall, Guillaume Malod (Nagoya Univ.) |
We study the quantum version of the closeness testing problem in communication complexity, in the case where Alice and B... [more] | |
| COMP | 2019-10-25 16:35 |
Hokkaido | Sapporo Campus, Hokkaido University | Fine-grained quantum supremacy based on Orthogonal Vectors, 3-SUM and All-Pairs Shortest Paths Ryu Hayakawa, Tomoyuki Morimae (YITP, Kyoto Univ.), Suguru Tamaki (School of Social Information Science, Univ. of Hyogo) COMP2019-28 |
Fine-grained quantum supremacy is a study of excluding possibilities of superpolynomial time classical simulations of qu... [more] | COMP2019-28 pp.71-78 |
| COMP | 2019-09-02 14:50 |
Okayama | Tsushima Campus, Okayama University | Fine-grained quantum computational supremacy Tomoyuki Morimae (Kyoto Univ.), Suguru Tamaki (Univ. Hyogo) COMP2019-14 |
It is known that probability distributions generated by quantum circuits cannot be approximately sampled by efficient cl... [more] | COMP2019-14 p.25 |
| QIT (2nd) |
2019-05-21 12:00 |
Fukuoka | Kyushu University, Chikushi Campus | Analysis of Quantum Multi-Prover Zero-Knowledge Systems: Elimination of the Honest Condition and Computational Zero-Knowledge Systems for QMIP Yusuke Kinoshita (Nagoya Univ.) |
Zero-knowledge and multi-prover systems are both central notions in classical and quantum complexity theory. There is, ... [more] |
|
| 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] | |
| QIT (2nd) |
2018-06-04 11:00 |
Hiroshima | ICCH Ran | Power of Uninitialized Qubits in Shallow Quantum Circuits Yasuhiro Takahashi, Seiichiro Tani (NTT) |
We study the computational power of shallow quantum circuits with $O(log n)$ initialized and $n^{O(1)}$ uninitialized a... [more] |
|
| SS, MSS | 2018-01-18 14:15 |
Hiroshima | Computational Complexity of Membership and Emptiness Problems for Register Context-Free Grammars Ryoma Senda, Hiroyuki Seki (Nagoya Univ.) MSS2017-54 SS2017-41 |
Register context-free grammar (RCFG) is an extension of context-free grammar to handle data values. RCFGs can be applied... [more] | MSS2017-54 SS2017-41 pp.41-46 |
|
| IBISML | 2017-11-10 13:00 |
Tokyo | Univ. of Tokyo | IBISML2017-85 |
We consider binary classification problems using local features of objects. One of motivating applications is time-serie... [more] | IBISML2017-85 pp.361-368 |
| COMP, IPSJ-AL | 2016-06-24 13:45 |
Ishikawa | On completeness of polynomial-time counting hierarchy under relaxed subtractive reductions Shunichi Matsubara (Aoyama Gakuin Univ.) COMP2016-7 |
The polynomial-time hierarchy was introduced by Meyer and Stockmeyer, which is a hierarchy on decision problems and has ... [more] | COMP2016-7 pp.9-12 |
|
| ICM, LOIS | 2016-01-22 10:20 |
Fukuoka | Fukuoka Institute of Technology | Complexity Resolution Control for Context Based on Metromaps Marat Zhanikeev (Kyutech) ICM2015-36 LOIS2015-58 |
Metromaps are recognized well in visualization research but are rarely found in applied technologies. Earlier works sho... [more] | ICM2015-36 LOIS2015-58 pp.59-62 |
| COMP | 2015-09-01 10:30 |
Nagano | Impossibility of Classically Simulating One-Clean-Qubit Computation Keisuke Fujii (Kyoto Univ.), Hirotada Kobayashi (NII), Tomoyuki Morimae (Gunma Univ.), Harumichi Nishimura (Nagoya Univ.), Shuhei Tamate (NII), Seiichiro Tani (NTT) COMP2015-17 |
Deterministic quantum computation with one quantum bit (DQC1) is a restricted model of quantum computing where the input... [more] | COMP2015-17 pp.5-12 |
|
| EMM, IT | 2015-05-22 10:00 |
Kyoto | Kyoto International Community House | On the Computational Complexity of Information Flow Problem with Hierarchy Constraint Yuki Takeda, Yuichi Kaji, Minoru Ito (NAIST) IT2015-11 EMM2015-11 |
An information flow problem discusses how to distribute information over a complicated network. It is known that the te... [more] | IT2015-11 EMM2015-11 pp.57-62 |
| COMP | 2014-12-05 11:00 |
Kumamoto | Sojo University | On Zero-Suppressed Binary Decision Diagrams and Complexity Theory Hiroki Morizumi (Shimane Univ.) COMP2014-34 |
Zero-suppressed binary decision diagrams (ZDDs) are a data structure representing Boolean functions, and one of the most... [more] | COMP2014-34 pp.17-19 |
| COMP | 2014-09-02 15:45 |
Aichi | Toyohashi University of Technology | A Note on the Class of the Computational Comlexity of the Coin-Exchange Problem of Frobenius Shunichi Matsubara (Aoyama Gakuin Univ.) COMP2014-22 |
The coin-exchange problem of Frobenius is a problem that determines whether the Frobenius number for given relatively pr... [more] | COMP2014-22 pp.51-54 |
| COMP, IPSJ-AL | 2014-06-14 09:25 |
Ehime | Matsuyama, Ehime | Computational Complexity of Irredundancy of Local Hamiltonian Ryo Kawasaki, Harumichi Nishimura (Nagoya Univ.) COMP2014-11 |
Gharibian and Kempe [ICALP2012] introduced a problem on irredundancy of local Hamiltonians, named as QIRR, which asks wh... [more] | COMP2014-11 pp.69-76 |
| COMP, IPSJ-AL | 2014-06-14 10:30 |
Ehime | Matsuyama, Ehime | On Characterizations of Randomized Computation Using Plain Kolmogorov Complexity Shuichi Hirahara, Akitoshi Kawamura (Univ. of Tokyo) COMP2014-12 |
Allender, Friedman, and Gasarch recently proved an upper bound of PSPACE for the class $DTTR_K$ of decidable language... [more] |
COMP2014-12 pp.77-83 |
[Return to Top Page]