коммуникационная сложность

Иван Андреевич Михайлин

лаборатория прикладных вероятностных и алгоритмических методов
Должность: 
научный сотрудник
Email: 
ivmihajlin [at] gmail.com
Научные интересы: 
Схемная сложность
высокоточная теория сложности
алгоритмы
коммуникационная сложность
арифметическая сложность

Краткая биография:

Образование:
2012
Санкт-Петербургский политехнический университет Петра Великого,
Физико-технический факультет,
Физика твердого тела.
2014
Академический университет им. Ж.И. Алферова
Факультет теоретической информатики.
2019
Университет Калифорнии в Сан-Диего (UCSD, США).
Факультет: Computer Science and Engineering
 

Основные публикации:

1. Nondeterministic extensions of the strong exponential time hypothesis and consequences for non-reducibility L Carmosino, J Gao, R Impagliazzo, I Mihajlin, R Paturi, S Schneider

2. Tight Bounds for Graph Homomorphism and Subgraph Isomorphism Marek Cygan, Fedor V. Fomin, Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin, Jakub Pachocki, and Arkadiusz Socała

3.Toward better depth lower bounds: the XOR-KRW conjecture I Mihajlin, A Smal

4. Polynomial formulations as a barrier for reduction-based hardness proofs T Belova, A Golovnev, AS Kulikov, I Mihajlin, D Sharipov

https://scholar.google.ru/citations?user=fXSjhHoAAAAJ&hl=ru&oi=sra

 

Александр Владимирович Смаль

лаборатория математической логики и дискретной математики
Должность: 
младший научный сотрудник
Учёная степень: 
кандидат ф.-м. наук
Email: 
smal [at] pdmi.ras.ru
Домашняя страница: 
http://logic.pdmi.ras.ru/~smal/
Научные интересы: 
Теория сложности булевых схем
коммуникационная сложность
теория информации
алгоритмы

Образование:

2008 Университет ИТМО, факультет информационных технологий и программирования, прикладная математика и информатика.

Публикации:

  1. Ivan Mihajlin, Alexander Smal: Toward Better Depth Lower Bounds: The XOR-KRW Conjecture. CCC 2021: 38:1-38:24.
  2. Kenneth Hoover, Russell Impagliazzo, Ivan Mihajlin, Alexander V. Smal: Half-Duplex Communication Complexity. ISAAC 2018: 10:1-10:12.
  3. Alexander V. Smal, Navid Talebanfard: Prediction from partial information and hindsight, an alternative proof. Inf. Process. Lett. 136: 102-104 (2018).
  4. Alexander Golovnev, Alexander S. Kulikov, Alexander V. Smal, Suguru Tamaki: Gate elimination: Circuit size lower bounds and #SAT upper bounds. Theor. Comput. Sci. 719: 46-63 (2018).
  5. Edward A. Hirsch, Dmitry Itsykson, Ivan Monakhov, Alexander Smal: On Optimal Heuristic Randomized Semidecision Procedures, with Applications to Proof Complexity and Cryptography. Theory Comput. Syst. 51(2): 179-195 (2012).

https://dblp.uni-trier.de/pid/74/8864.html