山本研特別ゼミ

興味のある方は,自由に参加して下さい.開催案内通知をメールで欲しい人は山本(Hirosuke (at) ieee.org)まで申し出て下さい。

(注意:講演者の所属は,開催日当時の所属です。)

第27回,2017年10月24日(火),東京大学 東京大学柏キャンパス基盤棟5階 5H6-2室

  • 14:00-15:30(ごろ)
  • 講演者:Danny Dub\'{e}(Universit\{e} Laval)
  • 講演タイトル: Towards Optimal Almost-Instantaneous Variable-to-Fixed Codes
  • 概要:Variable-to-fixed codes are often based on dictionaries that obey the prefix-free property. In particular, the Tunstall algorithm builds such codes. However, the prefix-free property is not necessary to have correct variable-to-fixed codes. Removing the constraint to obey the prefix-free property may offer the opportunity to build more efficient codes. Here, we come back on the almost instantaneous variable-to-fixed codes presented in a paper by Yamamoto and Yokoo that appeared in 2001. They considered both cases of single trees and multiple trees to perform the parsing of the source string. We show that, in some cases, their techniques build suboptimal codes. We also propose a new, completely different technique based on dynamic programming that build optimal (individual) dictionary trees. Our technique does not take into account the notion of joint efficiency of a family of trees in the case of multiple trees. This work is under progress.

第26回,2017年1月28日(土),東京大学 柏フューチャーセンター2階会議室(205号室)

  • 15:00-16:30(ごろ)
  • 講演者:Ulrich Speidel(The University of Auckland)
  • 講演タイトル: Can network coding bridge the digital divide in Pacific Island countries?
  • 概要:Internet connecitivity in many Pacific Island nations relies on expensive satellite Internet links with low bandwidth and high latency. Many islands cannot afford submarine fibre cables because of small populations, low per-capita GDP, huge distances and a mostly very deep ocean. To add insult to injury, many ISPs in the islands struggle to utilise the full capacity of their satellite links. The cause of this problem is TCP queue oscillation, an effect discovered decades ago - and widely considered solved through the evolution of TCP/IP stacks. However, we show that it does still occur across satellite links where a large number of TCP senders share the same bandwidth into the island. We demonstrate that coding packets allows at least some TCP flows to recoup some of the capacity lost to queue oscillation, and report about ongoing work to simulate whole-of-island network coding of traffic.

第25回,2015年10月24日(土),東京大学 柏キャンパス 新領域基盤棟5階複雑理工学専攻セミナー室(5D6室)

  • 16:00-17:00(ごろ)
  • 講演者:Marat Burnashev(ロシア科学アカデミー,東京大学)
  • 講演タイトル: ON RELIABILITY FUNCTION OF BSC: EXPANDING THE REGION, WHERE IT IS KNOWN EXACTLY
  • 概要:On the exact form of the BSC(p) reliability function E(R,p), till 2006 it was known only in the region [R_crit,C] (it is the "sphere-packing bound"), where R_crit is some critical rate. In 2006-2007 it was shown that in the region [R_1,Rcrit] the reliability function E(R,p) is a piece of a "straight line", where R_1 is another critical rate and R_1 < R_crit.In the talk it will be shown that such form remains valid for a wider region [R_2,Rcrit], where R_2 < R_1.

第24回,2015年1月6日(火),東京大学 柏キャンパス 基盤棟2階 基盤棟共通セミナー室(2C5/2C7室)

  • 一人目の講演 14:30-15:40 (講演1時間+質疑10分)
  • 講演者:松本隆太郎(東京工業大学)
  • 講演タイトル: Quantum Strongly Secure Ramp Secret Sharing
  • 概要:It is well-known that the ramp (or non-perfect) secret sharing schemes reduce share size. This benefit also exists in the quantum ramp secret sharing, in which secret and shares are quantum information. The first and only quantum ramp secret sharing was proposed by Ogawa et al., which encodes vector indices of quantum secret into coefficients of a polynomial over a finite field $F_q$. Ogawa et al.'s scheme has two drawbacks, namely, (1) it does not control how information is leaked to a non-qualified set of shares, and (2) the dimension $q$ of quantum shares must be larger than the number of shares, because a share is constructed by evaluation of a polynomial at distinct non-zero elements in $F_q$. We propose new quantum ramp schemes to overcome (1) and (2). To overcome (1), we introduce a quantum version of the strong security proposed by H. Yamamoto for classical ramp schemes, which ensures a non-qualified set of shares has zero information about parts of secret, then we provide an explicit construction of quantum strongly secure ramp schemes based on the classical strongly secure ramp schemes. If there is extra time, a solution to (2) is discussed. The first part is DOI:10.1007/s11128-014-0863-2 and the second is arXiv:1405.0149.

  • 15:40-16:50 :休憩


  • 二人目の講演 16:50-17:00 (講演1時間+質疑10分)
  • 講演者:Terence Chan(University of South Australia)
  • 講演タイトル: Aspects of Distributed Data Storage
  • 概要:The era of Big Data has presented both opportunities and challenges. Data loss or system unavailability (caused by hardware failures, malicious attacks or natural disasters) is unavoidable, and in fact commonplace in any large-scale storage system. The challenge is to provide low cost, reliable and secure data storage, while being able to efficiently access data, update data and recover from (or be impervious to) failure of system components. Recently, coding for distributed data storage has received a lot attention. In this talk, we will review some recent results in the area. Linear programming bounds for storage codes will also be introduced and a graph based storage code construction will be proposed.

