Committee |
Date Time |
Place |
Paper Title / Authors |
Abstract |
Paper # |
COMP, IPSJ-AL |
2024-05-09 10:45 |
Kyoto |
Kyoto University (Rakuyu-kaikan) |
Depth-Three Circuits for Inner Product and Majority Functions Kazuyuki Amano (Gunma Univ.) COMP2024-4 |
A $Sigma_3^k$-circuit is a depth-three OR $circ$ AND $circ$ OR circuit in which each bottom gate has fan-in at most $k$.... [more] |
COMP2024-4 p.9 |
WBS, IT, ISEC |
2021-03-05 09:00 |
Online |
Online |
Relationships among Security Notions and Lower Bounds on Tags in Anonymous Broadcast Authentication Hirokazu Kobayashi (Yokohama National Univ..), Yohei Watanabe (The Univ. of Electro-Communications/AIST), Junji Shikata (Yokohama National Univ..) IT2020-143 ISEC2020-73 WBS2020-62 |
Watanabe et al. (SCIS2021) proposed Anonymous Broadcast Authentication (ABA) as a cryptographic primitive for remote con... [more] |
IT2020-143 ISEC2020-73 WBS2020-62 pp.187-194 |
COMP |
2018-10-26 15:00 |
Kyoto |
Kyoto University |
Upper and lower bounds on the OBDD-width of a special integer multiplication Tong Qin (Tokyo Tech) COMP2018-27 |
We consider a Boolean function ${rm SMul}_{n-1}^n$ that computes the middle bit of the multiplication of two natural num... [more] |
COMP2018-27 pp.45-54 |
HWS, ISEC, SITE, ICSS, EMM, IPSJ-CSEC, IPSJ-SPT [detail] |
2018-07-25 14:10 |
Hokkaido |
Sapporo Convention Center |
[Invited Talk]
Memory Lower Bounds of Reductions Revisited (from EUROCRYPT 2018) Yuyu Wang (Tokyo Tech/AIST/IOHK), Takahiro Matsuda, Goichiro Hanaoka (AIST), Keisuke Tanaka (Tokyo Tech) ISEC2018-24 SITE2018-16 HWS2018-21 ICSS2018-27 EMM2018-23 |
In this invited talk, we introduce the paper, “ Memory Lower Bounds of Reductions Revisited ” by Y. Wang, T. Matsuda, G.... [more] |
ISEC2018-24 SITE2018-16 HWS2018-21 ICSS2018-27 EMM2018-23 p.93 |
COMP |
2016-10-21 14:30 |
Miyagi |
Tohoku University |
On lower bounds for the complexity of the Frobenius problem and its subproblems Shunichi Matsubara (Aoyama Gakuin Univ.) COMP2016-28 |
In this paper, we lower bounds for the time complexity of the Frobenius problem. Given a set $A$ of coprime positive in... [more] |
COMP2016-28 pp.35-37 |
COMP |
2015-10-02 10:00 |
Tokyo |
|
Upper and lower bounds and time complexities on the Frobenius problem obtained from analysing its additive structure Shunichi Matsubara (Aoyama Gakuin Univ.) COMP2015-22 |
In this work, we investigate upper and lower bounds for the Frobenius problem, using some existing results in additive c... [more] |
COMP2015-22 pp.1-5 |
COMP, IPSJ-AL |
2013-05-17 13:35 |
Hokkaido |
Otaru University of Commerce |
Query Complexity of Witness Finding Akinori Kawachi (Tokyo Inst. of Tech.), Benjamin Rossman (NII), Osamu Watanabe (Tokyo Inst. of Tech.) COMP2013-11 |
For any polynomial-time relation L subset_of {0,1}^m x {0,1}^n where n = m^{O(1)}, the classic search-to-decision reduct... [more] |
COMP2013-11 pp.39-46 |
COMP |
2012-04-27 10:35 |
Osaka |
Osaka Prefecture University |
Reconstructing Strings from Substrings with Quantum Queries Richard Cleve (Univ. of Waterloo), Kazuo Iwama (Kyoto Univ.), Francois Le Gall (Univ. of Tokyo), Harumichi Nishimura (Nagoya Univ.), Seiichiro Tani (NTT), Junichi Teruyama (Kyoto Univ.), Shigeru Yamashita (Ritsumeikan Univ.) COMP2012-2 |
This paper investigates the number of quantum queries made
to solve the problem of reconstructing an unknown string fro... [more] |
COMP2012-2 pp.7-14 |
COMP |
2011-06-30 14:40 |
Hiroshima |
Hiroshima Univ. |
On the Constant Depth Circuit Complexity of Subgraph Isomorphism on Random Graphs Koutarou Nakagawa (Tokyo Inst. of Tech.) COMP2011-20 |
The AC$^0$ circuit complexity of $k$-clique on random graphs is already known. Rossman established the lower bound $n^{\... [more] |
COMP2011-20 pp.33-37 |
MSS |
2009-01-29 13:00 |
Kanagawa |
Kanagawa Industrial Promotion Center |
On Upper and Lower Bounds of Optimal Execution Time of Task Graph by Considering Communication Delays Takashi Otsuka, Masato Nakahara, Qi-Wei Ge, Mitsuru Nakata (Yamaguchi Univ.), Yuu Moriyama, Hirotoshi Tonou (Fujitsu TEN Limited) CST2008-41 |
This paper deals with upper and lower bounds of optimal execution time of task graphs that are supposed to be executed i... [more] |
CST2008-41 pp.1-4 |
COMP |
2008-12-03 14:35 |
Gunma |
Gunma Univ. |
Improved Formula Size Lower Bounds for Monotone Self-Dual Boolean Functions Kenya Ueno (Univ. of Tokyo) COMP2008-51 |
We introduce a new technique proving formula size lower bounds based on the linear programming bound originally introduc... [more] |
COMP2008-51 pp.33-40 |
ICM, NS, CQ (Joint) |
2005-11-17 14:00 |
Shimane |
Kunibiki-messe (Matsue city) |
Traffic Pattern Filtering Based on Lower Bounds of Traffic Volume for Improving DDoS Traceback Accuracy Hironori Utsumi, Hiroshi Tsunoda, Yuji Waizumi, Yoshiaki Nemoto (Tohoku Univ.) |
For Traffic pattern based traceback techniques, non-DoS traffic included in DoS traffic becomes a source of noise which ... [more] |
NS2005-110 pp.1-4 |
ISEC |
2005-09-16 15:45 |
Tokyo |
Kikai-Shinko-Kaikan Bldg. |
Precise Tardos Bound for Fingerprinting Codes Taichi Isogai, Hirofumi Muratani (Toshiba) |
``Fingerprinting'' is a technique that user's ID is embedded in digital contents. This technique is used for finding a m... [more] |
ISEC2005-85 pp.67-72 |
RCS, AP, WBS, MW, MoNA |
2005-03-04 10:00 |
Kanagawa |
Yokosuka Research Park |
A theoretical performance study of the ESPRIT algorithm for the 7-element ESPAR antenna Mickael Pencole, Eddy Taillefer, Tatsuya Shimizu, Takashi Ohira (ATR) |
Recently, the Estimation of Signal Parameters via Rotational Invariance Techniques (ESPRIT) algorithm for the Electronic... [more] |
WBS2004-147 AP2004-328 RCS2004-415 MoMuC2004-198 MW2004-325 pp.151-156 |