Dept. of Math. and Comp. Sciences
Research Reports (Series C: Computer Science)

Notice!
Some reports in this list may not have complete on-line information. In this case, or in general, if you have any question, please contact to the contacting author of the report directly.
ID: C-276 (October, 2011)
Title: Message Passing Algorithms for MLS-3LIN Problem
Authors: Osamu Watanabe
Email: watanabe(at)is. titech. ac. jp
Abstract: C-276.txt
Document: C-276.pdf

ID: C-275 (September, 2011)
Title: Fourier Approximation under Non-uniform Distribution
Authors: Hiroki Yamaguchi
Email: yamaguc6(at)is. titech. ac. jp
Abstract: C-275.txt
Document: C-275.pdf

ID: C-274 (January, 2011)
Title: Faster Evaluation of ZBDD Compressed Multi-Linear Functions with GPU Parallelism
Authors: Shin-ichi Minato, Mikael Onsjo, and Osamu Watanabe
Email: watanabe(at)is. titech. ac. jp
Abstract: C-274.txt
Document: C-274.pdf

ID: C-273 (October, 2010)
Title: On the Optimality of Lattice for the Coppersmith Technique
Authors: Yoshinori Aono, Manindra Agrawal, Takakazu Sato, and Osamu Watanabe
Email: watanabe(at)is.titech.ac.jp
Abstract: C-273.txt
Document: This article is removed due to the presentation of its revised version at Cryptology ePrint archive, http://eprint.iacr.org/2012/108

ID: C-272(May, 2010)
Title: Certificateless Identity-Based Proxy Signature for Grid Computing Authorization
Authors: Mohamed Amin JABRI, Satoshi MATSUOKA
Email: matsu@is.titech.ac.jp
Abstract: C-272.txt
Document: C-272.pdf

ID: C-271 (April, 2010)
Title: Propagation Connectivity of Random Hypergraphs
Authors: Amin Coja-Oghlan, Mikael Onsjo, and Osamu Watanabe
Email: watanabe(at)is. titech. ac. jp
Abstract: C-271.txt
Document: C-271.pdf

ID: C-270 (April, 2010)
Title: Spectral Analysis of Random Sparse Matrices
Authors: T. Ando, Y. Kabashima, H. Takahashi, O. Watanabe, and M. Yamamoto
Email: watanabe(at)is. titech. ac. jp
Abstract: C-270.txt
Document: C-270.pdf

ID: C-269 (March, 2010)
Title: Level-wise Node Size Distribution of Randomly Generated Regular Trees
Authors: Elitza Maneva, Takeya Shigezumi, Yushi Uno, and Osamu Watanabe
Email: Takeya.Shigezumi@is.titech.ac.jp
Abstract: C-269.txt
Document: C-269.pdf

ID: C-268 (Feb., 2010)
Title: CUDA Implementation of Iterative Updating with Application for the Radix-2 Algorithm for DFT
Authors: Mikael Onsjo, Kenta Kasai, Osamu Watanabe
Email: watanabe(at)is. titech. ac. jp
Abstract: C-268.txt
Document: C-268.pdf

ID: C-267 (December, 2009)
Title: Mostly modular composition of crosscutting structures by contextual predicate dispatch
Authors: Shigeru Chiba, Atsushi Igarashi, and Salikh Zakirov
Email: chiba AT is.titech...
Abstract: C-267.txt
Document: C-267.pdf

ID: C-266 (December, 2009)
Title: A proof of the completeness theorem for the modal logic with transitive closure of accessibility relation
Authors: Ryo Kashima
Email: kashima@is.titech.ac.jp
Abstract: C-266.txt
Document: C-266.pdf

ID: C-265 (October, 2009)
Title: Propagation Connectivity of Random Hypergraphs
Authors: Robert Berke and Mikael Onsjö
Email: mikael(at)is.titech.ac.jp
Abstract: C-265.txt
Document: C-265.pdf

ID: C-264 (November, 2009)
Title: Yet Another Reduction from Graph to Ring Isomorphism Problems
Authors: Hayasaka Tomoyuki
Email: hayasak6@is.titech.ac.jp
Abstract: C-264.txt
Document: C-264.pdf

ID: C-263(September, 2009)
Title: Simplification of the lattice based attack of Boneh and Durfee for RSA cryptoanalysis
Authors: Yoshinori Aono
Email: aono.y.ac@m.titech.ac.jp
Abstract: C-263.txt
Document: C-263.pdf

ID: C-262 (March, 2009)
Title: A tight bound of the largest eigenvalue of sparse random graph
Authors: Tomonori Ando
Email: ando4@is.titech.ac.jp
Abstract: C-262.txt
Document: C-262.pdf

ID: C-261 (March, 2009)
Title: Strong Hardness Preserving Reduction from a P-Samplable Distribution to the Uniform Distribution for NP-Search Problems
Authors: Akinori Kawachi and Osamu Watanabe
Email: watanabe(at)is.titech.ac.jp
Abstract: C-261.txt
Document: C-261.pdf

ID: C-260 (March, 2009)
Title: One-Way Functions and the Isomorphism Conjecture
Authors: Manindra Agrawal and Osamu Watanabe
Email: watanabe(at)is.titech.ac.jp
Abstract: C-260.txt
Document: C-260.pdf

ID: C-259 (March, 2009)
Title: Can low degree polynomials compute modulo functions over finite fields?
Authors: Akinori Kawachi, Hidetoki Tanaka, and Osamu Watanbe
Email: tanaka7@is.titech.ac.jp
Abstract: C-259.txt
Document: C-259.pdf

