Information Theory and its Applications  Page description

Help  Print 
Back »

 

Details of project

 
Identifier
105840
Type K
Principal investigator Csiszár, Imre
Title in Hungarian Információelmélet és alkalmazásai
Title in English Information Theory and its Applications
Keywords in Hungarian információelmélet, titkos kulcs, matematikai statisztika, mértékkoncentráció, kombinatorika
Keywords in English Information theory; secret key; mathematical statistics; measure concentration; combinatorics
Discipline
Mathematics (Council of Physical Sciences)100 %
Ortelius classification: Probability theory
Panel Mathematics and Computing Science
Department or equivalent Alfréd Rényi Institute of Mathematics, HAS
Participants Farkas, Lóránt
Kói, Tamás
Marton, Katalin
Rásonyi, Miklós
Simonyi, Gábor
Starting date 2013-01-01
Closing date 2016-12-31
Funding (in million HUF) 11.476
FTE (full time equivalent) 8.52
state closed project
Summary in Hungarian
A kutatás összefoglalója, célkitűzései szakemberek számára
Itt írja le a kutatás fő célkitűzéseit a témában jártas szakember számára.

A pályázat az MTA Rényi Alfréd Matematikai Kutatóintézetében több évtizede folyamatos, nemzetközi elismertségű információelméleti alapkutatás folytatását célozza, mind a szűkebb értelemben vett információelmélet, mind az információelméleti módszereknek a matematika más ágaiban való alkalmazása területén.
Az információelméleti titkosságra vonatkozó eddigi munkánkat folytatva tervezzük speciálisan a több bemenetű csatornák titkos kulcs generálási kapacitásának vizsgálatát. Fiatal kutatók bevonásával tervezzük a több bemenetű aszinkron csatornák vizsgálatát, ilyenekkel modellezhető pl. a mobiltelefon. Folytatni tervezzük az információ-mértékszámokra vonatkozó kutatásainkat, egyik célunk az I-divergencia tulajdonságainak eddigi eredményeinknél teljesebb kiterjesztése általános entrópia-funkcionálokra, melyek közül pl. a Bregman távolságok alkalmazási jelentősége számottevő.
Korábbi kutatásainkban jelentős eredményeket értünk el információelméleti módszerek és információelméleti motiváltságú modellek használatával a mértékkoncentráció-elmélet és a kombinatorika területén. A pályázat keretében folytatni tervezzük ilyen irányú kutatásainkat is, így az irányított gráfok Sperner kapacitására és lokális kromatikus számára, valamint más kombinatorikai kapacitás fogalmakra vonatkozó nyitott kérdések vizsgálatát.

Mi a kutatás alapkérdése?
Ebben a részben írja le röviden, hogy mi a kutatás segítségével megválaszolni kívánt probléma, mi a kutatás kiinduló hipotézise, milyen kérdéseket válaszolnak meg a kísérletek.

A tervezett kutatás több irányú, a szűkebb értelemben vett információelméleten kívül a matematika más területeire is kiterjed. A közös alapkérdés abban áll, hogy információelméleti módszerekkel ill. információelméleti motiváltságú modellek vizsgálatával kívánunk új matematikai tételeket bizonyítani.
A kutatási terv szerint elsősorban a következő területeken várhatók eredmények: több bemenetű aszinkron csatornák, információelméleti titkosság, entrópia-funkcionálok tulajdonságai, mértékkoncentráció és logaritmikus Szoboljev egyenlőtlenségek, kombinatorika.

Mi a kutatás jelentősége?
Röviden írja le, milyen új perspektívát nyitnak az alapkutatásban az elért eredmények, milyen társadalmi hasznosíthatóságnak teremtik meg a tudományos alapját. Mutassa be, hogy a megpályázott kutatási területen lévő hazai és a nemzetközi versenytársaihoz képest melyek az egyediségei és erősségei a pályázatának!