第23回,2014年5月31日(土),東京大学 柏フューチャーセンター2階会議室

  • 13:00-15:00(ごろ)
  • 講演者:岩田賢一(福井大学)
  • 講演タイトル: 部分列数え上げデータ圧縮法のアルゴリズムと性能評価について
  • 概要:2010年のData Compression Conference (DCC)において,DubeとBeaudoinに より提案された Lossless Data Compression via Substring Enumeration(CSE) について,原型のアルゴリズムからはじめ,CSEの特徴,最近まで進展を紹介 する.CSEは圧縮する系列の最後尾と先頭を連結することで巡回系列と見なし, 巡回系列の部分列の数え上げ回数が満たす特徴を利用して効率的に符号化と 復号化を行う.今回の発表では,CSEのMarkov情報源に対するユニバーサル性を, Dubeと横尾がISIT2011で発表した結果に基づき紹介とともに,その後の発展や 拡張について話題としたい.

第22回,2013年8月9日(金),東京大学 柏キャンパス 基盤棟5階 山本-國廣研セミナー室 (5F4室)

  • 10:00-12:00(ごろ)
  • 講演者:有村光晴(湘南工科大学)
  • 講演タイトル: 定常情報源で成立する2つの性質に対する情報スペクトル理論を用いた必要十分条件
  • 概要:本発表では,定常情報源に対しては当然成立する性質を2つ考え,これに対して情報スペクトル理論を用いることで,非定常情報源を含むより広いクラスにおいて必要十分条件が与えられることを示す. まず,FF符号に対して符号化レートと理想符号長の差を冗長度として定義し,その最適値が,古賀によって定義されたエントロピースペクトルの漸近的な幅W(X)に一致することを示す.次に,符号化レートと冗長度を用いた基準でそれぞれ最適な符号のクラス(レート最適な符号クラスと冗長度最適な符号クラス)を定義し,2つの符号クラスの包含関係が,W(X)の上界と下界を示す不等式を用いて与えられることを示す.最終的に,レート最適な符号クラスと冗長度最適な符号クラスが等しくなるための必要十分条件を与える. また,全てのレート最適なFF符号の符号化レートが収束するための条件についても考察し,これについても必要十分条件を与える. これら2つの必要十分条件は,定常情報源を含む非定常情報源のあるクラスとして与えられるので,情報スペクトル的方法を用いた非定常情報源クラスの解析の有用性が示される.

第21回,2011年11月18日(金),東京大学 柏キャンパス 基盤棟2階 基盤棟共通セミナー室(2C5/2C7室)

  • 16:00-17:10(ごろ)
  • 講演者:Marat Burnashev (ロシア科学アカデミー,東京大学)
  • 講演タイトル: On channels without feedback, with noiseless feedback and with noisy feedback: review and new results
  • 概要:Since Shannon (1961) it is known that even the noiseless feedback does not increase the (memoryless) channel capacity. But it allows to improve the decoding error probability of information transmision and to simplify transmission methods. During 60-80's possibility of such improvement were shown by many authors (different channels, constraints, etc.). All those results were heavily based on the assumption that the feedback channel is NOISELESS. For a rather long time it was not known whether it is possible to get similar improvements if the feedback channel is noisy. The first result showing possibility of such improvements was obtained by Burnashev-Yamamoto in 2008 (and developed further in 2008-2010). In the talk those results and some new ones will be presented.

第20回,2010年12月8日(水),東京大学 柏キャンパス 基盤棟2階 複雑理工学専攻講義室(2D5室)

  • 15:30-17:00(ごろ)
  • 講演者:Terence Chan (University of South Australia)
  • 講演タイトル: Aspects of information inequalities and their applications
  • 概要:Information inequalities are well-known as the basic laws governing the fundamental limits in data transmission and compression. These inequalities are also closely related to different areas including matroid theory, group theory, linear algebra, algorithmic complexity, determinantal inequalities and others.
    In this talk, we will cover several interesting aspects of information inequalities and entropic polymatroids. Relations between inequalities for groups and information inequalities will be derived and properties for entropic polymatroids induced by groups and vector spaces will be discussed. Recent progress in deriving subspace rank inequalities will also be included. Finally, we will describe how to use information inequalities to characterise the throughput of a network.

