Skip to main content
Home

St. Petersburg Department
of Steklov Mathematical Institute
of Russian Academy of Sciences

27 Fontanka, St. Petersburg, Russia

Main menu

  • Institute structure
    • Administration
    • EIMI
    • Laboratories
    • Researchers
    • Academic council
    • Center of Research and Education
    • Publishing Department
    • Contacts
  • Activities
    • Conferences
    • Seminars
    • Dissertation Councils
    • Journal "Algebra and Analysis"
    • Journal "Zapiski Nauchnykh Seminarov POMI"
    • Preprints (partially in Russian)
    • Publications
  • Search
  • Resources
    • Video records
    • History of the Institute
    • Digital libraries (in Russian)
    • Links (in Russian)
    • Former Employees
    • Remembering Olga Ladyzhenskaya
    • PDMI Library

арифметическая сложность

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

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

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

Образование:
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

 

  • Русский Русский
  • English English