 |
Information Theory and its Applications
|
Help 
Print 
|
Here you can view and search the projects funded by NKFI since 2004
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.
|
|
|
|
|
|
|
|
| |
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 |
|
|
|
|
|
|
|
|
|