第19回,2010年9月29日(水),東京大学 柏キャンパス 基盤棟2階 複雑理工学専攻講義室(2D5室)

  • 15:00-17:00(ごろ)
  • 講演者:Ulrich Speidel (オークランド大学,東京大学)
  • 講演タイトル: Practical applications of T-codes, T-complexity and associated information measures in compression evaluation, event/anomaly detection and secure authentication
  • 概要:I will give a brief introduction into T-complexity as a refresher. I will then demonstrate the use of our command-line research T-decomposition tool ftd and will discuss the impact of factors such as alphabet size on practical estimation. As a first example, I will present recent results of experimental work by Raimund Eimann and myself which looked at the entropy produced by the SILK codec used in the Skype Internet telephony service. If I can get this set up on a Mac here, I will also demonstrate an audio input "entropy meter" developed by Mark Titchener that incorporates the ftd tool. A second example is a cooperation with Kazuo Ohzeki from Shibaura Institute of Technology: in 2005, we looked at entropy measurements on reference frame sequences used in the testing and evaluation of MPEG-2 video compression. Among other things, we were able to demonstrate that the original unencoded frame sequences contain a hum that affects colour resolution between even and odd frames in! the sequences that had not previously been noticed. We were also able to show that the entropy along and MPEG-2 encoded bitstream is not uniform but has noticeable sections of higher and lower entropy, suggesting potential for improvement. I will then present experimental results from Raimund Eimann's PhD research. They demonstrate how T-complexity can be used to detect events on computer networks. Finally, I will present a secure authentication scheme that Aaron Gulliver and I have recently proposed. It uses variable-length codes and I will argue that T-codes meet many if not all of the requirements of the scheme.
  • T-Code Generator (made by Ulrich Speidel) is available here.

第18回,2010年9月2日(木),東京大学 柏キャンパス 基盤棟2階 複雑理工学専攻講義室(2D5室)

  • 15:00-17:00(ごろ)
  • 講演者:Ulrich Speidel (オークランド大学,東京大学)
  • 講演タイトル: From T-codes to T-complexity and information measures
  • 概要:This lecture gives a very brief refresher on T-code construction. It then discusses the significance of the longest codewords in T-codes and shows how T-decomposition can be used to derive the full code from the knowledge of one of its longest codewords. The lecture also demonstrates how any finite string can be converted into a unique T-code in this way, giving rise to a duality between finite strings and T-codes. The copy-and-append process that is used in the construction of T-codes can thus also be applied to the construction of strings. Titchener proposed to use the number of steps in this process as a measure of complexity for the string. Each step is weighted by the log of the number of copies made. We will discuss the physical "meaning" of this measure. I will discuss the parallels to another measure, the Lempel-Ziv production complexity, which was proposed in 1976. Sadly, too few people know about it: Lempel and Ziv are much better known for their subsequent LZ77 and LZ78 compression algorithms. These are based on the same parsing principle and have also been used for complexity estimation. The lecture discusses the parallels and differences between the approaches and offers some experimental evidence to demonstrate that T-complexity is a useful estimator. I will also talk about open problems in the area.

第17回,2010年7月28日(水),東京大学 柏キャンパス 基盤棟2階 複雑理工学専攻講義室(2D5室)

  • 15:00-17:00(ごろ)
  • 講演者:Ulrich Speidel (オークランド大学,東京大学)
  • 講演タイトル: A general introduction to T-codes and T-code synchronisation
  • 概要:This talk is aimed at an audience with a fundamental understanding of bits and serial communication, e.g., someone who knows what an ASCII code is and how ASCII codes or similar are transferred via a serial connection. It briefly introduces the idea of variable-length codes and then specifically looks at the construction of T-codes. It explains why they are statistically self-synchronising and how the synchronisation status may be derived by a decoder. The lecture then looks at T-code synchronisation from a different angle. The relationship between cyclic equivalence classes and code synchronisation has been known for many decades. The cyclic equivalence classes of strings of length L are the sets of strings of length L that can be transformed into each other by cyclic shift. E.g., the strings 00011, 00110, and 10001 all belong to the same cyclic equivalence class of the length 5, whereas the string 10100 belongs to a different class. During my last sabbatical in 2006, Aaron Gulliver and I discovered that subsets of T-code codewords of the same length L contain at most one codeword from each cyclic equivalence class. Moreover, we were able to show that, for any given L, it is possible to generate T-codes that contain elements from each of the non-periodic cyclic equivalence classes of length L. The lecture shows how to generate such sets. We are also able to describe under which circumstances elements from periodic cyclic equivalence classes are created in addition to those from non-periodic classes. We can now show that the presence of periodic codewords in T-codes makes them statistically self-synchronisable rather - if we leave these codewords out, the resulting code has a bounded synchronisation delay.

第16回,2009年9月2日(火),東京大学 柏キャンパス 基盤棟2階 基盤棟共通セミナー室(2C5/2C7室)

  • 14:00〜16:00(ごろ)
  • 講演者:八木 秀樹 (電気通信大学)
  • 講演タイトル:共通メッセージを有する複合多重アクセス通信路における符号アン サンブルの構成(A restricted code ensemble for compound multiple access channel with common information)
  • 概要: 本発表では,通信ネットワーク上に送信機・受信機が複数存在するCompound多重アクセス通信路において,2つの協調通信モデルに対する符号化法を提案する.提案する符号はシングルユーザ通信における線形ブロック符号を組み合わせて構成される.最尤復号を仮定して,提案する符号アンサンブルの復号性能を解析する.また,構成に用いる線形ブロック符号組に対し,通信路容量域を平均的に達成するための条件を導出する.さらに低密度パリティ検査(LDPC)符号が導出した条件を満足することを示す.提案符号により,従来の通信路容量を達成する符号に比べて時間計算量やメモリ量の大幅な削減が期待できる。