ID: C-258 (January, 2009)
Title: A new lattice construction for partial key exposure attack for RSA (revised)
Authors: Yoshinori Aono
Email: aono5@is.titech.ac.jp
Abstract: C-258.txt
Document: C-258.pdf

ID: C-257 (October, 2008)
Title: A New lattice construction for partial key exposure attack for RSA
Authors: Yoshinori Aono
Email: aono5@is.titech.ac.jp
Abstract: C-257.txt
Document: C-257.pdf

ID: C-256 (Aug., 2008)
Title: On Proving Circuit Lower Bounds Against the Polynomial-time Hierarchy: Positive and Negative Results
Authors: Jin-Yi Cai and Osamu Watanabe
Email: watanabe(at)is.titech.ac.jp
Abstract: C-256.txt
Document: C-256.pdf

ID: C-255 (March, 2008)
Title: Scale Free Interval Graphs
Authors: Naoto Miyoshi, Takeya Shigezumi, Ryuhei Uehara, Osamu Watanabe
Email: Takeya.Shigezumi@is.titech.ac.jp
Abstract: C-255.txt
Document: C-255.pdf

ID: C-254 (February, 2008)
Title: Reduction for NP-search Problems from Samplable to Uniform Distributions: Hard Distribution Case
Authors: Akinori Kawachi and Osamu Watanabe
Email: kawachi@is.titech.ac.jp
Abstract: C-254.txt
Document: C-254.pdf

ID: C-253(Febrary, 2008)
Title: Simple Decomposition of Ciphertexts
Authors: Takato Hirano, Koichiro Wada, and Keisuke Tanaka
Email: hirano6@is.titech.ac.jp
Abstract: C-253.txt
Document: C-253.pdf

ID: C-252(Febrary, 2008)
Title: A Variant of the Schmidt-Takagi Encryption Scheme
Authors: Takato Hirano, Koichiro Wada, and Keisuke Tanaka
Email: hirano6@is.titech.ac.jp
Abstract: C-252.txt
Document: C-252.pdf

ID: C-251(December, 2007)
Title: Public-key Steganography with Authentication
Authors: Hirotoshi Takebe and Keisuke Tanaka
Email: takebe3@is.titech.ac.jp
Abstract: C-251.txt
Document: C-251.pdf

ID: C-250(January, 2008)
Title: Key-Substitutable Signature and its Application to Certified Signature
Authors: Koichi Sakumoto and Keisuke Tanaka
Email: sakumot3@is.titech.ac.jp
Abstract: C-250.txt
Document: C-250.pdf

ID: C-249 (November, 2007)
Title: Concurrently Secure Identification Schemes and Ad Hoc Anonymous Identification Schemes Based on the Worst-Case Hardness of Lattice Problems
Authors: Akinori Kawachi, Keisuke Tanaka, and Keita Xagawa
Email: xagawa5@is.titech.ac.jp
Abstract: C-249.txt
Document: C-249.pdf

ID: C-248 (November, 2007)
Title: Belief Propagation and Spectral Methods
Authors: Masaki Yamamoto and Osamu Watanabe
Email: watanabe(at)is. titech. ac. jp
Abstract: C-248.txt
Document: C-248.pdf

ID: C-247 (November, 2007)
Title: Validating Correctness of Compiler Optimizer Execution Using Temporal Logic
Authors: Masataka Sassa and Soichiro Sahara
Email: sassa(at)is.titech.ac.jp
Abstract: C-247.txt
Document: C-247.pdf

ID: C-246(Nobember, 2007)
Title: Methodology for Coping with Heterogeneity of Modern Accelerators on a Massive Supercomputing Scale
Authors: Toshio Endo and Satoshi Matsuoka
Email: endo(at)matsulab.is.titech.ac.jp
Abstract: C-246.txt
Document: C-246.pdf

ID: C-245 (May, 2007)
Title: Weighted Random Popular Matchings
Authors: Toshiya Itoh and Osamu Watanabe
Email: watanabe(at)is.titech.ac.jp
Abstract: C-245.txt
Document: C-245.pdf

ID: C-244(April, 2007)
Title: Completeness Theorem of First-Order Modal mu-calculus
Authors: Ryo Kashima and Keishi Okamoto
Email: kashima@is.titech.ac.jp
Abstract: C-244.txt
Document: C-244.pdf

ID: C-243
Withdrawn (revised into C-244).
ID: C-242(February, 2007)
Title: Token-Controlled Public-Key Encryption in the Multi-User Setting
Authors: Ryotaro Hayashi and Keisuke Tanaka
Email: keisuke@is.titech.ac.jp
Abstract: C-242.txt
Document: C-242.pdf

ID: C-241(February, 2007)
Title: The Semantic Security and the Non-Malleability with the Randomness Revealed for Public-Key Encryption
Authors: Ryotaro Hayashi and Keisuke Tanaka
Email: keisuke@is.titech.ac.jp
Abstract: C-241.txt
Document: C-241.pdf

ID: C-240(January, 2007)
Title: An Efficient Parsing for Highly Ambiguous Context-Free Grammars Based on Pruning
Authors: Shin-ichi Morimoto
Email: s-morimoto@ah.jp.nec.com
Abstract: C-240.txt
Document: C-240.pdf

ID: C-239(January, 2007)
Title: Variations on Pseudo-Free Groups
Authors: Takato Hirano and Keisuke Tanaka
Email: hirano6@is.titech.ac.jp
Abstract: C-239.txt
Document: C-239.pdf

