Tsuyoshi Ito’s Papers

Listed roughly in reverse chronological order.

• Tsuyoshi Ito, Hirotada Kobayashi and John Watrous.
  Quantum interactive proofs with weak error bounds.
  Available as arXiv:1012.4427 [quant-ph], Dec. 2010.
  An oral presentation (contributed talk) at the 14th Workshop on Quantum Information Processing (QIP 2011), Singapore, Jan. 10–14, 2011.
• Dmitry Gavinsky and Tsuyoshi Ito.
  Quantum fingerprints that keep secrets.
  Available as arXiv:1010.5342 [quant-ph], Oct. 2010.
  Also available as Electronic Colloquium on Computational Complexity, Technical Report TR10‐165, Nov. 2010.
• Tsuyoshi Ito.
  Polynomial‐space approximation of no‐signaling provers.
  In Automata, Languages and Programming: Proceedings of the 37th International Colloquium on Automata, Languages and Programming (ICALP 2010), pp. 140–151, Bordeaux, France, July 5–10, 2010 (link). Volume 6198 of Lecture Notes in Computer Science, ISBN 978-3-642-14164-5, Springer. An oral presentation.
  @InProceedings{Ito10ICALP, author = {Tsuyoshi Ito}, title = {Polynomial-Space Approximation of No-Signaling Provers}, booktitle = {Automata, Languages and Programming: Thirty-Seventh International Colloquium, Part~I}, series = {Lecture Notes in Computer Science}, volume = 6198, pages = {140-151}, month = jul, year = 2010, }
  A preliminary version available as arXiv:0908.2363 [cs.CC], Aug. 2009. Revised to v2, Oct. 2009.
  A poster presentation at the 13th Workshop on Quantum Information Processing (QIP 2010), Zurich, Switzerland, Jan. 18–22, 2010.
• Jean Cardinal, Erik D. Demaine, Martin L. Demaine, Shinji Imahori, Tsuyoshi Ito, Masashi Kiyomi, Stefan Langerman, Ryuhei Uehara and Takeaki Uno.
  Algorithmic folding complexity.
  Graphs and Combinatorics, 27(3):341–351, May 2011 (link). Special issue for the Japan Conference on Computational Geometry and Graphs (JCCGG2009).
  @Article{CarDemDemImaItoKiyLanUehUno11GC, author = {Jean Cardinal and Erik D. Demaine and Martin L. Demaine and Shinji Imahori and Tsuyoshi Ito and Masashi Kiyomi and Stefan Langerman and Ryuhei Uehara and Takeaki Uno}, title = {Algorithmic Folding Complexity}, journal = {Graphs and Combinatorics}, volume = 27, number = 3, pages = {341-351}, month = may, year = 2011, }
• Tsuyoshi Ito, Hirotada Kobayashi and Keiji Matsumoto.
  Oracularization and two‐prover one‐round interactive proofs against nonlocal strategies.
  In Proceedings: 24th Annual IEEE Conference on Computational Complexity (CCC 2009), pp. 217–228, Paris, France, July 15–18, 2009 (link). An oral presentation.
  @InProceedings{ItoKobMat09CCC, author = {Tsuyoshi Ito and Hirotada Kobayashi and Keiji Matsumoto}, title = {Oracularization and Two-Prover One-Round Interactive Proofs against Nonlocal Strategies}, booktitle = {Proceedings: Twenty-Fourth Annual IEEE Conference on Computational Complexity (CCC 2009)}, pages = {217-228}, month = jul, year = 2009, }
  A preliminary version available as arXiv:0810.0693 [quant-ph], Oct. 2008.
  Also presented at the 12th Workshop on Quantum Information Processing (QIP 2009) as oral presentation, Santa Fe, New Mexico, USA, Jan. 12–16, 2009.
• Tsuyoshi Ito, Masashi Kiyomi, Shinji Imahori and Ryuhei Uehara.
  Complexity of pleats folding.
  In Proceedings of the 25th European Workshop on Computational Geometry (EuroCG 2009), pp. 53–56, Brussels, Belgium, Mar. 16–18, 2009. (An oral presentation given by Ryuhei Uehara.)