第15回,2009年1月31日(土),東京大学 柏キャンパス 基盤棟2階 基盤棟共通セミナー室(2C5/2C7室)

  • 参加者が予想より多くなったため,会場を「基盤棟5階 山本-國廣研セミナー室(5F4室)」から上記に変更しました。
  • 10:00〜12:00, 13:00〜15:00(ごろ)
  • 講演者:村松 純 (NTT コミュニケーション科学基礎研究所 メディア情報研究部 信号処理研究グループ)
  • 講演タイトル:アンサンブルのハッシュ性による符号化定理
  • 概要: 加法的雑音を伴う通信路の容量を達成する符号として疎行列を用いた LDPC (Low Density Parity Check) 符号がある.これと確率伝搬法や線形計画法等の近似アルゴリズムを用いることにより現実的な計算時間で最尤復号を実現出来ることから,近年盛んに研究されている.このアイデアは加法的雑音を伴う通信路符号の構成に留まらず,さまざまな符号の構成にも応用出来ることが明らかになってきた.本講演では, これらの符号の漸近最良性はアンサンブル(関数族上の確率分布)の持つハッシュ性と呼ばれる性質から導かれることを示す.まず最初にハッシュ性の定義とその基本的な性質を紹介し, 続いてハッシュ性を持つアンサンブルを用いて,一般の定常無記憶通信路の容量を達成する符号,一般の定常無記憶情報源のレート・歪み限界を達成する符号 の存在定理の証明を与える.

第14回,2008年11月11日(火),東京大学 柏キャンパス 基盤棟2階 基盤棟共通セミナー室(2C5/2C7室)

  • 15:00〜16:30
  • 講演者:Marat Burnashev (東京大学客員教授,Russian Academy of Scienece)
  • 講演タイトル:On Zero-Rate Error Exponent for BSC with Nosiy Feedback
  • 概要: For the information transmission a binary symmetric channel is used. There is also another noisy binary symmetric channel (feedback channel), and the transmitter observes without delay all the outputs of the forward channel via that feedback channel. The transmission of a nonexponential number of messages (i.e. the transmission rate equals zero) is considered. The achievable decoding error exponent for such a combination of channels is investigated. It is shown that if the crossover probability of the feedback channel is less than a certain positive value, then the achievable error exponent is better than the similar error exponent of the no-feedback channel.

柏キャンパスにおける「情報理論研究会(電子情報通信学会 )」の開催案内

  • 日時:2008年7月24日(木)25日(金)
  • 場所:柏図書館メディアホール
  • プログラム
    (招待講演:電波伝搬を活用した無線通信セキュリティ,笹岡秀一(同志社大),24日(木)16:20〜17:20)

第13回,2008年6月25日(水),東京大学 柏キャンパス 基盤棟5階 山本-國廣研セミナー室(5F4室)

  • 15:00〜17:00
  • 講演者:Vo Ngoc Anh (The University of Melbourne)
  • 講演タイトル:Inverted Index Compression using Word-Synchronised Binary Codes
  • 概要: In this talk, we present some simple mechanisms for compressing document-based inverted lists using word-aligned and word-synchronised binary codes. The new mechanisms provides compression rates that are inferior to the best that have been previously achieved, but has the advantage of requiring exceptionally low computational effort at decoding time, and also support efficient implementation of skipping - fast jumping over a number of compressed items without actual decompression. That is, by allowing some inefficiency in the compressed representation, the new codes provides fast access into the compressed inverted lists, and overall provides faster query processing than previous techniques. Results are given for several large text collections in support of these claims, both for compression effectiveness and query efficiency. The techniques can also be applied to compression of other clustered sparse bitmaps.