A szűkebb értelemben vett információelméletben végzendő kutatásainkat jelenleg intenzíven kutatott illetőleg fokozódó jelentőségű területeken tervezzük, mint az információelméleti titkosság ill. a több bemenetű aszinkron csatornák. Ezek az alapkutatási témakörök fontos gyakorlati feladatok matematikai modellezése során alakultak ki. Ezért az új matematikai tételekben megnyilvánuló kutatási eredmények áttételesen hasznosnak bizonyulhatnak a szóban forgó gyakorlati feladatok, nevezetesen a hírközlés titkosságának biztosítása ill. a mobiltelefonok hatékonyabb kihasználása szempontjából is.
Az entrópia-funkcionálokra vonatkozólag tervezett kutatás eredményei szintén hasznosulhatnak a gyakorlatban is, mivel e funkcionálok közül többnek (pl. a Bregman távolságoknak) jelentős statisztikai alkalmazásai vannak, pl. tanuló-algoritmusokban.
A matematika más területén tervezett kutatás, információelméleti módszerek alkalmazásával vagy információelméleti motiváltságú kérdésekre vonatkozólag, már önmagában jelentős, amennyiben a matematika különböző területei közötti kapcsolatot demonstrálja. Ezen túlmenőleg, a mértékkoncentráció elméletben ma az általunk kezdeményezett információelméleti módszer az egyik leghatékonyabb, és a kombinatorikában az információelmélet által motivált kérdések körül mára önálló kutatási terület alakult ki.

A kutatás összefoglalója, célkitűzései laikusok számára
Ebben a fejezetben írja le a kutatás fő célkitűzéseit alapműveltséggel rendelkező laikusok számára. Ez az összefoglaló a döntéshozók, a média illetve az adófizetők tájékoztatása szempontjából különösen fontos az NKFI számára.

A pályázat célkitűzése matematikai alapkutatás két fő irányban, a szűkebb értelemben vett információelmélet területén és a matematika más, az információelmélettel kölcsönhatásban lévő ágaiban.
Az első irány, elméleti jelentőségén túlmenően, gyakorlati alkalmazásokhoz is vezethet. Az információelméleti alapkutatás eredményei többször viszonylag hamar hasznosultak látványos alkalmazásokban, pl. hibajavító és adattömörítő algoritmusok, űrtávközlés, internet. A pályázat keretében foglalkozni tervezünk olyan kérdésekkel, melyek a hírközlési titkosság valamint a mobiltelefon problematikájának matematikai modellezése során merültek fel. Az elérendő eredmények, melyek matematikai tételek lesznek, elősegíthetik ezen gyakorlati problémák jobb megértését, és később közvetlenebb gyakorlati alkalmazásokhoz is vezethetnek, ha nem is olyan látványosakhoz, mint az említettek.
A kutatás másik fő iránya olyan, a matematika más ágaihoz tartozó problémákat vesz célba, melyek információelméleti módszerekkel vizsgálhatók vagy információelméleti kérdésfeltevés során merültek fel. E kutatási irány jelentősége abban áll, hogy demonstrálja a matematika különböző ágainak kölcsönhatását és ezen kölcsönhatások kihasználásának előnyeit.
Summary
Summary of the research and its aims for experts
Describe the major aims of the research for experts.

The main purpose of this project is to continue the internationally recognized work on fundamental research in information theory, going on in the Rényi Institute of Mathematics since several decades, both in strict sense information theory and concerning applications of information theoretic methods in other branches of mathematics.
Continuing our work on information theoretic secrecy, in particular investigation of the secret key generating capacity of multiterminal channels is planned. With involvement of young researchers, we plan to investigate asynchronous multiple access channels, which are suitable to model, e.g., mobile phones. Continuation of our previous work concerning information measures is also planned, one goal is a more complete extension of the properties of I-divergence to general entropy functionals than we were able to do previously; these functionals include, e.g., Bregman distances which are often used in applications.
Our previous research has lead to significant results via applying information theoretic methods and models in the theory of measure concentration and in combinatorics. Within this project, further research in these directions is also planned, such as investigation of open problems about Sperner capacity and local chromatic number of directed graphs, and about other combinatorial capacity concepts.

What is the major research question?
Describe here briefly the problem to be solved by the research, the starting hypothesis, and the questions addressed by the experiments.

Research in several directions is planned including in addition to strict sense information theory also other branches of mathematics. The common basic problem is that we intend to employ information theoretic techniques or information theoretically motivated models for proving new mathematical theorems. According to the research plan, results are expected primarily in the following fields: asynchronous multiple access channels, information theoretic secrecy, properties of entropy functionals, measure concentration and logarithmic Sobolev inequalities, combinatorics.