ID: C-238(December, 2006)
Title: Quantum Asymmetric-Key Cryptosystem Secure Against A Computationally Unbounded Adversary
Authors: Christopher Portmann and Akinori Kawachi
Email: christo5@is.titech.ac.jp
Abstract: C-238.txt
Document: C-238.pdf

ID: C-237(January, 2007)
Title: Key-Substitution Attacks on Group Signature
Authors: Koichi Sakumoto and Keisuke Tanaka
Email: sakumot3@is.titech.ac.jp
Abstract: C-237.txt
Document: C-237.pdf

ID: C-236(January, 2007)
Title: Proof of Plaintext Knowledge for the Regev Cryptosystems
Authors: Keita Xagawa, Akinori Kawachi, and Keisuke Tanaka
Email: xagawa5@is.titech.ac.jp
Abstract: C-236.txt
Document: C-236.pdf

ID: C-235(January, 2007)
Title: A Lattice-Based Cryptosystem and Proof of Knowledge on Its Secret Key
Authors: Keita Xagawa, Akinori Kawachi, and Keisuke Tanaka
Email: xagawa5@is.titech.ac.jp
Abstract: C-235.txt
Document: C-235.pdf

ID: C-234(December, 2006)
Title: Private Approximation of the Set Cover Problem
Authors: Masatoshi Yashiro and Keisuke Tanaka
Email: yashiro2@is.titech.ac.jp
Abstract: C-234.txt
Document: C-234.pdf

ID: C-233(December, 2006)
Title: Steganographic Signature
Authors: Hirotoshi Takebe and Keisuke Tanaka
Email: takebe3@is.titech.ac.jp
Abstract: C-233.txt
Document: C-233.pdf

ID: C-232(January, 2007)
Title: Constructions for Conditional Oblivious/Converge Transfer/Cast
Authors: Daisuke Inoue and Keisuke Tanaka
Email: inoue.d.aa@m.titech.ac.jp
Abstract: C-232.txt
Document: C-232.pdf

ID: C-231(December, 2006)
Title: An ID-based Combined Scheme with Encryption and Signature
Authors: Naoyuki Yamashita and Keisuke Tanaka
Email: yamashi1@is.titech.ac.jp
Abstract: C-231.txt
Document: C-231.pdf

ID: C-230(November, 2006)
Title: Generating Java Compiler Optimizers Using Bidirectional CTL
Authors: Ling Fang and Masataka Sassa
Email: {fang3,sassa}@is.titech.ac.jp
Abstract: C-230.txt
Document: C-230.pdf

ID: C-229(November, 2006)
Title: Secret Handshake with Multiple Groups
Authors: Naoyuki Yamashita and Keisuke Tanaka
Email: yamashi1@is.titech.ac.jp
Abstract: C-229.txt
Document: C-229.pdf

ID: C-228(November, 2006)
Title: The Security with the Randomness Revealed for Public-Key Encryption
Authors: Ryotaro Hayashi and Keisuke Tanaka
Email: hayashi9@is.titech.ac.jp
Abstract: C-228.txt
Document: C-228.pdf

ID: C-227 (Oct, 2006)
Title: Stringent Relativizaton
Authors: Jin-Yi Cai and Osamu Watanabe
Email: watanabe@is.titech.ac.jp
Abstract: C-227.txt
Document: C-227.pdf

ID: C-226(August, 2006)
Title: Public-Key Encryption with Masking
Authors: Ryotaro Hayashi and Keisuke Tanaka
Email: hayashi9@is.titech.ac.jp
Abstract: C-226.txt
Document: C-226.pdf

ID: C-225 (August, 2006)
Title: Average-case Analysis for the MAX-2SAT Problem
Authors: Osamu Watanabe and Masaki Yamamoto
Email: watanabe@is.titech.ac.jp
Abstract: C-225.txt
Document: C-225.pdf

ID: C-224(April, 2006)
Title: PA in the Two-Key Setting and a Generic Conversion for Encryption with Anonymity
Authors: Ryotaro Hayashi and Keisuke Tanaka
Email: hayashi9@is.titech.ac.jp
Abstract: C-224.txt
Document: C-224.pdf

ID: C-223(April, 2006)
Title: Computational Indistinguishability between Quantum States and Its Cryptographic Application
Authors: Akinori Kawachi, Takeshi Koshiba, Harumichi Nishimura, and Tomoyuki Yamakami
Email: kawachi@is.titech.ac.jp
Abstract: C-223.txt
Document: C-223.pdf

ID: C-222 (March, 2006)
Title: An extension of Azuma-Hoeffding inequality
Authors: Hayato Takahashi and Yasuaki Niikura
Email: Hayato.Takahashi@ieee.org
Abstract: C-222.txt
Document: C-222.pdf

ID: C-221(February, 2006)
Title: Experience in Testing Compiler Optimizers Using Comparison Checking
Authors: Masataka Sassa and Daijiro Sudo
Email: sassa@is.titech.ac.jp
Abstract: C-221.txt
Document: C-221.pdf

ID: C-220 (February, 2006)
Title: Aspect-Oriented Programming Meets Dependency Injection (in Japanese)
Authors: Rei Ishikawa and Shigeru Chiba
Email: chiba@is.titech.ac.jp
Abstract: C-220.txt
Document: C-220.pdf

ID: C-219(January, 2006)
Title: A detail analysis on factor oracle construction of computing repeated factors
Authors: Hisashi Iwasaki
Email: watanabe@is.titech.ac.jp
Abstract: C-219.txt
Document: C-219.pdf

ID: C-218(Dec, 2005)
Title: Robustness of Greedy Type Minimum Evolution Algorithms
Authors: Takeya Shigezumi
Email: Takeya.Shigezumi@is.titech.ac.jp
Abstract: C-218.txt
Document: C-218.ps.gz