第12回,2008年3月29日(土),東京大学 柏キャンパス 基盤棟2階 複雑理工学専攻講義室(2D5室)

  • 9:30〜11:30
  • 講演者:Anant Sahai (University of California, Berkeley)
  • 講演1タイトル:How valuable is noisy or unreliable feedback?
  • 講演2タイトル:Fundamental bounds for power consumption at the physical layer: "waterslide curves" and the price of certainty
  • 講演1の概要: In the context of memoryless channels, the traditional approach of information theory is to studying feedback by considering ideal noisefree instantaneous feedback of the channel outputs to the encoder. This was acceptable in classical work because the results were essentially negative: Shannon pointed out that feedback does not improve capacity and in the context of symmetric DMCs, Dobrushin (following earlier work by Berlekamp) showed that it does not improve the fixed block-coding error exponents either, at least in the interesting high rate regime.
    However, posing the communication problem in different ways does allow noiseless feedback to dramatically improve reliability, even for DMCs. If improvements are claimed with ideal instantaneous feedback, then it is natural to wonder whether the improvements remain with noisy or otherwise limited feedback. We will cover three problem variations, each having its own error exponent.
    First, we will cover the case of variable-length block-coding and show how to limit the loss from the Burnashev exponent despite having only a noisy feedback path. The schemes to do this are more closely related to those of Yamamoto and Itoh. We take a Forney perspective on this problem and consider it as a problem with a soft deadline. (errors and erasures view)
    Second, we relax the block-coding constraint and take a per-bit formulation of soft deadlines. The relevant noiseless feedback exponent was given by Kudryashov and not only is it substantially higher than the Burnashev exponent, but we show it can be *achieved* using only a noisy DMC on the feedback path, as long as this feedback channel has a sufficiently high capacity and we are allowed to code appropriately over it.
    Finally, we maintain the per-bit perspective, but require a hard deadline. In this case we consider erasure channels on both the forward and feedback links and show that if the feedback erasure probability is low enough, there is no loss in attainable error exponents. Furthermore, we also show that noisy feedback increases reliability even if there is a half-duplex constraint.
    [Parts of this talk are joint work with my former student Tunc Simsek and former postdoc Stark Draper.]
  • 講演2の概要:The classical problem of reliable point-to-point digital communication can be considered as wanting to achieve a very low probability of error while keeping the rate high and the total power consumption small. Traditional information-theoretic analysis uses explicit models for the communication channel to study the power spent in transmission. The resulting bounds are expressed using `waterfall' curves that convey the revolutionary idea that unboundedly low probabilities of bit-error are attainable using only finite transmit power.
    However, practitioners have long observed that the decoder complexity, and hence the total power consumption, goes up when attempting to use sophisticated codes that operate close to the Shannon waterfall curve. This is especially true when short-range communication is considered. This talk asks the question of what "capacity-achieving" should mean if we have to care about total power rather than just transmitter power.
    Classical results on decoding complexity are reinterpreted in this context and are shown to imply that neither classical dense linear codes with ML decoding nor convolutional codes can be capacity achieving in any reasonable sense. An explicit model for power consumption at an idealized decoder is then given that allows for extreme parallelism in implementation. This decoder architecture is in the spirit of message passing and iterative decoding for sparse-graph codes.
    Generalized sphere-packing arguments are used to derive lower bounds on the decoding power needed for any possible code given only the gap from the Shannon limit and the desired average probability of bit error. As the gap goes to zero, the energy per bit spent in decoding is shown to go to infinity. This suggests that to optimize total power, the transmitter should operate at a power that is strictly above the minimum demanded by the Shannon capacity. The lower bound is also plotted to show an unavoidable tradeoff between the average bit-error probability and the total power used in transmission and decoding. In the spirit of conventional waterfall curves, we call these `waterslide' curves.
    (This is joint work with my student Pulkit Grover)

第11回,2007年11月14日(水),東京大学 柏キャンパス 基盤棟2階 基盤棟共通セミナー室(2C5/2C7室)

  • 15:00〜16:30
  • 講演者:Marat Burnashev (東京大学客員教授,Russian Academy of Scienece)
  • 講演タイトル:Code spectrum and the reliablity function: Gaussian channel
  • 概要:A new approach for upper bounding the channel reliability function using the code spectrum is described. It allows to treat both low and high rate cases in a unified way. In particular, the earlier known upper bounds are improved, and a new derivation of the sphere-packing bound is presented.
    (上記と同じタイトルで,「Problems of Information Transmission, vol.43, no.2, pp.69-88, 2007」に掲載された論文に関する講演)

第10回,2007年7月13日(金),東京大学 柏キャンパス 基盤棟2階 基盤棟共通セミナー室(2C5/2C7室)

  • 16:00〜17:30
  • 講演者:Anderson C. A. Nascimento (University of Brasilia)
  • 講演タイトル:Cryptographic Capacities of Noisy Channels
  • 概要:Noisy channels turned out to be valuable resources in cryptography. Recent research results proved that mutually distrustful players can exploit a source of trusted noise in order to accomplish cryptographic tasks. We will review recent results in the area and point out interesting directions for future research. We will focus mostly on intersections between noise based cryptography and Shannon Theory.

第9回,2007年6月19日(火),東京大学 柏キャンパス 基盤棟2階 基盤棟共通セミナー室(2C5/2C7室)

  • 14:50〜16:20
  • 講演者:Ulrich Speidel (University of Auckland, Dept. of Computer Science)
  • 講演タイトル:The wonderful world of T-codes and T-complexity
  • 概要:T-codes were invented in the 1980's by Mark Titchener. They were initially noticed as variable length codes with strong statistical self-synchronization tendency and considered for source coding. However, the lack of a simple Huffman-style construction algorithm made this seem prohibitive. It was not until the 1990s when Nicolescu and Titchener demostrated that each finite string could be converted into a unique T-code set where the string defined the longest codewords. This has since given rise not only to a new computable complexity measure for strings, but in turn also to information and entropy measures. When used on sources with known entropies, these compare favourably with traditional entropy estimators such as Shannon n-gram entropy, Lempel-Ziv production complexity or compressors of the Lempel-Ziv family. I will give an application example in the area of TCP/IP network event detection. Time permitting I will also comment on more recent results, which show that T-codes provide a generating algorithm for all non-periodic cyclic equivalence classes of strings of any given length, and that they can be used for the construction of variable-length bounded synchronization delay codes that are larger than those proposed by Scholtz.

