{"id":441,"date":"2026-08-18T13:03:01","date_gmt":"2026-08-18T04:03:01","guid":{"rendered":"https:\/\/isita.ieice.org\/2026\/?page_id=441"},"modified":"2026-08-18T13:05:51","modified_gmt":"2026-08-18T04:05:51","slug":"organized-session","status":"publish","type":"page","link":"https:\/\/isita.ieice.org\/2026\/organized-session\/","title":{"rendered":"Organized Session"},"content":{"rendered":"\r\n

Intersections of Information Theory, Cryptography, and Complexity Theory<\/strong><\/span><\/p>\r\n

Organizer: Shun Watanabe, Tokyo University of Agriculture and Technology<\/p>\r\n

Title: Applications of Majorization to Cryptography and Theoretical Computer Science<\/span><\/h2>\r\n

Mitsugu Iwamoto, University of Electro-Communications<\/p>\r\n

\r\n

Majorization is useful not only in information theory but also in cryptography and theoretical computer science. In this talk, we illustrate its usefulness through two examples. First, in information-theoretically secure symmetric-key encryption, we show that perfect secrecy forces the ciphertext distribution to be uniform under a natural size condition. Second, we consider k-sources, namely, sources with min-entropy at least k. When k is an integer, every k-source can be expressed as a convex combination of flat sources, each supported on \\(2^k\\) points. Both results admit natural proofs based on majorization.<\/p>\r\n<\/div>\r\n

Title: How much does a black box reveal?<\/span><\/h2>\r\n

Akinori Kawachi, Mie University<\/p>\r\n

\r\n

Query complexity asks how many interactions with a black-box oracle are required to determine a property of the hidden input. In this talk, we overview quantum query lower bounds as quantitative limitations on how much task-relevant information can be extracted from an oracle by each query. We introduce three techniques through this common perspective. The adversary method tracks how rapidly oracle queries can distinguish quantum states corresponding to different inputs. The polynomial method shows that the outcome probabilities of a bounded-query algorithm are constrained to be low-degree polynomials of the oracle variables. Finally, an information-theoretic method measures the information about the hidden input contained in the inner state of the algorithm by using von Neumann entropy and state distinguishability. Although these methods employ different mathematical quantities, they share a common proof strategy: bound the information gained per query and compare it with the amount required to solve the problem. We illustrate this viewpoint using quantum search problems. Additionally, we review recent topics related with quantum query complexity.<\/p>\r\n<\/div>\r\n

Title: Multiplicative Weights Update Algorithm and Its Applications to Cryptography and Information Theory<\/span><\/h2>\r\n

Shun Watanabe, Tokyo University of Agriculture and Technology<\/p>\r\n

\r\n

The multiplicative weights update (MWU) algorithm is a versatile iterative algorithm for computing approximate equilibria in two-player games. It also provides a general framework encompassing several boosting algorithms in learning theory. From the viewpoint of optimization, MWU is known as a special case of the mirror descent (MD) algorithm. MWU has long been widely used in theoretical computer science and cryptography, particularly in areas such as hardness amplification. On the other hand, the Arimoto\u2013Blahut algorithm, which is well known in information theory as an algorithm for computing channel capacity, can also be interpreted as a special instance of MD algorithm. Related optimization methods have recently been studied actively in the context of computing capacities of quantum channels. In this talk, we provide an introduction to the MWU algorithm and its matrix-valued extension, the matrix MWU algorithm, and discuss their applications to cryptography and information theory. In particular, we explain how these algorithms can be used to deterministically construct codes for the channel resolvability problem in information theory.<\/p>\r\n<\/div>\r\n

Title: Information-Theoretic Perspectives on Computational Hardness<\/span><\/h2>\r\n

Kenji Yasunaga, Science Tokyo<\/p>\r\n

\r\n

Computational hardness is one of the fundamental notions in modern cryptography, while entropy and divergence are central concepts in information theory. Several results have revealed close connections between these viewpoints, showing that computational hardness can be studied through information-theoretic quantities such as entropy and Kullback\u2013Leibler divergence. This talk discusses some of these connections, focusing on the relationship between computational hardness and pseudoentropy. In particular, it explains how KL hardness can lead to pseudo-Shannon entropy. Some further applications of these ideas will also be discussed.<\/p>\r\n<\/div>\r\n","protected":false},"excerpt":{"rendered":"

Intersections of Information Theory, Cry\u2026<\/p>\n","protected":false},"author":2,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-441","page","type-page","status-publish","hentry"],"aioseo_notices":[],"_links":{"self":[{"href":"https:\/\/isita.ieice.org\/2026\/wp-json\/wp\/v2\/pages\/441","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/isita.ieice.org\/2026\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/isita.ieice.org\/2026\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/isita.ieice.org\/2026\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/isita.ieice.org\/2026\/wp-json\/wp\/v2\/comments?post=441"}],"version-history":[{"count":8,"href":"https:\/\/isita.ieice.org\/2026\/wp-json\/wp\/v2\/pages\/441\/revisions"}],"predecessor-version":[{"id":450,"href":"https:\/\/isita.ieice.org\/2026\/wp-json\/wp\/v2\/pages\/441\/revisions\/450"}],"wp:attachment":[{"href":"https:\/\/isita.ieice.org\/2026\/wp-json\/wp\/v2\/media?parent=441"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}