ID: C-217(December, 2005)
Title: Error analysis of factor oracles
Authors: Hisashi Iwasaki
Email: watanabe@is.titech.ac.jp
Abstract: C-217.txt
Document: C-217.pdf

ID: C-216 (Dec, 2005)
Title: A Message Passing Algorithm for MAX2SAT
Authors: Osamu Watanabe and Masaki Yamamoto
Email: watanabe@is.titech.ac.jp
Abstract: C-216.txt
Document: C-216.pdf

ID: C-215 (December, 2005)
Title: Sanitizable Signature with Secret Information
Authors: Manabu Suzuki, Isshiki Toshiyuki, and Keisuke Tanaka
Email: keisuke@is.titech.ac.jp
Abstract: C-215.txt
Document: C-215.pdf

ID: C-214 (October, 2005)
Title: Comparison and Evaluation of Back-translation Algorithms for Static Single Assignment Forms
Authors: Masataka Sassa, Yo Ito, and Masaki Kohama
Email: sassa@is.titech.ac.jp
Abstract: C-214.txt
Document: C-214.pdf

ID: C-213 (August, 2005)
Title: The Complexity of Kings
Authors: Edith Hemaspaandra, Lane Hemaspaandra, and Osamu Watanabe
Email: watanabe@is.titech.ac.jp
Abstract: C-213.txt
Document: C-213.pdf

ID: C-212 (August, 2005)
Title: Simple Algorithms for Graph Partition Problems
Authors: Mikael Onsjo and Osamu Watanabe
Email: watanabe@is.titech.ac.jp
Abstract: C-212.txt
Document: C-212.pdf

ID: C-211(July, 2005)
Title: An Improved $\widetilde{\cal O}(1.234^m)$-Time Deterministic Algorithm for SAT
Authors: Masaki Yamamoto
Email: masaki.yamamoto@is.titech.ac.jp
Abstract: C-211.txt
Document: C-211.pdf

ID: C-210 (May, 2005)
Title: Distributions in the Ehrenfest Process
Authors: Srinivasan Balaji, Hosam Mahmound, and Osamu Watanabe
Email: watanabe@is.titech.ac.jp
Abstract: C-210.txt
Document: C-210.pdf

ID: C-209 (April, 2005)
Title: Hausdorff dimension and the Stochastic Traveling Salesman Problem
Authors: Hayato Takahashi
Email: Hayato.Takahashi@is.titech.ac.jp
Abstract: C-209.txt
Document: C-209.pdf

ID: C-208(February, 2005)
Title: Universal Anonymizable Public-Key Encryption
Authors: Ryotaro Hayashi and Keisuke Tanaka
Email: hayashi9@is.titech.ac.jp
Abstract: C-208.txt
Document: C-208.pdf

ID: C-207(December, 2004)
Title: Security for Authenticated Key Exchange Based on Non-Malleability
Authors: Hiroki Hada and Keisuke Tanaka
Email: keisuke@is.titech.ac.jp
Abstract: C-207.txt
Document: C-207.pdf

ID: C-206(December, 2004)
Title: A Cramer-Shoup Variant Related to the Quadratic Residuosity Problem
Authors: Harunaga Hiwatari and Keisuke Tanaka
Email: hiwatar1@is.titech.ac.jp
Abstract: C-206.txt
Document: C-206.ps.gz

ID: C-205(December, 2004)
Title: A Criterion and Schemes on the Random Oracle Model
Authors: Manabu Suzuki, Keisuke Tanaka
Email: suzuki1@is.titech.ac.jp
Abstract: C-205.txt
Document: C-205.pdf

ID: C-203 (December, 2004)
Title: Universal Designated-Verifier Signature with Aggregation
Authors: Akihiro Mihara and Keisuke Tanaka
Email: keisuke@is.titech.ac.jp
Abstract: C-203.txt
Document: C-203.pdf

ID: C-202(December, 2004)
Title: A Model and Methods for Moderately-Hard Functions
Authors: Takao Onodera and Keisuke Tanaka
Email: onodera0@is.titech.ac.jp
Abstract: C-202.txt
Document: C-202.pdf

ID: C-201(December, 2004)
Title: The Sampling Twice Technique for the RSA-based Cryptosystems with Anonymity
Authors: Ryotaro Hayashi and Keisuke Tanaka
Email: hayashi9@is.titech.ac.jp
Abstract: C-201.txt
Document: C-201.pdf

ID: C-200(November, 2004)
Title: ElGamal and Cramer-Shoup Variants with Anonymity Using Different Groups (Extended Abstract)
Authors: Ryotaro Hayashi and Keisuke Tanaka
Email: hayashi9@is.titech.ac.jp
Abstract: C-200.txt
Document: C-200.pdf

ID: C-199 (September, 2004)
Title: Random Access to Advice Strings and Collapsing Results
Authors: Jin-Yi Cai and Osamu Watanabe
Email: watanabe@is.titech.ac.jp
Abstract: C-199.txt
Document: C-199.pdf

ID: C-198 (September, 2004)
Title: Pseudo Expectation: A Tool for Analyzing Local Search Algorithms
Authors: Osamu Watanabe
Email: watanabe@is.titech.ac.jp
Abstract: C-198.txt
Document: C-198.pdf

ID: C-197 (September, 2004)
Title: Another proof for an upper bound of a local search algorithm for 3-SAT
Authors: Masaki Yamamoto
Email: yamamot3@is.titech.ac.jp
Abstract: C-197.txt
Document: C-197.ps.gz