柏キャンパスにおける「ISETC(情報セキュリティ) - OIS(オフィスインフォメーションシステム)合同研究会(電子情報通信学会 )」の開催案内

  • 日時:2006年11月16日(木)13:00〜17:25,17日(金)9:45〜12:30
  • 場所:柏図書館メディアホール
  • プログラム
    (招待講演:バイオメトリクス・セキュリティの動向と課題,小松尚久(早稲田大学),16日(木)14:55〜15:55)

第8回,2006年8月29日(火),東京大学 柏キャンパス 基盤棟2階 複雑理工学専攻講義室(2D5室)

  • 10:00〜12:00
  • 講演者:中村昌裕 (大阪大学 大学院理学研究科 博士後期課程2年)
  • 講演タイトル:Martin-Lof ランダムネスによる確率法則の拡張
  • 概要:Martin-Lof ランダムネスとは,確率過程から得られたデータ系列がランダムであるか否かを,アルゴリズムの観点から特徴づけたものである.Martin-Lof ランダムな系列の全体の集合は確率測度1を持つが,それでは,確率1で成立する種々の確率法則を,「すべての Martin-Lof ランダムな系列に対して成立する」という形の表現に拡張することは可能であろうか.実際,独立同分布過程における「大数の強法則」や「重複対数の法則」などではこの拡張は比較的容易であるが,一般の確率過程においては困難な問題である.本発表では,V'yugin による Shannon-McMillan-Breiman 定理の拡張を,有限次マルコフ近似を用いることによって別証明を与える.また,ユニバーサルデータ圧縮法の原理をなす Wyner-Ziv-Ornstein-Weiss の再帰時間定理についても,順定理部分においてランダム系列版への拡張を行う.
  • 13:00〜15:00
    講演者:Kirill Morozov (Research Center for Information Security (RCIS), National Institute of Advanced Industrial Science and Technology (AIST))
  • 講演タイトル:Unconditionally Secure Cryptographic Primitives Based on Noisy Channels
  • 概要:Oblivious Transfer (OT) and Bit Commitment (BC) appear to be fundamental in the cryptographic protocol design. These are important tools for providing privacy in secure computation between two parties who do not trust each other. OT is about transmitting data such that the sender is guaranteed that the data will be partially erased during the transmission, but he does not know what exactly the receiver gets. BC scheme is a tool for transmitting an evidence about a piece of information such that the receiver cannot learn it without the sender's help, while the sender cannot open something different from what he had committed to.
  • Secure two-party computation can be build based on OT, while BC implies zero-knowledge proofs. We shall consider implementations of OT and BC with unconditional (aka information-theoretic) security for both parties. Unconditional security provides protection against computationally unbounded adversaries, hence it does not depend on unproven intractability assumptions like integer factoring or discrete logarithm.
  • It is well known that unconditional security cannot be provided for both parties "from scratch", i.e. based on noiseless communication and local randomness. Some restriction on the parties' communication/abilities must be imposed. We assume that they are connected by a noisy channel. This is a very natural assumption since noise is inherently present in any real communication. Hence, the noise turns out to be an ally of cryptographers while being an enemy of telecommunication engineers.
  • Our talk is organised as follows:
    -) Introduction of oblivious transfer and bit commitment and their security definitions
    -) Motivation on why these protocols are important
    -) History of development for this research area (constructions for BC and OT based on various noisy channel models; variants of BC and OT; reductions between these variants and noisy primitives)
    -) Mathematical background and useful tools: privacy amplification, universal hashing, error correcting codes
    -) Some constructions for BC and OT
    -) Current research in this area
    -) Open questions

柏キャンパスにおける「情報理論研究会(電子情報通信学会 )」の開催案内

  • 日時:2006年7月27日(木)28日(金)
  • 場所:柏図書館メディアホール
  • プログラム
    (招待講演:データの符号化とモデル選択,伊藤秀一(電通大),27日(木)16:30〜17:30)