• Tsuyoshi Ito, Hirotada Kobayashi, Daniel Preda, Xiaoming Sun and Andrew C.‐C. Yao.
  Generalized Tsirelson inequalities, commuting‐operator provers, and multi‐prover interactive proof systems.
  In Proceedings: 23rd Annual IEEE Conference on Computational Complexity (CCC 2008), pp. 187–198, College Park, Maryland, USA, June 22–26, 2008 (link). An oral presentation.
  @InProceedings{ItoKobPreSunYao08CCC, author = {Tsuyoshi Ito and Hirotada Kobayashi and Daniel Preda and Xiaoming Sun and Andrew C.-C. Yao}, title = {Generalized {Tsirelson} Inequalities, Commuting-Operator Provers, and Multi-Prover Interactive Proof Systems}, booktitle = {Proceedings: Twenty-Third Annual IEEE Conference on Computational Complexity (CCC 2008)}, pages = {187-198}, month = jun, year = 2008, }
  Available as arXiv:0712.2163 [quant-ph], Dec. 2007. Revised to v2, April 2008.
  Also presented at the 11th Workshop on Quantum Information Processing (QIP 2008) as oral presentation, New Delhi, India, Dec. 17–21, 2007.
• David Avis, Hiroshi Imai and Tsuyoshi Ito.
  Generating facets for the cut polytope of a graph by triangular elimination.
  Mathematical Programming, 112(2):303–325, Apr. 2008 (link).
  @Article{AviImaIto08MP, author = {David Avis and Hiroshi Imai and Tsuyoshi Ito}, title = {Generating Facets for the Cut Polytope of a Graph by Triangular Elimination}, journal = {Mathematical Programming}, volume = 112, number = 2, pages = {303-325}, month = apr, year = 2008, }
  Manuscript appeared at arXiv:math.CO/0601375, Jan. 2006. Revised in v2, June 2006.
  An oral presentation, CORS / Optimization Days 2006 Joint Conference, Montreal, Quebec, Canada, May 8–10, 2006.
• David Avis and Tsuyoshi Ito.
  New classes of facets of cut polytope and tightness of I_mm22 Bell inequalities.
  Discrete Applied Mathematics, 155(13):1689–1699, Aug. 2007 (link).
  @Article{AviIto07DAM, author = {David Avis and Tsuyoshi Ito}, title = {New Classes of Facets of Cut Polytope and Tightness of {$\mathrm{I}_{mm22}$} {Bell} Inequalities}, journal = {Discrete Applied Mathematics}, volume = 155, number = 13, pages = {1689-1699}, month = aug, year = 2007, }
  Manuscript appeared at arXiv:math.CO/0505143, May 2005.
  A preliminary version appeared in Proceedings of 4th Japanese‐Hungarian Symposium on Discrete Mathematics and Its Applications (JH2005), pp. 122–128, Budapest, Hungary, June 3–6, 2005. An oral presentation.
• David Avis, Hiroshi Imai and Tsuyoshi Ito.
  On the relationship between convex bodies related to correlation experiments with dichotomic observables.
  Journal of Physics A: Mathematical and General, 39(36):11283–11299, Sept. 2006 (link).
  @Article{AviImaIto06JPhysA, author = {David Avis and Hiroshi Imai and Tsuyoshi Ito}, title = {On the Relationship between Convex Bodies Related to Correlation Experiments with Dichotomic Observables}, journal = {Journal of Physics A: Mathematical and General}, volume = 39, number = 36, pages = {11283-11299}, month = sep, year = 2006, }
  Manuscript appeared at arXiv:quant-ph/0605148, May 2006.
• David Avis and Tsuyoshi Ito.
  Polyhedral and semidefinite approaches to classical and quantum Bell inequalities.
  In Proceedings of Asian Conference on Quantum Information Science 2006 (AQIS 2006), 8 pages, Beijing, China, Sept. 1–4, 2006. An oral presentation.
• Tsuyoshi Ito, Hiroshi Imai and David Avis.
  Bell inequalities stronger than the Clauser–Horne–Shimony–Holt inequality for three‐level isotropic states.
  Physical Review A, vol. 73, article no. 042109, 9 pages, Apr. 2006 (link).
  @Article{ItoImaAvi06PRA, author = {Tsuyoshi Ito and Hiroshi Imai and David Avis}, title = {{Bell} Inequalities Stronger than the {Clauser--Horne--Shimony--Holt} Inequality for Three-Level Isotropic States}, journal = {Physical Review A}, volume = 73, number = 042109, month = apr, year = 2006, }
  Manuscript: Bell inequalities stronger than the CHSH inequality for 3‐level isotropic states, arXiv:quant-ph/0508210, Aug. 2005. Revised to v2, Jan. 2006.