What is the significance of the research?
Describe the new perspectives opened by the results achieved, including the scientific basics of potential societal applications. Please describe the unique strengths of your proposal in comparison to your domestic and international competitors in the given field.

Within srtict sense information theory, the planned research will focus on areas which are intensively researched currently or appear to attract growing interest, as information theoretic secrecy and asynchronous multiple access channels. These areas of fundamental research emerged via mathematical modeling of important practical problems. Hence the research results, though they will appear as new mathematical theorems, may indirectly turn out beneficial also for these practical problems, specifically for maintaining secure communication or using mobile phones more efficiently. The results of the planned research about entropy functionals may also provide practical benefits, since several of these functionals (e.g. Bregman distances) have substantial statistical applications, e.g., in learning algorithms.
The research planned in other branches of mathematics, using information theoretic methods or addressing problems motivated by information theory, is significant on its own, by demonstrating the interplay of different fields. In addition, in the theory of measure concentration, one of the most efficient methods is currently the information theoretic one iniciated by us. In combinatorics, the problems motivated by information theory have lead to the development of an independent research area.

Summary and aims of the research for the public
Describe here the major aims of the research for an audience with average background information. This summary is especially important for NKFI in order to inform decision-makers, media, and the taxpayers.

In this project , fundamental research in mathematics is planned in two main directions, in strict sense information theory and in other branches of mathematics that have an interplay with information theory.
The first direction, in addition to its theoretical interest, may lead to practical applications, as well. Fundamental research in inforamtion theory had produced several results which were followed within a relatively short time by spectacular applications, see error correcting and data compression algorithms, space communication, internet. Within this project. we plan to study questions having emerged in the context of mathematical modeling of problems about communication security, respectively mobile phones. The expected results, which will be mathematical theorems, may contribute to a better understanding of these practical problems, and later may lead also to more direct applications, even if less spectacular than those mentioned above.
The other main direction of research addresses such problems in other branches of mathematics which can be studied by information theoretic methods or have emerged from information theoretic questions. The significance of this research direction is that it demonstrates the interplay of different branches of mathematics, as well as the adventages of utilizing this interplay.





 

Final report

 
Results in Hungarian
A kutatási terv szerinti munkát végeztük egyrészt a klasszikus Shannon elmélet területén, másrészt a matematika olyan területein, ahol az információelméleti módszerek már korábban hasznosnak bizonyultak. Exponenciális hibabecsléseket adtunk a korábbiaknál általánosabb hírközlési modellekre, így univerzális kódolással elérhető hibaexponenseket határoztunk meg töb felhasználós, valamint véletlen hozzáférésű csatornákra. A pénzügyi matematika területén vizsgáltunk egy információelméleti motiváltságú kockázatmodellt. Általános feltételek mellett megmutattuk, hogy bár legkedvezőtlenebb (a kockázatot maximalizáló) eloszlás nem mindig létezik, a közel legkedvezőtlenebbek mindig torlódnak egy konkrétan meghatározott, esetleg nem helyes eloszláshoz. Információelméleti módszerrel vizsgáltunk logaritmikus Sobolev egyenlőtlenségeket. Fontos speciális esetekben explicit becsléseket kaptunk az ú.n. Gibbs sampler által származtatott eloszlások konvergenciasebességére. Új összefüggéseket állapítottunk meg gráfok lokális kromatikus száma és ennek irányitott gráfokra vonatkozó megfelelője között. Bevezettünk egy információelméleti motiváltságú új gráfparamétert, erre becsléseket adtunk ismert gráfparaméterek függvényében.
Results in English
According to plan, research has been done both in classical Shannon theory and in areas of mathematis whereinformation theoretic methods have already proved successfull. Exponential error bounds have been derived for more general communication models that before. Error exponents achievable via universal coding have been given for multiple access and random access channels. In mathematical finance, a risk model motivated by information theory has been studied. It has been shown under general conditions that althrough a worst case distribution (yielding maximum risk) need not always exist, the almost worst case ones always cluster around a specified, perhaps incomplete, distribution. Logarithmic Sobolev inequalityes have been studied via information theoretic methods. In important special cases, explicit results hacve been obtained for the speed of convergence of distributions provided by the so-called Gibbs-sampler. New relations have been established between the localchromatic number of graphs and its counterpart for directed graphs. A new graph-parameter motivated by information theory has been introduced, and bounds to this were derived in terms of known graph parameters.
Full text https://www.otka-palyazat.hu/download.php?type=zarobeszamolo&projektid=105840
Decision
Yes





 