第7回,2006年6月24日(土),東京大学 柏キャンパス 基盤棟2階 複雑理工学専攻講義室(2D5室)

  • 10:00〜12:00
  • 講演者:木村昭悟(NTTコミュニケーション科学基礎研究所/東京工業大学 大学院理工学研究科 博士課程2年)
  • 講演タイトル:Multiterminal source coding with complementary delivering
  • 概要:A coding problem where messages from two correlated sources are jointly encoded and separately decoded is investigated. Each decoder has access to one of two messages to reproduce the other message. The rate-distortion function for the coding problem is clarified. Some related coding problems are also examined.
  • 13:00〜15:00
  • 講演者:高橋勇人(JST ERATO 合原複雑数理モデルプロジェクト)
  • 講演タイトル:積空間上のランダムな点の集合とベイズ統計
  • 概要:まず前半では積空間上でマルチンレフの意味でのランダムな点の集合を考える.
    1.次にランダムな点に関するマルチンゲールの収束性を示す.その後尤度比検定が2つの計算可能な確率分布に関するランダムな点の集合を分類することを示す.またそれを用いて2つの計算可能な確率分布が互いに特異であることとそれらのランダムな点の集合が交わりを持たないことが同値である事を示す.また絶対連続性とランダムな点の集合との関係を示す.2. 積空間上のランダムな点の集合のセクションを考えそれと条件付き確率,Fubiniの定理との関係を示す.3. 積空間上のランダムな点に対して条件付きコルモゴロフ複雑度の加法性を示す.
    後半では前半の結果とパラメトリックモデルのベイズ統計との関わりについて話す.
    1. ここではベイズ統計を積空間上の確率モデルと捉える.それによりまず最初にユニバーサルベイズテストを導入する.これは積空間上のユニバーサルマルチンレフテストから自然に定義される. またユニバーサルベイズテストをもちいてランダムなサンプルとパラメータのペア及びパラメトリックモデルに対する乱数列を自然な形で定義する.2. ランダムなサンプルとパラメータのペアに対してBIC/MDL/MMLの一致性を示す.3. ランダムなサンプルとパラメータのペアに対してベイズ推定量の一致性及び同値な条件を示す.4. アルゴリズム的な意味で最適な推定量を示す。

第6回,2006年3月4日(土),東京大学 柏キャンパス 基盤棟2階 複雑理工学専攻講義室(2D5室)

  • 10:00〜12:00, 13:00〜15:00
  • 講演者:田中利幸(京都大学 大学院情報学研究科)
  • 講演タイトル:情報統計力学の方法
  • 概要:情報統計力学とは,統計力学の方法論を情報理論分野の様々な問題に適用することを試みたり,逆に情報理論の知見にもとづいて統計力学の対象となる系の巨視的な性質について理解を深めたり,といった研究課題を探求する学問分野のことを指す.本講演では,近年の情報統計力学の主要な研究成果を生み出すもととなった「レプリカ法」と「確率伝搬法=ベーテ近似」とについて,それぞれの手法の数理的な側面に力点を置いて概説する.

第5回,2005年12月10日(土),東京大学 柏キャンパス 基盤棟2階 複雑理工学専攻講義室(2D5室)

  • 10:00〜12:00
  • 講演者:坂本比呂志(九州工業大学 情報工学部)
  • 講演タイトル:文脈自由文法を用いた効率的な圧縮アルゴリズム
  • 概要:テキストを圧縮する問題を,そのテキストを生成する最小の文脈自由文法を計算する最適化問題とみなす.この問題はNP-困難で,最適解をある定数倍以内で近似することも不可能であることが知られている.本研究では,最適解に十分に近い,およそlog n倍以内の近似(nはテキストサイズ)を保証する2種類の線形時間アルゴリズムを提案する.
  • 13:00〜15:00
  • 講演者:松井知己(東京大学 大学院情報理工学系研究科)
  • 講演タイトル:CFTP を用いた Perfect Sampling
  • 概要:本発表では,マルコフ連鎖を用いたsampling 法の一つであるCFTP(coupling from the past)法について,解説を行う。 マルコフ連鎖を用いた従来のサンプリング法では、初期状態から十分な回数推移させることによりサンプリングを行っているが、その回数の算定は経験に基づくものであることが多い。本発表で解説するCFTP法は、目的とする分布を極限分布に持つマルコフ連鎖から、極限分布に「厳密に」従うサンプルを得る手法である。CFTP法は、無限の過去から推移しているマルコフ連鎖を仮想的に考え、現時点でサンプリングを行うという革新的なアイデアに基づく。現時点の状態を知るために、過去に遡り全状態からの coupling が起こっているか(coalescence が起こっているか)を確認することから、CFTPという名前がついている。
  • 参考文献:来嶋秀治, 松井知己, 「完璧にサンプリングしよう!」 オペレーションズ・リサーチ,vol. 50 (2005), 第一話: 169-174; 第二話: 264-269; 第三話: 329-334.

第4回,2005年11月8日(火),東京大学 柏キャンパス 基盤棟2階 複雑理工学専攻講義室(2D5室)

  • 15:00〜16:30
  • 講演者:Marat Burnashev (Institute for Information Transmission Problems, Russian Academy of Sciences)
  • 講演タイトル:On Gaussian Approximation, Asymptotically Optimal Linear and Nonlinear Detectors in CDMA and Multiuser Detection
  • 概要:The talk is based on 3 our papers published in 2003-2004. The following topics are supposed to be covered.
    • 1) On Gaussian and Better Approximation on bit-error probability.
      It is known that Gaussian approximation is not accurate for high SNR. A new very tight upper bound is presented. Issues of asymptotic behavior and optimality are also explored.
    • 2) Geometrical Description of Optimal Linear Detector and Asymptotic Efficiency.
      It is shown that finding the asymptotically best linear detector and the largest asymptotic efficiency is equivalent to a standard problem of convex analysis in Euclidean space --- finding the distance from a point to a convex set. As an application, the necessary and sufficient conditions for the decorrelating and conventional detectors to be asymptotically optimal are derived. As another application, it is shown that in the case of randomly chosen CDMA signals with high probability the decorrelating detector is asymptotically optimal. It allows to find the largest asymptotic efficiency of linear detectors.
    • 3) When Asymptotically Optimal Detectors Are Linear ?
      The necessary and sufficient condition is found.
  • Based on:
    1. M.V.Burnashev, "On optimal linear detectors, asymptotic efficiency and some CDMA problems", Probl. of Inform. Trans., 39, no. 2, pp. 36-52, 2003.
    2. M.V.Burnashev and H.V.Poor, "On the probability of error in linear multiuser detection", IEEE Trans. on Inform. Theory, 49, no. 8, pp. 1922-1941, 2003.
    3. M.V.Burnashev, "On optimal detectors in multiuser detection problems", Probl. of Inform. Trans., 40, no. 1, pp. 48-57, 2004.