• Tsuyoshi Ito, Hiroshi Imai and David Avis.
  Some open problems on Bell inequalities and partial solutions to them.
  (Title in Japanese: Bell 不等式に関する未解決問題集とそれに対する部分的解答.)
  The 13th Quantum Information Technology Symposium (QIT13), Sendai, Japan, Nov. 24–25, 2005. (An oral presentation given by Hiroshi Imai.)
• Tsuyoshi Ito.
  Bell inequalities: combinatorial derivation and relevance.
  An oral presentation, 1st Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS 2005), Znojmo, Czech, Oct. 14–17, 2005.
• David Avis, Hiroshi Imai, Tsuyoshi Ito and Yuuya Sasaki.
  Two‐party Bell inequalities derived from combinatorics via triangular elimination.
  Journal of Physics A: Mathematical and General, 38(50):10971–10987, Dec. 2005 (link).
  @Article{AviImaItoSas05JPhysA, author = {David Avis and Hiroshi Imai and Tsuyoshi Ito and Yuuya Sasaki}, title = {Two-Party {Bell} Inequalities Derived from Combinatorics via Triangular Elimination}, journal = {Journal of Physics A: Mathematical and General}, volume = 38, number = 50, pages = {10971-10987}, month = dec, year = 2005, }
  Manuscript appeared at arXiv:quant-ph/0505060, May 2005. Revised to v3, Sept. 2005.
  A related page containing a list of Bell inequalities and a program to produce it is available at http://www-imai.is.s.u-tokyo.ac.jp/~tsuyoshi/bell/.
• Tsuyoshi Ito.
  Relevance relation among Bell inequalities of 2‐valued measurements in multilevel system.
  (Title in Japanese: 2 値測定の Bell 不等式の間の多準位系での必要性関係.)
  A poster presentation, The 12th Quantum Information Technology Symposium (QIT12), Atsugi, Japan, May 12–13, 2005.
  Technical Report No. QIT2005-33, May 2005, in Japanese.
• David Avis, Hiroshi Imai, Tsuyoshi Ito and Yuuya Sasaki.
  Test of relevance relation between Bell inequalities using nonlinear and semidefinite programming.
  (Title in Japanese: 非線型および半定値計画を用いた Bell 不等式の必要性関係の判定.)
  An oral presentation, The 11th Quantum Information Technology Symposium (QIT11), No. QIT2004-57, Kyoto, Japan, Dec. 6–7, 2004, in Japanese.
• Tsuyoshi Ito, Yuuya Sasaki, Hiroshi Imai and David Avis.
  Families of tight Bell inequalities derived from classes of facets of cut polytopes.
  In Proceedings of ERATO Conference on Quantum Information Science 2004 (EQIS’04), pp. 78–79, Tokyo, Japan, Sept. 1–5, 2004. An oral presentation.
• Takayuki Yato, Takahiro Seta and Tsuyoshi Ito.
  Finding yozume of generalized tsume‐shogi is exptime‐complete.
  IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, Special Section on Discrete Mathematics and Its Applications, E88-A(5):1249–1257, May 2005 (link).
  @Article{YatSetIto05IEICEA, author = {Takayuki Yato and Takahiro Seta and Tsuyoshi Ito}, title = {Finding Yozume of Generalized Tsume-Shogi is Exptime-Complete}, journal = {IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences}, volume = {E88-A}, number = 5, pages = {1249-1257}, month = may, year = 2005, }
  A preliminary version appeared under the title 一般化詰将棋の余詰判定の指数時間完全性 in IEICE Technical Report No. COMP2004-21, the Institute of Electronics, Information and Communication Engineers, June 2004, in Japanese. (An oral presentation given by Takayuki Yato.)
• Tsuyoshi Ito.
  カット多面体のファセットの三角消去と量子情報理論における Bell 不等式.
  (Triangular elimination of facets of cut polytopes and Bell inequalities in quantum information theory.)
  An oral presentation, Seminars on Algorithms in Operations Research (SAOR), Tsukuba, Japan, May 29–30, 2004.
• Yuuya Sasaki, Tsuyoshi Ito, Hiroshi Imai and David Avis.
  Bell inequalities derived from combinatorics.
  (Title in Japanese: 組合せ論から導出される Bell 不等式.)
  The 10th Quantum Information Technology Symposium (QIT10), No. QIT2004-12, Tokyo, Japan, May 24–25, 2004, in Japanese. (An oral presentation given by Yuuya Sasaki.)