ID: C-196 (August, 2004)
Title: RAM-SE'04 --- ECOOP'04 Workshop on Reflection, AOP, and Meta-Data for Software Evolution
Editors: Walter Cazzola, Shigeru Chiba, and Gunter Saake
Email:
Abstract: C-196.txt
Document: C-196.pdf

ID: C-195 (June, 2004)
Title: An Error Bound for the Pseudo Expectation: 1D Case
Authors: Osamu Watanabe and Johannes Schneider
Email: watanabe@is.titech.ac.jp
Abstract: C-195.txt
Document: C-195.ps.gz

ID: C-194 (June, 2004)
Title: Learning r-of-k Functions by Boosting
Authors: Kohei Hatano and Osamu Watanabe
Email: watanabe@is.titech.ac.jp
Abstract: C-194.txt
Document: C-194.ps.gz

ID: C-193 (June, 2004)
Title: Shuffle for Paillier's Encryption Scheme
Authors: Takao Onodera and Keisuke Tanaka
Email: onodera0@is.titech.ac.jp
Abstract: C-193.txt
Document: C-193.ps.gz

ID: C-192(May, 2004)
Title: A New Method and Analysis of Anonymous Public-Key Cryptosystems (Extended Abstract)
Authors: Ryotaro Hayashi and Keisuke Tanaka
Email: hayashi9@is.titech.ac.jp
Abstract: C-192.txt
Document: C-192.ps.gz

ID: C-191 (February, 2004)
Title: On Generating Instances for MAX2SAT with Optimal Solutions
Authors: Masaki Yamamoto
Email: masaki.yamamoto@is.titech.ac.jp
Abstract: C-191.txt
Document: C-191.ps.gz

ID: C-190 (February, 2004)
Title: Finding Maximal Repeats with Factor Oracles
Author: Ryoichi Kato
Email: watanabe@is.titech.ac.jp
Abstract: C-190.txt
Document: C-190.ps.gz

ID: C-189 (January, 2004)
Title: Short Signatures with Message Recovery in the Random Oracle Model
Authors: Akihiro Mihara and Keisuke Tanaka
Email: mihara0@is.titech.ac.jp
Abstract: C-189.txt
Document: C-189.ps.gz

ID: C-188(January, 2004)
Title: A Verifiable Secret Shuffle of the Paillier's Encryption Scheme
Authors: Takao Onodera and Keisuke Tanaka
Email: onodera0@is.titech.ac.jp
Abstract: C-188.txt
Document: C-188.ps.gz

ID: C-187(January, 2004)
Title: Ring Signatures in the Random Oracle Model(Extended Abstract)
Authors: Toshiyuki Isshiki and Keisuke Tanaka
Email: isshiki9@is.titech.ac.jp
Abstract: C-187.txt
Document: C-187.ps.gz

ID: C-186 (December, 2003)
Title: The Complexity of Routing Strategies in Update Networks
Authors: Crasmaru Marcel and Shinya Umeno
Email: umeno1@is.titech.ac.jp
Abstract: C-186.txt
Document: C-186.ps.gz

ID: C-185 (December, 2003)
Title: A New Full-Text Search Algorithm Using Factor Oracle as Index
Authors: Ryoichi Kato
Email: Ryoichi.Kato@is.titech.ac.jp
Abstract: C-185.txt
Document: C-185.ps.gz

ID: C-184 (December, 2003)
Title: On Unique Pigeon Hole Principles
Authors: Marcel Crasmaru and Osamu Watanabe
Email: watanabe@is.titech.ac.jp
Abstract: C-184.txt
Document: C-184.ps.gz

ID: C-183(November, 2003)
Title: An RSA Family of Trap-door Permutations with a Common Domain and its Applications (Revised)
Authors: Ryotaro Hayashi, Tatsuaki Okamoto, and Keisuke Tanaka
Email: hayashi9@is.titech.ac.jp
Abstract: C-183.txt
Document: C-183.ps.gz

ID: C-182 (November, 2003)
Title: An Efficient (n-t)-out-of-n Threshold Ring Signature Scheme
Authors: Toshiyuki Isshiki and Keisuke Tanaka
Email: isshiki9@is.titech.ac.jp
Abstract: C-182.txt
Document: C-182.ps.gz

ID: C-181 (July, 2003)
Title: An Efficient Anonymous Group Identification Scheme with Short Secret Keys
Authors: Toshiyuki Isshiki and Keisuke Tanaka
Email: isshiki9@is.titech.ac.jp
Abstract: C-181.txt
Document: C-181.ps.gz

ID: C-180(July, 2003)
Title: Generalized Systematic Debugging Method for Attribute Grammars
Authors: Akira Sasaki and Masataka Sassa
Email: sassa@is.titech.ac.jp
Abstract: C-180.txt
Document: C-180.ps.gz

ID: C-179 (July, 2003)
Title: A New Text Search Algorithm Using Factor Oracle as Full-Text Index
Author: Ryoichi Kato
Email: watanabe@is.titech.ac.jp
Abstract: C-179.txt
Document: C-179.ps.gz

ID: C-178(June, 2003)
Title: Limiting Negations in Bounded-Depth Circuits: An Extension of Markov's Theorem
Authors: Shao Chin Sung and Keisuke Tanaka
Email: keisuke@is.titech.ac.jp
Abstract: C-178.txt
Document: C-178.ps.gz

ID: C-177 (June, 2003)
Title: Instance generating algorithms for MAX2SAT with optimal solutions
Authors: Masaki Yamamoto
Email: masaki.yamamoto@is.titech.ac.jp
Abstract: C-177.txt
Document: C-177.ps.gz