第3回,2005年10月1日(土),東京大学 柏キャンパス 基盤棟2階 複雑理工学専攻講義室(2D5室)

  • 10:00〜12:00
  • 講演者:四方 順司(横浜国立大学 大学院環境情報研究院)
  • 講演タイトル:Unconditionally Secure Steganography
  • 概要:Recently, steganography has been studied intensively from a theoretical viewpoint. In this talk, under the general insecure channel on which the adversary may read and write messages, we formally define an information-theoretic model of stegosystems against active attacks. Also, we consider several security notions of stegosystems in unconditional security setting. Furthermore, we provide a generic construction method of unconditionally secure stegosystems against active attacks.
  • 13:00〜15:00
  • 講演者:尾形わかは(東京工業大学 大学院イノベーションマネジメント研究科)
  • 講演タイトル:Webページのアクセス数計数に対する暗号学的アプローチ
  • 概要:インターネット広告の広告料決定の方法には,バナー広告をクリックした数によるクリック保証型,広告が含まれるページを閲覧したユーザ数(アクセス数)によるインプレッション型,そしてアフェリエイト型の3つがある.本講演では,インプレッション型におけるアクセス数計測を,秘密分散共有法,メッセージ認証コード,一方向性関数といった暗号理論を利用して,フェアに行う方法について説明する.

第2回,2005年8月19日(金),東京大学 柏キャンパス 基盤棟2階 複雑理工学専攻講義室(2D5室)

  • 10:00〜12:00
  • 講演者:川端 勉 (電気通信大学 情報通信工学科)
  • 講演タイトル:Redundancy of Symbol Decomposition Algorithms for Memoryless Source
  • 概要:The symbol decomposition algorithm is proposed by Willems et.al. as an efficient and practical symbol predictor applicable for compressing multi-alphabet data like text. However, no theoretical analysis of the algorithm has been presented. In this paper, we first elucidate a parameterization and a prior distribution that the algorithm assumes. We then analyze the redundancy for memoryless source with a structured probability and point out its non-optimality in the first order asymptotics. Next we give an interpretation of the algorithm in comparison with the multi-alphabet Krichevsky-Trofimov estimator. Finally, we propose a modification enhanced with a zero-redundancy estimator and show that it asymptotically achieves the optimal first order redundancy. We demonstrate by a computer simulation an effectiveness of the symbol decomposition algorithm and in particular
  • 13:00〜15:00
  • 講演者:横尾英俊 (群馬大学工学部 情報工学科)
  • 講演タイトル:無ひずみデータ埋め込みのためのユニバーサル法
  • 概要:電子透かし等の埋め込み技術では,認識されない程度に原データ (本講演では「ホストデータ」とよぶ) を書き換えることによって埋め込みを実現する.このとき,埋め込み後のデータから,埋め込みデータだけでなくホストデータも誤りなく再現できることを要求するのが無ひずみデータ埋め込みである.本講演では,無ひずみデータ埋め込みの情報理論的モデルを与え,そのモデルのもとで埋め込み可能な最大レートを漸近的に達成するユニバーサルな埋め込み法を提案する.

第1回,2005年7月16日(土),東京大学 柏キャンパス 基盤棟2階 複雑理工学専攻講義室(2D5室)

  • 10:00〜12:00
    講演者:葛岡成晃 (東京工業大学 大学院理工学研究科 博士課程2年)
  • 講演タイトル:Relationship among Complexities of Individual Sequences over Countable Alphabet
  • 概要:In this study, we investigate some relations among four complexities of sequence over countably infinite alphabet, and show that two kinds of empirical entropies and the self-entropy regarding a finite state source are asymptotically equal and lower bounded by the muximun number of phrases in distinct parsing of the sequence. Some connections with source coding theorems are also investigated. Further, we consider the empirical entropies with fidelity criterion.
  • 13:00〜15:00
    講演者:藤岡 淳(NTT 情報流通プラットフォーム研究所)
  • 講演タイトル:暗号技術における擬似乱数生成
  • 概要: 暗号技術における擬似乱数の使われ方(ストリーム暗号など)とそこで求められる性質(予測不可能性と識別不可能性)について述べる.