• David Avis, Hiroshi Imai, Tsuyoshi Ito and Yuuya Sasaki.
  Deriving tight Bell inequalities for 2 parties with many 2‐valued observables from facets of cut polytopes.
  Preprint, arXiv:quant-ph/0404014, April 2004. Revised in v3, April 2004.
  This preprint was superseded by arXiv:quant-ph/0505060.
• Yasuhito Asano, Tsuyoshi Ito, Hiroshi Imai, Masashi Toyoda and Masaru Kitsuregawa.
  Compact encoding of the Web Graph exploiting various power distributions.
  IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, Special Section on Discrete Mathematics and Its Applications, E87-A(5):1183–1184, May 2004 (link).
  @Article{AsaItoImaToyKit04IEICEA, author = {Yasuhito Asano and Tsuyoshi Ito and Hiroshi Imai and Masashi Toyoda and Masaru Kitsuregawa}, title = {Compact Encoding of the {Web} {Graph} Exploiting Various Power Distributions}, journal = {IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences}, volume = {E87-A}, number = 5, pages = {1183-1184}, month = may, year = 2004, }
  A preliminary version appeared under the title Compact encoding of the Web Graph exploiting various power laws — statistical reason behind Link Database in Advances in Web‐Age Information Management: Proceedings of 4th International Conference on Web‐Age Information Management (WAIM 2003), pp. 37–46, vol. 2762 of Lecture Notes in Computer Science, Springer, ISBN 3-540-40715-4, Chengdu, China, Aug. 17–19, 2003 (link).
• Tsuyoshi Ito and Mary Inaba.
  Theoretical analysis of performances of TCP/IP congestion control algorithm with different distances.
  In NETWORKING 2004, Networking Technologies, Services, and Protocols; Performance of Computer and Communication Networks; Mobile and Wireless Communication: Proceedings of 3rd International IFIP-TC6 Networking Conference (NETWORKING 2004), pp. 962–973, vol. 3042 of Lecture Notes in Computer Science, Springer, ISBN 3-540-21959-5, Athens, Greece, May 9–14, 2004. Online date: April 2004 (link). An oral presentation.
  A preliminary version appeared under the title Theoretical analysis of throughput of TCP/IP congestion control algorithm with different distances (in Japanese: 長距離・短距離通信が混在する環境での TCP/IP のデータ転送速度の理論的解析) in IPSJ SIG Technical Report No. 2003-AL-93-8, Information Processing Society of Japan, Jan. 2004 (link).
• Makoto Nakamura, Junsuke Sembon, Yutaka Sugawara, Tsuyoshi Itoh, Mary Inaba and Kei Hiraki.
  End‐node transmission rate control kind to intermediate routers — towards 10 Gbps era.
  2nd International Workshop on Protocols for Fast Long‐Distance Networks (PFLDnet 2004), Feb. 16–17, 2004. (An oral presentation given by Makoto Nakamura.)
• Tsuyoshi Ito and Hiroshi Imai.
  Reformalization and implementation of fully dynamic algorithm for transitive closure on directed graphs.
  (Title in Japanese: 有向グラフの推移閉包問題に対する Fully Dynamic アルゴリズムの再定式化と実装.)
  IPSJ SIG Notes No. 2002-AL-84-2, Information Processing Society of Japan, May 2002 (link). An oral presentation.

Theses

• Tsuyoshi Ito.
  Bell Inequalities and the cut polytope: Bridging quantum information science and combinatorial optimization.
  (Title in Japanese: Bell 不等式とカット多面体: 量子情報科学と組合せ最適化の結合.)
  Ph.D. Thesis, Department of Computer Science, Graduate School of Information Science and Technology, the University of Tokyo, Dec. 2006.
• Tsuyoshi Ito.
  Analyses of flow time and fairness of TCP congestion control algorithms in wide area networks.
  (Title in Japanese: 広域ネットワークにおける TCP の輻輳制御アルゴリズムの通信時間と公平性の解析.)
  Master Thesis, Department of Computer Science, Graduate School of Information Science and Technology, the University of Tokyo, Feb. 2004.
• Tsuyoshi Ito.
  Reformalization and implementation of fully dynamic algorithm for transitive closure on directed graphs.
  (Title in Japanese: 有向グラフの推移閉包問題に対する Fully Dynamic アルゴリズムの再定式化と実装.)
  Senior Thesis, Department of Information Science, Faculty of Science, the University of Tokyo, Feb. 2002.