ID: C-176(May, 2003)
Title: RSA Family of Trap-door Permutations with a Common Domain and its Applications (Extended Abstract)
Authors: Ryotaro Hayashi, Tatsuaki Okamoto, and Keisuke Tanaka
Email: hayashi9@is.titech.ac.jp
Abstract: C-176.txt
Document: C-176.ps.gz

ID: C-175 (April, 2003)
Title: On the Degree of Multivariate Polynomials over Fields of Characteristic 2
Authors: Marcel Crasmaru
Email: watanabe@is.titech.ac.jp
Abstract: C-175.txt
Document: C-175.ps.gz

ID: C-174 (February, 2003)
Title: Density Attack on the Knapsack Cryptosystems with Enumerative Source Encoding (Extended Abstract)
Authors: Keiji Omura, and Keisuke Tanaka
Email: keisuke@is.titech.ac.jp
Abstract: C-174.txt
Document: C-174.ps.gz

ID: C-173 (February, 2003)
Title: Analysis of a Randomized Local Search Algorithm for LDPCC Decoding Problem
Authors: Osamu Watanabe and Takeshi Sawai
Email: watanabe@is.titech.ac.jp
Abstract: C-173.txt
Document: C-173.ps.gz

ID: C-172(February, 2003)
Title: Improved Constructions of Quantum Bit-Commitment Based on Quantum One-Way Permutations
Authors: Toshiyuki Isshiki and Keisuke Tanaka
Email: isshiki9@is.titech.ac.jp
Abstract: C-172.txt
Document: C-172.ps.gz

ID: C-171 (February, 2003)
Title: Key-Privacy in Digital Signature (Extended Abstract)
Authors: Ryotaro Hayashi and Keisuke Tanaka
Email: hayashi9@is.titech.ac.jp
Abstract: C-171.txt
Document: C-171.ps.gz

ID: C-170 (February, 2003)
Title: On Routing in Update Networks
Authors: Crasmaru Marce
Email: watanabe@is.titech.ac.jp
Abstract: C-170.txt
Document: C-170.ps.gz

ID: C-169 (Februrary, 2003)
Title: Relativized Collapsing Results under Stringent Oracle Access
Authors: Jin-Yi Cai and Osamu Watanabe
Email: watanabe@is.titech.ac.jp
Abstract: C-169.txt
Document: C-169.ps.gz

ID: C-168 (Februrary, 2003)
Title: BPP = PH by Polynomially Stringent Relativization
Authors: Jin-Yi Cai and Osamu Watanabe
Email: watanabe@is.titech.ac.jp
Abstract: C-168.txt
Document: C-168.ps.gz

ID: C-167 (Februrary, 2003)
Title: On Proving Circuit Lower Bounds Against the Polynomial-time Hierarchy: Positive / Negative Results and Some Related Lower Bounds for Constant Depth Circuits
Authors: Jin-Yi Cai and Osamu Watanabe
Email: watanabe@is.titech.ac.jp
Abstract: C-167.txt
Document: C-167.ps.gz

ID: C-166 (January, 2003)
Title: Quantum Bit-Commitment for Small Strage Based on Quantum One-Way Permutations
Authors: Toshiyuki Isshiki, Keisuke Tanaka
Email: isshiki9@is.titech.ac.jp
Abstract: C-166.txt
Document: C-166.ps.gz

ID: C-165(January, 2003)
Title: A Proof-Theoretical Study on Logics with Constructible Falsity
Authors: HASUO Ichiro and KASHIMA Ryo
Email: hasuo2@is.titech.ac.jp
Abstract: C-165.txt
Document: C-165.ps.gz

ID: C-164(December, 2002)
Title: Jarcler: Aspect-Oriented Middleware for Distributed Software in Java
Authors: Muga Nishizawa and Shigeru Chiba
Email: muga@csg.is.titech.ac.jp
Abstract: C-164.txt
Document: C-164.ps.gz

ID: C-163 (June, 2002)
Title: On the Influence of Outliers in the Support Vector Machine Framework
Authors: Yang Dai, Jun'ichi Tanaka, and Osamu Watanabe
Email: watanabe@is.titech.ac.jp
Abstract: C-163.txt
Document: C-163.ps.gz

ID: C-162 (May, 2002)
Title: How Can Computer Science Contribute to Knowledge Discovery?
Authors: Osamu Watanabe
Email: watanabe@is.titech.ac.jp
Abstract: C-162.txt
Document: C-162.ps.gz

ID: C-161 (May, 2002)
Title: On Proving Circuit Lower Bounds Against the Polynomial-time Hierarchy: Positive and Negative Results
Authors: Jin-Yi Cai and Osamu Watanabe
Email: watanabe@is.titech.ac.jp
Abstract: C-161.txt
Document: removed (see C-256)

ID: C-160 (May, 2002)
Title: Provably Fast Training Algorithms for Support Vector Machines
Authors: Jose Balcazar, Yang Dai, Junichi Tanaka, and Osamu Watanabe
Email: watanabe@is.titech.ac.jp
Abstract: C-160.txt
Document: C-160.ps.gz

ID: C-159 (April, 2002)
Title: Linear Logics with Communication Merge
Authors: Norihiro Kamide
Email: kamide2@is.titech.ac.jp
Abstract: C-159.txt
Document: not available

ID: C-158 (April, 2002)
Title: Normal Modal Substructural Logics with Strong Negation
Authors: Norihiro Kamide
Email: kamide2@is.titech.ac.jp
Abstract: C-158.txt
Document: not available