List of publications

 
L. Farkas, T. Kói: Random access and source-channel error exponent for multiple access channels, IEEE Trans. Inform. Theory Vol. 61. , pp. 3029 - 3040., 2015
L. Farkas, T Kói: Controlled asynchronism improves error exponents, Proc. ISIT 2015, 2638-2645 (electronic), 2015
L. Farkas, T. Kói: Successive decoding error exponent for multiple access channel., ISIT 2015 - poster, 2015
I Csiszár, T Breuer: An information theory problem in mathematical finance, LNCS 9389, pp. 435-443. Springer, 2015
G. Simonyi, G Tardos, A Zsbán: Relations between the local chromatic number and its directed version, J Graph Theory 79 pp. 319ó8-330., 2015
G Simonyi, A tóth: Dilworth rate: a generalization of Witsenhausen's zero-error rate for directed graphs, IEEE Trans Inform THeory Vol 61. (2) pp. 715-726., 2015
K. Marton: Distance-divergence inequalities, Shannon lecture ISIT 2013 Istambul, 2013
T. Breuer, I. Csiszár: An information geometry problem in mathematical finance, Geometric science of information, 435-443, Lecture Notes in Comput. Sci., 9389, pp. 435- 443., Springer, Cham, 2015
L. Farkas, T. Kói: Universal random access error exponents for codebooks of different block-lenghts, 2017 IEEE International Symposium on Information Theory, pp. 3155-3159. arXiv:1607.01935, 2016
K. Marton: Logarithmic Sobolev inequalities in discrete product spaces: a proof by a transportation cost distance, accepted for publication in Combinatorics, Probability and Computing., 2016
I. Csiszár, T. Breuer: Expected value minimization in information theoretic multiple prior models, IEEE Trans. Inform. Theory, accepted, 2016
Z. Helle, G. Simonyi: Orientations making k-cycles cyclic, Graphs and Combinatorics, 32 (2016), 2415 - 2423., 2016
I. Csiszar, F. Matus: Convergence of generalized entropy minimizers in sequences of convex problems, Proc. 2016 IEEE International Symposium on Information Theory, 2609 - 2613., 2016
L. Farkas, T Kói, I. Csiszár: Error Exponents for Sparse Communication, Proc. 2017 IEEE International Symposium on Information Theory, pp. 3150-3154, 2017
T. Breuer, I. Csiszár: Information Geometry in mathematical Finance, 2013 IEEE International Symposium on Information Theory pp. 404 -- 408., 2013
K. Marton: Distance-divergence inequalities, Shannon lecture ISIT 2013 Istambul, 2013
L. Farkas, T. Kói: Random Access and Source-Channel Coding Error Exponents for Multiple Access Channels, 2013 IEEE International Symposium on Information Theory pp. 374 -- 378., 2013
T. Breuer, I. Csiszár: Measuring Distribution Model Risk, Mathematical Finance (published online, 2013
G. Simonyi, C. Tardif, A. Zsbán: Colorful theorems and indices of homomorphism complexes, Electron. J. Combin,. 20 (2013) no. 1. #P10, 2013
G. Simonyi, G. Tardos, B. Mohar: Local chromatic number of quadrangulations of surfaces, Combinatorica, 33 pp. 467 -- 494., 2013
G Simonyi, A Toth: Dilworth rate: a generalization of Witsenhausen's zero-error rate for directed graphs, IEEE TRANSACTIONS ON INFORMATION THEORY (ISSN: 0018-9448) 61: (2) pp. 715-726. (2015), 2015
G Simonyi, G Tardos, A Zsbán: Relations between the local chromatic number and its directed version, JOURNAL OF GRAPH THEORY (ISSN: 0364-9024) (eISSN: 1097-0118) 79: (4) pp. 318-330. (2014), 2014
G Simonyi, A Toth: A generalization of Witsenhausen's zero-error rate for directed graphs, ISIT 2014, IEEE International Symposium on Information Theory. pp. 2864-2868., 2014





 

Events of the project

 
2016-03-18 12:55:32
Résztvevők változása




Back »