Так как я неудавшийся учёный в теоретической информатике, я всё ещё с трепетом порой вспоминаю с̶в̶о̶ю̶ ̶м̶о̶л̶о̶д̶о̶с̶т̶ь̶, что неплохо бы почитывать теоретические вещи время от времени. Я не хочу забывать математику, а также для меня это способ сделать себе карьеру, принося интересные идеи в инженерию, а также ощущение наукоёмкости и загруженности мозга.
В целом суть такова, что кроссовер, который меня сегодня настиг, очень забавен.
В теории есть достаточно сложная задача о нахождении максимальной клики (полного графа) в случайных графах G(n, 1/2), где каждое ребро в графе на n вершинах выбирается с вероятностью 1/2. Понятное дело, что размер максимальной клики будет $c log n$ с большой вероятностью, тем не менее, оказывается, что если взять такой случайный граф и поместить туда случайно клику размера k, то известно следующее
1. k >= \sqrt(n), то полиномиальный алгоритм нахождения существует, там кстати забавный алгоритм [2], хоть даже в универе рассказывай
2. k = o(\sqrt(n)), k = \Omega(log n), то это открытый вопрос, гипотеза, что нет
В текущей криптографии очень много завязано на RSA, которое в эпоху квантовых компьютеров не имеет смысла, и мне было вечером интересно, что происходит там дальше. Оказалось, что задачу про клику рассматривают [3,4] для будущего шифрования. Также, так как я немного увлёкся соц графами, то прочитал в итоге [5], про то, как искать большие культы в таких графах из-за статьи по Maximum Biclique Search at Billion Scale [10], которую я случайно наткнулся из VLDB-2020 paper awards [9].
Примерно год назад я помогал моему товарищу (и ничего не знал про то, что эта задача вообще важна в social networks [5] и машинном обучении [6]) по университету с одной теоремой и просто минимальной вычиткой задачи про прятание клики в случайном графе -- отличие лишь в том, что клику можно не случайно помещать, а произвольно, то полиномиальный алгоритм при k >= sqrt(n) тоже существует. Даже получил благодарность в acknowledgments за это [8].
Забавно, что ничего не зная год назад про то, зачем оно используется на практике (или хотя бы планируется), наткнулся на эту тему совершенно с другой стороны. Статья была принята на конференцию ICALP [7], кстати, которая является достаточно сильной в теоретической информатике. Практического применения этому особо нет, но развитие темы не менее важно.
Мечтаю когда-нибудь написать/дописать свою статью, найти бы идеи и время. И ещё я рад, что я могу читать такие статьи.
[1] Planted Clique in G(n,p), varying p
[2] Finding a Large Hidden Clique in a Random Graph
[3] Hiding Cliques for Cryptographic Security
[4] Public key cryptography based on the clique andlearning parity with noise problems for post-quantum cryptography
[5] Finding Endogenously Formed Communities
[6] Complexity Theoretic Lower Boundsfor Sparse Principal Component Detection
[7] ICALP
[8] How to hide a Clique?
[9] VLDB
[10] Maximum Biclique Search at Billion Scale
В целом суть такова, что кроссовер, который меня сегодня настиг, очень забавен.
В теории есть достаточно сложная задача о нахождении максимальной клики (полного графа) в случайных графах G(n, 1/2), где каждое ребро в графе на n вершинах выбирается с вероятностью 1/2. Понятное дело, что размер максимальной клики будет $c log n$ с большой вероятностью, тем не менее, оказывается, что если взять такой случайный граф и поместить туда случайно клику размера k, то известно следующее
1. k >= \sqrt(n), то полиномиальный алгоритм нахождения существует, там кстати забавный алгоритм [2], хоть даже в универе рассказывай
2. k = o(\sqrt(n)), k = \Omega(log n), то это открытый вопрос, гипотеза, что нет
В текущей криптографии очень много завязано на RSA, которое в эпоху квантовых компьютеров не имеет смысла, и мне было вечером интересно, что происходит там дальше. Оказалось, что задачу про клику рассматривают [3,4] для будущего шифрования. Также, так как я немного увлёкся соц графами, то прочитал в итоге [5], про то, как искать большие культы в таких графах из-за статьи по Maximum Biclique Search at Billion Scale [10], которую я случайно наткнулся из VLDB-2020 paper awards [9].
Примерно год назад я помогал моему товарищу (и ничего не знал про то, что эта задача вообще важна в social networks [5] и машинном обучении [6]) по университету с одной теоремой и просто минимальной вычиткой задачи про прятание клики в случайном графе -- отличие лишь в том, что клику можно не случайно помещать, а произвольно, то полиномиальный алгоритм при k >= sqrt(n) тоже существует. Даже получил благодарность в acknowledgments за это [8].
Забавно, что ничего не зная год назад про то, зачем оно используется на практике (или хотя бы планируется), наткнулся на эту тему совершенно с другой стороны. Статья была принята на конференцию ICALP [7], кстати, которая является достаточно сильной в теоретической информатике. Практического применения этому особо нет, но развитие темы не менее важно.
Мечтаю когда-нибудь написать/дописать свою статью, найти бы идеи и время. И ещё я рад, что я могу читать такие статьи.
[1] Planted Clique in G(n,p), varying p
[2] Finding a Large Hidden Clique in a Random Graph
[3] Hiding Cliques for Cryptographic Security
[4] Public key cryptography based on the clique andlearning parity with noise problems for post-quantum cryptography
[5] Finding Endogenously Formed Communities
[6] Complexity Theoretic Lower Boundsfor Sparse Principal Component Detection
[7] ICALP
[8] How to hide a Clique?
[9] VLDB
[10] Maximum Biclique Search at Billion Scale