ID: C-157 (November, 2001)
Title: Proof Theoretical Studies on Semilattice Relevant Logics
Authors: Ryo Kashima
Email: kashima@is.titech.ac.jp
Abstract: C-157.txt
Document: C-157.ps.gz

ID: C-156 (November, 2001)
Title: Sequential Sampling Algorithms: Unified Analysis and Lower Bounds
Authors: Ricard Gavalda and Osamu Watanabe
Email: watanabe@is.titech.ac.jp
Abstract: C-156.txt
Document: C-156.ps.gz

ID: C-155 (November, 2001)
Title: Games with a Unique Solution Property
Authors: Shin Aida, Marcel Crasmaru, Kenneth Regan, and Osamu Watanabe
Email: watanabe@is.titech.ac.jp
Abstract: C-155.txt
Document: C-155.ps.gz

ID: C-154(October, 2001)
Title: Mathematical Analysis of a Correlation-Based Model for Orientation Map Formation
Authors: YAMAZAKI Tadashi
Email: tyam@is.titech.ac.jp
Abstract: C-154.txt
Document: C-154.ps.gz

ID: C-153(August, 2001)
Title: Random Instance Generation for MAX 3SAT
Authors: Mitsuo Motoki
Email: watanabe@is.titech.ac.jp
Abstract: C-153.txt
Document: C-153.ps.gz

ID: C-152(May, 2001)
Title: Analyses of Multi-Way Branching Decision Tree Boosting Algorithms
Authors: Kohei Hatano
Email: hatano@is.titech.ac.jp
Abstract: C-152.txt
Document: C-152.ps.gz

ID: C-151 (May, 2001)
Title: AM is contained in QMA
Authors: Tatsuaki Okamoto, Keisuke Tanaka, and Osamu Watanabe
Email: watanabe@is.titech.ac.jp
Abstract: C-151.txt
Document: C-151.ps.gz

ID: C-150(5, 2001)
Title: Graph Non-Isomorphism Has a Succinct Quantum Certificate
Authors: Tatsuaki Okamoto and Keisuke Tanaka
Email: keisuke@is.titech.ac.jp
Abstract: C-150.txt
Document: C-150.ps.gz

ID: C-149 (April, 2001)
Title: An Application of a Random Sampling Technique to Primal-Form Maximal-Margin Classifiers\\
Authors: Jose Balcazar, Yang Dai, and Osamu Watanabe
Email: watanabe@is.titech.ac.jp
Abstract: C-149.txt
Document: C-149.ps.gz

ID: C-148 (February, 2001)
Title: Deterministic Application of Grover's Quantum Search Algorithm
Authors: Kyoichi Okamoto and Osamu Watanabe
Email: watanabe@is.titech.ac.jp
Abstract: C-148.txt
Document: C-148.ps.gz

ID: C-147(Feb, 2001)
Title: A Mathematical Analysis of Development of Oriented Receptive Fields in Linsker's Model (revised version)
Authors: YAMAZAKI Tadashi
Email: tyam@is.titech.ac.jp
Abstract: C-147.txt
Document: C-147.ps.gz

ID: C-146 (February, 2001)
Title: An Improved Randomized Algorithm for 3-SAT
Authors: Rainer Schuler, Uwe Schoening, and Osamu Watanabe
Email: watanabe@is.titech.ac.jp
Abstract: C-146.txt
Document: C-146.ps.gz

ID: C-145 (August, 2000)
Title: A Proof of the Standardization Theorem in Lambda-Calculus
Authors: Ryo Kashima
Email: kashima@is.titech.ac.jp
Abstract: C-145.txt
Document: C-145.ps.gz

ID: C-144(Jul, 2000)
Title: A Mathematical Analysis of Development of Oriented Receptive Fields in Linsker's Model (revised version)
Authors: YAMAZAKI Tadashi
Email: tyam@is.titech.ac.jp
Abstract: C-144.txt
Document: C-144.ps.gz

ID: C-143 (June, 2000)
Title: On the Difference between Polynomial-Time Many-One and Truth-Table Reducibilities on Distributional Problems
Authors: Shin Aida, Rainer Schuler, Tatsuie Tsukiji, and Osamu Watanabe
Email: watanabe@is.titech.ac.jp
Abstract: C-143.txt
Document: C-143.ps.gz

ID: C-142(June, 2000)
Title: Ladders are PSPACE-Complete
Authors: Marcel Crasmaru and John Tromp
Email: marcel@is.titech.ac.jp
Abstract: C-142.txt
Document: C-142.ps.gz

ID: C-141(May, 2000)
Title: On the Maximum Satisfiability of Random 3-CNF Formulae
Authors: Mitsuo Motoki
Email: Mitsuo Motoki
Abstract: C-141.txt
Document: C-141.ps.gz

ID: C-140 (December, 1999)
Title: Labelled Sequent Calculi and Completeness Theorems for Implicational Relevant Logics
Authors: Ryo Kashima
Email: kashima@is.titech.ac.jp
Abstract: C-140.txt
Document: C-140.ps.gz

ID: C-139 (December, 1999)
Title: Experimental evaluation of an adaptive boosting by filtering algorithm
Authors: Carlos Domingo and Osamu Watanabe
Email: watanabe@is.titech.ac.jp
Abstract: C-139.txt
Document: C-139.ps.gz

ID: C-138 (December, 1999)
Title: MadaBoost: A modification of AdaBoost
Authors: Carlos Domingo and Osamu Watanabe
Email: watanabe@is.titech.ac.jp
Abstract: C-138.txt
Document: C-138.ps.gz

