Information Theory and its Applications  Page description

Help  Print 
Back »

 

Details of project

 
Identifier
120706
Type K
Principal investigator Simonyi, Gábor
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, matematikai statisztika, mértékkoncentráció, kombinatorika, gráfelmélet
Keywords in English Information theory, mathematical statistics, measure concentration, combinatorics, graph theory
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
Participants Csiszár, Imre
Farkas, Lóránt
Gujgiczer, Anna
Kói, Tamás
Marton, Katalin
Soltész, Dániel
Starting date 2016-12-01
Closing date 2023-06-30
Funding (in million HUF) 13.569
FTE (full time equivalent) 15.73
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.

Jelen pályázat az eddig Csiszár Imre vezetésével folyó, több cikluson keresztül támogatott kutatás folyamatosságát hivatott biztosítani. Ennek megfelelően a pályázat az MTA Rényi Alfréd Matematikai Kutatóintézetben 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, Dilworth rátájá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 és gráfelmélet.

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 érdeklődők tájékoztatása szempontjából különösen fontos az NKFI Hivatal 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.

This proposal aims to support the continuation of the research led so far by Imre Csiszár and supported during several project periods. In accordance with this 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, Dilworth rate 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 and graph theory.

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 initiated 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 NRDI Office in order to inform decision-makers, media, and others.

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 klasszikus információelmélet területén több eredményt sikerült bizonyítani a többszörös hozzáférésű csatornán történő aszinkron információtovábbítással kapcsolatban. Az egyik fő eredmény annak felismerése, hogy a kontrolláltan aszinkron működtetés jobb hibaexponenst eredményezhet mint a szinkron működtetés. További észrevétel, hogy a többszörös hozzáférésű csatorna egy kontrolláltan aszinkron kódja egy egyadós trellis kódot eredményez. Információelméleti módszerek segítségével sikerült log-Sobolev egyenlőtlenséget bizonyítani és használtunk ilyen módszereket pénzügyi és statisztikai problémákhoz is. Számos eredmény született az információelméleti kombinatorikának nevezhető területen. Ezek közül több is korlátokat vagy pontos eredményeket ad a rögzített n csúcson megadható olyan Hamilton utak számára, melyek közül bármely kettő uniója tartalmaz egy előírt részgráfot. Sikerült megválaszolni Tardif egy kérdését Kneser gráfokba irányuló bizonyos gráfhomomorfizmusokkal kapcsolatban. Szükséges illetve elégséges feltételeket bizonyítottunk Schrijver gráfok éleinek színkritikusságával kapcsolatban és sikerült megadni Schrijver gráfoknak egy a tört kromatikus számra nézve kritikus feszített részgráfját. Bevezettünk gráfokból álló kódokat és éles eredményeket bizonyítottunk róluk számos speciális esetben. A Shannon-féle gráfkapacitás Hedetniemi-típusú egyenlőséggel kapcsolatos vizsgálatát kezdeményeztük, illetve vizsgáltuk a gráfkapacitást Ramsey-típusú tételekkel kapcsolatban is.
Results in English
In the area of classical information theory several results were proven concerning asynchromous transmission over a multiple access channel (MAC). One of the main findings was that controlled asynchronism may outperform synchronism as far as the error exponents are concerned. It was also observed that a controlled asynchronous code for a MAC gives rise to a one-sender trellis code. Information theoretic techniques were also used to prove a log-Sobolev inequaity and to problems related to finance and statistics. Several results were proven in the are of information theory related combinatorics. Some of these give bounds or exact results about the maximum number of Hamiltonian paths on a given set of n vertices that have the property that the union of any two of them contains a prescribed subgraph. A question of Tardif was answered about the existence of certain graph homomorphisms into Kneser graphs. Criteria about the color-criticality of edges in Schrijver graphs were proven and the criticality of a certain induced subgraph of Schrijver graphs was shown with respect to the fractional chromatic number. Graph codes were introduced and tight results about their maximum possible size were proven in several special cases. Investgations about the behaviour of the Shannon capacity of graphs and a Hedetniemi-type equality were initiated. Shannon's graph capacity problem was also investigated in relation with Ramsey type results.
Full text https://www.otka-palyazat.hu/download.php?type=zarobeszamolo&projektid=120706
Decision
Yes





 

