Committee |
Date Time |
Place |
Paper Title / Authors |
Abstract |
Paper # |
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] |
|
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 15:30 |
Fukuoka |
Kyushu University, Chikushi Campus |
Fine-grained quantum supremacy Tomoyuki Morimae (Kyoto Univ.), Suguru Tamaki (Hyogo Univ.) |
[more] |
|
COMP |
2018-09-18 16:00 |
Fukuoka |
Kyusyu Institute of Technology |
NP-hardness of k-modularity maximization on sparse graphs Shunsuke Hirata, Francois Le Gall, Suguru Tamaki (Kyoto Univ.), Junichi Teruyama (Univ. of Hyogo) COMP2018-18 |
[more] |
COMP2018-18 pp.63-68 |
COMP |
2017-03-07 13:30 |
Aichi |
Nanzan University |
[Invited Talk]
Beating Brute Force for Systems of Polynomial Equations over Finite Fields Daniel Lokshtanov (U. Bergen), Ramamohan Paturi (UC San Diego), Suguru Tamaki (Kyoto U.), Ryan Williams (MIT), Huacheng Yu (Stanford U.) COMP2016-53 |
Solving systems of multivariate polynomial equations over finite fields is a fundamental problem in mathematics, science... [more] |
COMP2016-53 p.19 |
COMP |
2016-10-21 14:00 |
Miyagi |
Tohoku University |
An Exact Algorithm for the Satisfiability of Depth-2 SYM-AND Circuits. Kazuhisa Seto (Seikei Univ.), Suguru Tamaki (Kyoto Univ.), Junichi Teruyama (NII) COMP2016-27 |
A Boolean function $f: bits{n} to bit$ is {em weighted symmetric}
if there exist a function $g: mathbb{Z} to bit$ and i... [more] |
COMP2016-27 pp.29-34 |
COMP |
2013-10-18 13:55 |
Aichi |
Nagoya Institute of Technology |
[Tutorial Lecture]
Introduction to Computational Complexity Theory (4): Barriers in Proving the Limits of Computation Suguru Tamaki (Kyoto Univ.) COMP2013-35 |
The P != NP conjecture states that deterministic computation cannot efficiently simulate non-deterministic computation. ... [more] |
COMP2013-35 p.21 |
COMP |
2012-06-21 13:20 |
Hokkaido |
Hokkaido University |
A Satisfiability Algorithm and Average-Case Hardness for Formulas over the Full Binary Basis Kazuhisa Seto, Suguru Tamaki (Kyoto Univ.) COMP2012-17 |
We present a moderately exponential time algorithm for the satisfiability of Boolean formulas over the full binary basis... [more] |
COMP2012-17 pp.41-48 |
COMP |
2007-09-20 15:15 |
Aichi |
|
The Complexity of the Hajos Calculus on Planar Graphs Yoichi Hanatani (Kyoto Univ.), Takashi Horiyama (Saitama Univ.), Kazuo Iwama, Suguru Tamaki (Kyoto Univ.) COMP2007-38 |
The planar Haj\'os calculus is the Haj\'os calculus with the restriction
that all the graphs that appear in the constr... [more] |
COMP2007-38 pp.43-50 |
COMP |
2006-03-23 09:00 |
Tokyo |
The University of Electro-Communications |
Increasing the Success Probability of PPSZ-type Satisfiability Testing Kazuo Iwama, Suguru Tamaki (Kyoto Univ.) |
Recently, [Iwama, Tamaki, SODA04] gave a new worst-case upper bound
for 3SAT by modifying the PPSZ-type algorithm in
... [more] |
COMP2005-63 pp.1-6 |