ID: C-137 (October, 1999)
Title: Simple Sampling Techniques for Discovery Science
Authors: Osamu Watanabe
Email: watanabe@is.titech.ac.jp
Abstract: C-137.txt
Document: C-137.ps.gz

ID: C-136 (September, 1999)
Title: Adaptive Sampling Methods for Scaling Up Knowledge Discovery Algorithms (Extended Revised Version)
Authors: Carlos Domingo, Ricard Gavalda, and Osamu Watanabe
Email: watanabe@is.titech.ac.jp
Abstract: C-136.txt
Document: C-136.ps.gz

ID: C-135 (August, 1999)
Title: A Mathematical Analysis of Development of an Oriented Receptive Field on Linsker's Model
Authors: YAMAZAKI Tadashi
Email: tyam@is.titech.ac.jp
Abstract: C-135.txt
Document: C-135.ps.gz

ID: C-134 (July, 1999)
Title: A characterization of some linear cellular automata
Authors: Cr\^a\c smaru Marcel
Email: marcel@is.titech.ac.jp
Abstract: C-134.txt
Document: C-134.ps.gz

ID: C-133 (July, 1999)
Title: A Modification of AdaBoost: A Preliminary Report
Authors: Carlos Domingo and Osamu Watanabe
Email: watanabe@is.titech.ac.jp
Abstract: C-133.txt
Document: C-133.ps.gz

ID: C-132 (April, 1999)
Title: >>>From Computational Learning Theory to Discovery Science
Authors: Osamu Watanabe
Email: watanabe@is.titech.ac.jp
Abstract: C-132.txt
Document: C-132.ps.gz

ID: C-131 (April, 1999)
Title: Adaptive Sampling Methods for Scaling Up Knowledge Discovery Algorithms
Authors: Carlos Domingo, Ricard Gavalda, and Osamu Watanabe
Email: watanabe@is.titech.ac.jp
Abstract: C-131.txt
Document: C-131.ps.gz

ID: C-130(February, 1999)
Title: Super-Polynomial versus Half-Exponential Circuit Size in the Exponential Hierarchy
Authors: P.B. Miltersen, N.V. Vinodchandran, and O. Watanabe
Email: watanabe@is.titech.ac.jp
Abstract: C-130.txt
Document: C-130.ps.gz

ID: C-129 (January, 1999)
Title: Unique Solution Instance Generation for the 3-Satisfiability (3SAT) Problem
Authors: Mitsuo Motoki, and Ryuhei Uehara
Email: mmotoki@is.titech.ac.jp
Abstract: C-129.txt
Document: C-129. ps.gz

ID: C-128 (January, 1999)
Title: A Mathematical Analysis of a Correlation Based Model of Orientation Selectivity
Authors: Tadashi Yamazaki
Email: tyam@is.titech.ac.jp
Abstract: C-128.txt
Document: C-128.ps.gz

ID: C-127 (December, 1998)
Title: Theoretical Analysis of Algorithms for On-line Selection
Authors: Carlos Domingo, Ricard Gavalda, and Osamu Watanabe
Email: watanabe@is.titech.ac.jp
Abstract: C-127.txt
Document: C-127.ps.gz

ID: C-126 (December, 1998)
Title: On-Line Sampling Methods for Discovering Association Rules
Authors: Carlos Domingo, Ricard Gavalda, and Osamu Watanabe
Email: watanabe@is.titech.ac.jp
Abstract: C-126.txt
Document: C-126.ps.gz

ID: C-125 (November, 1998)
Title: Comparison of Initial Conditions for Distributed Algorithms on Anonymous Networks
Authors: Naoshi Sakamoto
Email: sakamoto@noc.titech.ac.jp
Abstract: C-125.txt
Document: C-125.ps.gz

ID: C-124 (July, 1998)
Title: A role of constraint in self-organization
Authors: Carlos Domingo, Osamu Watanabe, and Tadashi Yamazaki
Email: watanabe@is.titech.ac.jp
Abstract: C-124.txt
Document: C-124.ps.gz

ID: C-123 (July, 1998)
Title: Practical algorithms for on-line sampling
Authors: Carlos Domingo, Ricard Gavalda, and Osamu Watanabe
Email: watanabe@is.titech.ac.jp
Abstract: C-123.txt
Document: C-123.ps.gz

ID: C-122 (April, 1998)
Title: $\lambda$-representable functions over free structures revisited
Author: Masako Takahashi
Email: masako@is.titech.ac.jp
Abstract: C-122.txt
Document: not available

ID: C-121 (April, 1998)
Title: Intersection and singleton type assignment characterizing finite B"ohm-trees
Author: Toshihiko Kurata
Email: kurata@is.titech.ac.jp
Abstract: C-121.txt
Document: not available

ID: C-120 (April, 1998)
Title: A type theoretical view of B"ohm-trees
Author: Toshihiko Kurata
Email: kurata@is.titech.ac.jp
Abstract: C-120.txt
Document: not available

ID: C-118 (January, 1998)
Title: Concurrent transactions and communicators: extensible synchronization mechanisms for distributed programming
Authors: Ken Wakita and Yoshiki Ohshima
Email: wakita@is.titech.ac.jp
Abstract: C-118.txt
Document: C-118.ps.gz

ID: C-117 (January, 1998)
Title: Systematic debugging method for attribute grammar description
Authors: Masataka Sassa and Takuya Ookubo
Email: sassa@is.titech.ac.jp
Abstract: C-117.txt
Document: C-117.ps.gz

Last Update: 2011. 10. 28 by N.Katagai