List of publications

 
L. Farkas, T. Kói: Universal random access error exponents for codebooks of different word-lengths, IEEE Transactions on Information Theory, vol. 64., pp. 2240-2252., 2018
D. Soltész: New bounds on Simonyi's conjecture, European Journal of Combinatorics, Vol. 70, pp. 251-267., 2018
Anna Gujgiczer, Gábor Simonyi: On multichromatic numbers of widely colorable graphs,, J. Graph Theory, vol. 100, pp. 346-351., 2022
Noga Alon, Anna Gujgiczer, János Körner, Aleksa Milojević, Gábor Simonyi: Structured codes of graphs, SIAM J. Discrete Math., accepted for publication, 2022
Anna Gujgiczer, Gábor Simonyi: Critical subgraphs of Schrijver graphs for the fractional chromatic number, submitted, 2022
Eszter Uhrin, Zsuzsanna Domokos, László Márk Czumbel, Tamás Kói, Péter Hegyi , Péter Hermann, Judit Borbély, Bianca Golzio Navarro Cavalcante, Orsolya Németh: Teledentistry: A Future Solution In The Diagnosis Of Oral Lesions: A Diagnostic Meta-Analysis And Systematic Review, Telemedicine and e-Health, accepted, 2022
L. Farkas, T. Kói, I. Csiszár: Error exponents for sparse communication, Proceedings of IEEE International Symposium on Information Theory, pp. 3145-3149., 2017
Gergely Harcos, Daniel Soltész: New bounds on even cycle creating Hamiltonian paths using expander graphs, Combinatorica 40, 435-454, 2020
Lóránt Farkas: Trellis Code Error Exponent From Results for Asynchronous Multiple Access Channels, ISITA2020 (A01-10.), http://www.isita.ieice.org/2020/technical_program_all.html, 2020
Noga Alon, Anna Gujgiczer, János Körner, Aleksa Milojević, Gábor Simonyi: Structured codes of graphs, SIAM J. Discrete Math., 37, 379-403;, 2023
Eszter Uhrin, Zsuzsanna Domokos, László Márk Czumbel, Tamás Kói, Péter Hegyi , Péter Hermann, Judit Borbély, Bianca Golzio Navarro Cavalcante, Orsolya Németh: Teledentistry: A Future Solution In The Diagnosis Of Oral Lesions: A Diagnostic Meta-Analysis And Systematic Review, Telemedicine and e-Health, accepted (published online 28 Mar 2023), 2023
Anna Gujgiczer, Reza Naserasr, Rohini S, S Taruni: Winding number and circular 4-coloring of signed graphs, submitted, 2023
Anna Gujgiczer, Gábor Simonyi, Gábor Tardos: On the generalized Myczielskian of complements of odd cycles, Proceedings of the 12th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications, pp. 485-488., 2023
A. Sali, G. Simonyi, G. Tardos: Partitioning transitive tournaments into isomorphic digraphs, Order, 2020
G. Simonyi: On colorful edge triples in edge-colored complete graphs, Graphs and Combinatorics 36, 1623–1637., 2020
D. Soltész: Even cycle creating paths, J. Graph Theory 93 (3), 350-362, 2020
Gergely Harcos, Daniel Soltész: New bounds on even cycle creating Hamiltonian paths using expander graphs, Combinatorica 40, 435-454, 2020
Gábor Simonyi: Shannon capacity and the categorical product, arXiv:1911.00944 [math.CO] (submitted for publication), 2019
Gábor Simonyi, Gábor Tardos: On 4-chromatic Schrijver graphs: their structure, non-3-colorability, and critical edges, Acta Math. Hungar. 161 (2: Special issue dedicated to Endre Szemerédi's 80th birthday), 583–617, 2020
Imre Csiszár, Lóránt Farkas, Tamás Kói: Error exponents for asynchronous multiple access channels. controlled asynchronism may outperform synchronism, arXiv:1907.05139 [cs.IT], v2:2020, 2019
Lóránt Farkas: Trellis Code Error Exponent From Results for Asynchronous Multiple Access Channels, ISITA2020 (A01-10.), http://www.isita.ieice.org/2020/technical_program_all.html, 2020
A. Sali, G. Simonyi, G. Tardos: Partitioning transitive tournaments into isomorphic digraphs, Order, vol. 38, pp. 211-228., 2021
Péter L. Erdős, Ervin Győri, Tamás Róbert Mezei, István Miklós, Dániel Soltész: Half-graphs, other non-stable degree sequences, and the switch Markov chain, Electronic Journal of Combinatorics, Volume 28, Issue 3 (2021) P3.7, 2021
Péter L. Erdős, Catherine Greenhill, Tamás Róbert Mezei, István Miklós, Dániel Soltész, Lajos Soukup: The mixing time of switch Markov chains: a unified approach, European Journal of Combinatorics 99, #103421, 2022
Gábor Simonyi: Shannon capacity and the categorical product, Electronic Journal of Combinatorics, Volume 28, Issue 1, #P1.51, 2021
Imre Csiszár, Lóránt Farkas, Tamás Kói: Error exponents for asynchronous multiple access channels. controlled asynchronism may outperform synchronism, IEEE Transactions on Information Theory, vol. 67, no. 12, pp. 7684-7707., 2021
Anna Gujgiczer, Gábor Simonyi: On multichromatic numbers of widely colorable graphs,, J. Graph Theory, to appear; online already appeared at https://doi.org/10.1002/jgt.22785, 2021
L. Farkas, T. Kói: Universal random access error exponents for codebooks of different word-lengths, Proceedings of IEEE International Symposium on Information Theory, pp. 3150-3154, 2017
L. Farkas, T. Kói, I. Csiszár: Error exponents for sparse communication, Proceedings of IEEE International Symposium on Information Theory, pp. 3145-3149., 2017
I. Kovács, D. Soltész: Triangle-different Hamiltonian paths, Journal of Combinatorial Theory Series B, in press, available online, 2017
L. Farkas, T. Kói: Universal random access error exponents for codebooks of different word-lengths, IEEE Transactions on Information Theory, vol. 64., pp. 2240-2252., 2018
I. Kovács, D. Soltész: Triangle-different Hamiltonian paths, Journal of Combinatorial Theory Series B, Volume 129, pp. 1-17., 2018
I. Csiszár, T. Breuer: Expected value minimization in information theoretic multiple priors models, IEEE Transactions on Information Theory, vol. 64., pp. 1957-1974., 2018
L. Farkas, T. Kói: Contributions to successive decoding for multiple access channels, International Symposium on Information Theory and Its Applications (ISITA) Proceedings, 602-606., 2018
R. Aharoni, D. Soltész: Independent sets in the union of two Hamiltonian cycles, Electronic Journal of Combinatorics, Volume 25, Issue 4, 2018
P. L. Erdős, T. R. Mezei, I. Miklós, D. Soltész: Efficiently sampling the realizations of bounded, irregular degree sequences of bipartite and directed graphs, PLoS ONE 13(8): e0201995, 2018
L. Farkas, T. Kói,: An Improved Packing Lemma for Asynchronous Multiple Access Channel,, International Symposium on Information Theory (ISIT), 26 (2018), recent result poster session, 2018
D. Soltész: New bounds on Simonyi's conjecture, European Journal of Combinatorics, Vol. 70, pp. 251-267., 2018
A. Sali, G. Simonyi, G. Tardos: Partitioning transitive tournaments into isomorphic digraphs, arXiv:1806.00729 [math.CO] (submitted for publication), 2018
G. Simonyi: On colorful edge triples in edge-colored complete graphs, arXiv:1812.06706 [math.CO] (submitted for publication), 2018
I. Kovács, D. Soltész: On k-neighbor separated permutations, arXiv:1711.07524 [math.CO] (submitted for publication), 2017
D. Soltész: Even cycle creating paths, arXiv:1801.00737 [math.CO] (submitted for publication), 2018
I. Kovács, D. Soltész: Triangle-different Hamiltonian paths, Journal of Combinatorial Theory Series B, Volume 129, pp. 1-17., 2018
L. Farkas, T. Kói,: Two contributions to error exponents for asynchronous multiple access channel, International Symposium on Information Theory Proceedings (ISIT), 27 (2019), 2664 - 2668., 2019
A. Sali, G. Simonyi, G. Tardos: Partitioning transitive tournaments into isomorphic digraphs, arXiv:1806.00729 [math.CO] (preprint), 2018
I. Kovács, D. Soltész: On k-neighbor separated permutations, SIAM J. Discrete Math. 33(3), 1691–1711; https://doi.org/10.1137/17M1158744, 2019
D. Soltész: Even cycle creating paths, J. Graph Theory; https://doi.org/10.1002/jgt.22490, (accepted for publication), 2019
Péter L. Erdős, Ervin Győri, Tamás Róbert Mezei, István Miklós, Dániel Soltész: A non-P-stable class of degree sequences for which the swap Markov chain is rapidly mixing, arXiv:1909.02308 [math.CO] (submitted for publication), 2019
Péter L. Erdős, Catherine Greenhill, Tamás Róbert Mezei, István Miklós, Dániel Soltész, Lajos Soukup: The mixing time of the switch Markov chains: a unified approach, arXiv:1903.06600 [math.CO] (submitted for publication), 2019
Gergely Harcos, Daniel Soltész: New bounds on even cycle creating Hamiltonian paths using expander graphs, arXiv:1904.04601 [math.CO] (submitted for publication), 2019
Gábor Simonyi: Shannon capacity and the categorical product, arXiv:1911.00944 [math.CO] (submitted for publication), 2019
Gábor Simonyi, Gábor Tardos: On 4-chromatic Schrijver graphs: their structure, non-3-colorability, and critical edges, arXiv:1912.03724 [math.CO] (submitted for publication), 2019
Katalin Marton: Logarithmic Sobolev inequalities in discrete product spaces, Combin. Probab. Comput. 28, no. 6, 919–935., 2019
Lóránt Farkas, Tamás Kói: Error exponents for asynchronous multiple access channels. controlled asynchronism may outperform synchronism, arXiv:1907.05139 [cs.IT], 2019





 

Events of the project

 
2021-01-08 13:48:10
Résztvevők változása




Back »