default search action

combined dblp search
author search
venue search
publication search

ask others

BibTeX records: Ivan Mihajlin

Name: dblp XML data dump
Creator: Schloss Dagstuhl - Leibniz Center for Informatics
Published: 1993
License: https://creativecommons.org/publicdomain/zero/1.0/
Keywords: dblp, XML, computer science, scholarly publications, metadata

> Home > Persons > Ivan Mihajlin

download as .bib file

@inproceedings{DBLP:conf/esa/BelovaCKM24,
  author       = {Tatiana Belova and
                  Nikolai Chukhin and
                  Alexander S. Kulikov and
                  Ivan Mihajlin},
  title        = {Improved Space Bounds for Subset Sum},
  booktitle    = {{ESA}},
  series       = {LIPIcs},
  volume       = {308},
  pages        = {21:1--21:17},
  publisher    = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
  year         = {2024}
}

@inproceedings{DBLP:conf/soda/BelovaKMRRS24,
  author       = {Tatiana Belova and
                  Alexander S. Kulikov and
                  Ivan Mihajlin and
                  Olga Ratseeva and
                  Grigory Reznikov and
                  Denil Sharipov},
  title        = {Computations with polynomial evaluation oracle: ruling out superlinear
                  SETH-based lower bounds},
  booktitle    = {{SODA}},
  pages        = {1834--1853},
  publisher    = {{SIAM}},
  year         = {2024}
}

@inproceedings{DBLP:conf/sosa/KulikovM24,
  author       = {Alexander S. Kulikov and
                  Ivan Mihajlin},
  title        = {If Edge Coloring is Hard under SETH, then {SETH} is False},
  booktitle    = {{SOSA}},
  pages        = {115--120},
  publisher    = {{SIAM}},
  year         = {2024}
}

@article{DBLP:journals/corr/abs-2402-13170,
  author       = {Tatiana Belova and
                  Nikolai Chukhin and
                  Alexander S. Kulikov and
                  Ivan Mihajlin},
  title        = {Improved Space Bounds for Subset Sum},
  journal      = {CoRR},
  volume       = {abs/2402.13170},
  year         = {2024}
}

@inproceedings{DBLP:conf/soda/BelovaGKMS23,
  author       = {Tatiana Belova and
                  Alexander Golovnev and
                  Alexander S. Kulikov and
                  Ivan Mihajlin and
                  Denil Sharipov},
  title        = {Polynomial formulations as a barrier for reduction-based hardness
                  proofs},
  booktitle    = {{SODA}},
  pages        = {3245--3281},
  publisher    = {{SIAM}},
  year         = {2023}
}

@article{DBLP:journals/corr/abs-2307-11444,
  author       = {Tatiana Belova and
                  Alexander S. Kulikov and
                  Ivan Mihajlin and
                  Olga Ratseeva and
                  Grigory Reznikov and
                  Denil Sharipov},
  title        = {Computations with polynomial evaluation oracle: ruling out superlinear
                  SETH-based lower bounds},
  journal      = {CoRR},
  volume       = {abs/2307.11444},
  year         = {2023}
}

@inproceedings{DBLP:conf/coco/MihajlinS22,
  author       = {Ivan Mihajlin and
                  Anastasia Sofronova},
  title        = {A Better-Than-3log(n) Depth Lower Bound for De Morgan Formulas with
                  Restrictions on Top Gates},
  booktitle    = {{CCC}},
  series       = {LIPIcs},
  volume       = {234},
  pages        = {13:1--13:15},
  publisher    = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
  year         = {2022}
}

@inproceedings{DBLP:conf/isaac/IgnatievMS22,
  author       = {Artur Ignatiev and
                  Ivan Mihajlin and
                  Alexander Smal},
  title        = {Super-Cubic Lower Bound for Generalized Karchmer-Wigderson Games},
  booktitle    = {{ISAAC}},
  series       = {LIPIcs},
  volume       = {248},
  pages        = {66:1--66:18},
  publisher    = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
  year         = {2022}
}

@inproceedings{DBLP:conf/mfcs/EmdinKMS22,
  author       = {Gregory Emdin and
                  Alexander S. Kulikov and
                  Ivan Mihajlin and
                  Nikita Slezkin},
  title        = {{CNF} Encodings of Parity},
  booktitle    = {{MFCS}},
  series       = {LIPIcs},
  volume       = {241},
  pages        = {47:1--47:12},
  publisher    = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
  year         = {2022}
}

@article{DBLP:journals/corr/abs-2203-01082,
  author       = {Gregory Emdin and
                  Alexander S. Kulikov and
                  Ivan Mihajlin and
                  Nikita Slezkin},
  title        = {{CNF} Encodings of Parity},
  journal      = {CoRR},
  volume       = {abs/2203.01082},
  year         = {2022}
}

@article{DBLP:journals/corr/abs-2205-07709,
  author       = {Alexander S. Kulikov and
                  Ivan Mihajlin},
  title        = {Polynomial formulations as a barrier for reduction-based hardness
                  proofs},
  journal      = {CoRR},
  volume       = {abs/2205.07709},
  year         = {2022}
}

@article{DBLP:journals/eccc/IgnatievMS22,
  author       = {Artur Ignatiev and
                  Ivan Mihajlin and
                  Alexander Smal},
  title        = {Super-cubic lower bound for generalized Karchmer-Wigderson games},
  journal      = {Electron. Colloquium Comput. Complex.},
  volume       = {{TR22-016}},
  year         = {2022}
}

@article{DBLP:journals/eccc/MihajlinS22,
  author       = {Ivan Mihajlin and
                  Anastasia Sofronova},
  title        = {A better-than-$3\log{n}$ depth lower bound for De Morgan formulas with restrictions on top gates},
  journal      = {Electron. Colloquium Comput. Complex.},
  volume       = {{TR22-033}},
  year         = {2022}
}

@article{DBLP:journals/toct/FominLMSZ21,
  author       = {Fedor V. Fomin and
                  Daniel Lokshtanov and
                  Ivan Mihajlin and
                  Saket Saurabh and
                  Meirav Zehavi},
  title        = {Computation of Hadwiger Number and Related Contraction Problems: Tight
                  Lower Bounds},
  journal      = {{ACM} Trans. Comput. Theory},
  volume       = {13},
  number       = {2},
  pages        = {10:1--10:25},
  year         = {2021}
}

@inproceedings{DBLP:conf/coco/MihajlinS21,
  author       = {Ivan Mihajlin and
                  Alexander Smal},
  title        = {Toward Better Depth Lower Bounds: The {XOR-KRW} Conjecture},
  booktitle    = {{CCC}},
  series       = {LIPIcs},
  volume       = {200},
  pages        = {38:1--38:24},
  publisher    = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
  year         = {2021}
}

@inproceedings{DBLP:conf/esa/CyganKMNR21,
  author       = {Marek Cygan and
                  Alexander S. Kulikov and
                  Ivan Mihajlin and
                  Maksim Nikolaev and
                  Grigory Reznikov},
  title        = {Minimum Common String Partition: Exact Algorithms},
  booktitle    = {{ESA}},
  series       = {LIPIcs},
  volume       = {204},
  pages        = {35:1--35:16},
  publisher    = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
  year         = {2021}
}

@inproceedings{DBLP:conf/icalp/FominLM0Z20,
  author       = {Fedor V. Fomin and
                  Daniel Lokshtanov and
                  Ivan Mihajlin and
                  Saket Saurabh and
                  Meirav Zehavi},
  title        = {Computation of Hadwiger Number and Related Contraction Problems: Tight
                  Lower Bounds},
  booktitle    = {{ICALP}},
  series       = {LIPIcs},
  volume       = {168},
  pages        = {49:1--49:18},
  publisher    = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
  year         = {2020}
}

@article{DBLP:journals/corr/abs-2004-11621,
  author       = {Fedor V. Fomin and
                  Daniel Lokshtanov and
                  Ivan Mihajlin and
                  Saket Saurabh and
                  Meirav Zehavi},
  title        = {Computation of Hadwiger Number and Related Contraction Problems: Tight
                  Lower Bounds},
  journal      = {CoRR},
  volume       = {abs/2004.11621},
  year         = {2020}
}

@article{DBLP:journals/eccc/MihajlinS20,
  author       = {Ivan Mihajlin and
                  Alexander Smal},
  title        = {Toward better depth lower bounds: the {XOR-KRW} conjecture},
  journal      = {Electron. Colloquium Comput. Complex.},
  volume       = {{TR20-116}},
  year         = {2020}
}

@inproceedings{DBLP:conf/approx/GolovnevKLMN19,
  author       = {Alexander Golovnev and
                  Alexander S. Kulikov and
                  Alexander Logunov and
                  Ivan Mihajlin and
                  Maksim Nikolaev},
  title        = {Collapsing Superstring Conjecture},
  booktitle    = {{APPROX-RANDOM}},
  series       = {LIPIcs},
  volume       = {145},
  pages        = {26:1--26:23},
  publisher    = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
  year         = {2019}
}

@inproceedings{DBLP:conf/coco/CarmosinoILM18,
  author       = {Marco L. Carmosino and
                  Russell Impagliazzo and
                  Shachar Lovett and
                  Ivan Mihajlin},
  title        = {Hardness Amplification for Non-Commutative Arithmetic Circuits},
  booktitle    = {{CCC}},
  series       = {LIPIcs},
  volume       = {102},
  pages        = {12:1--12:16},
  publisher    = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
  year         = {2018}
}

@inproceedings{DBLP:conf/isaac/HooverIMS18,
  author       = {Kenneth Hoover and
                  Russell Impagliazzo and
                  Ivan Mihajlin and
                  Alexander V. Smal},
  title        = {Half-Duplex Communication Complexity},
  booktitle    = {{ISAAC}},
  series       = {LIPIcs},
  volume       = {123},
  pages        = {10:1--10:12},
  publisher    = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
  year         = {2018}
}

@article{DBLP:journals/corr/abs-1809-08669,
  author       = {Alexander Golovnev and
                  Alexander S. Kulikov and
                  Alexander Logunov and
                  Ivan Mihajlin},
  title        = {Collapsing Superstring Conjecture},
  journal      = {CoRR},
  volume       = {abs/1809.08669},
  year         = {2018}
}

@article{DBLP:journals/eccc/CarmosinoILM18,
  author       = {Marco Carmosino and
                  Russell Impagliazzo and
                  Shachar Lovett and
                  Ivan Mihajlin},
  title        = {Hardness Amplification for Non-Commutative Arithmetic Circuits},
  journal      = {Electron. Colloquium Comput. Complex.},
  volume       = {{TR18-095}},
  year         = {2018}
}

@article{DBLP:journals/eccc/HooverIMS18,
  author       = {Kenneth Hoover and
                  Russell Impagliazzo and
                  Ivan Mihajlin and
                  Alexander Smal},
  title        = {Half-duplex communication complexity},
  journal      = {Electron. Colloquium Comput. Complex.},
  volume       = {{TR18-089}},
  year         = {2018}
}

@article{DBLP:journals/jacm/CyganFGKMPS17,
  author       = {Marek Cygan and
                  Fedor V. Fomin and
                  Alexander Golovnev and
                  Alexander S. Kulikov and
                  Ivan Mihajlin and
                  Jakub Pachocki and
                  Arkadiusz Socala},
  title        = {Tight Lower Bounds on Graph Embedding Problems},
  journal      = {J. {ACM}},
  volume       = {64},
  number       = {3},
  pages        = {18:1--18:22},
  year         = {2017}
}

@article{DBLP:journals/talg/GolovnevKM16,
  author       = {Alexander Golovnev and
                  Alexander S. Kulikov and
                  Ivan Mihajlin},
  title        = {Families with Infants: Speeding Up Algorithms for NP-Hard Problems
                  Using {FFT}},
  journal      = {{ACM} Trans. Algorithms},
  volume       = {12},
  number       = {3},
  pages        = {35:1--35:17},
  year         = {2016}
}

@inproceedings{DBLP:conf/innovations/CarmosinoGIMPS16,
  author       = {Marco L. Carmosino and
                  Jiawei Gao and
                  Russell Impagliazzo and
                  Ivan Mihajlin and
                  Ramamohan Paturi and
                  Stefan Schneider},
  title        = {Nondeterministic Extensions of the Strong Exponential Time Hypothesis
                  and Consequences for Non-reducibility},
  booktitle    = {{ITCS}},
  pages        = {261--270},
  publisher    = {{ACM}},
  year         = {2016}
}

@inproceedings{DBLP:conf/soda/CyganFGKMPS16,
  author       = {Marek Cygan and
                  Fedor V. Fomin and
                  Alexander Golovnev and
                  Alexander S. Kulikov and
                  Ivan Mihajlin and
                  Jakub Pachocki and
                  Arkadiusz Socala},
  title        = {Tight Bounds for Graph Homomorphism and Subgraph Isomorphism},
  booktitle    = {{SODA}},
  pages        = {1643--1649},
  publisher    = {{SIAM}},
  year         = {2016}
}

@article{DBLP:journals/corr/CyganFGKMPS16,
  author       = {Marek Cygan and
                  Fedor V. Fomin and
                  Alexander Golovnev and
                  Alexander S. Kulikov and
                  Ivan Mihajlin and
                  Jakub Pachocki and
                  Arkadiusz Socala},
  title        = {Tight Lower Bounds on Graph Embedding Problems},
  journal      = {CoRR},
  volume       = {abs/1602.05016},
  year         = {2016}
}

@article{DBLP:journals/mst/DemenkovKMM15,
  author       = {Evgeny Demenkov and
                  Alexander S. Kulikov and
                  Olga Melanich and
                  Ivan Mihajlin},
  title        = {New Lower Bounds on Circuit Size of Multi-output Functions},
  journal      = {Theory Comput. Syst.},
  volume       = {56},
  number       = {4},
  pages        = {630--642},
  year         = {2015}
}

@inproceedings{DBLP:conf/icalp/FominGKM15,
  author       = {Fedor V. Fomin and
                  Alexander Golovnev and
                  Alexander S. Kulikov and
                  Ivan Mihajlin},
  title        = {Lower Bounds for the Graph Homomorphism Problem},
  booktitle    = {{ICALP} {(1)}},
  series       = {Lecture Notes in Computer Science},
  volume       = {9134},
  pages        = {481--493},
  publisher    = {Springer},
  year         = {2015}
}

@article{DBLP:journals/corr/FominGKM15,
  author       = {Fedor V. Fomin and
                  Alexander Golovnev and
                  Alexander S. Kulikov and
                  Ivan Mihajlin},
  title        = {Lower Bounds for the Graph Homomorphism Problem},
  journal      = {CoRR},
  volume       = {abs/1502.05447},
  year         = {2015}
}

@article{DBLP:journals/corr/FominGKM15a,
  author       = {Fedor V. Fomin and
                  Alexander Golovnev and
                  Alexander S. Kulikov and
                  Ivan Mihajlin},
  title        = {Tight Bounds for Subgraph Isomorphism and Graph Homomorphism},
  journal      = {CoRR},
  volume       = {abs/1507.03738},
  year         = {2015}
}

@article{DBLP:journals/eccc/CarmosinoGIMPS15,
  author       = {Marco Carmosino and
                  Jiawei Gao and
                  Russell Impagliazzo and
                  Ivan Mihajlin and
                  Ramamohan Paturi and
                  Stefan Schneider},
  title        = {Nondeterministic extensions of the Strong Exponential Time Hypothesis
                  and consequences for non-reducibility},
  journal      = {Electron. Colloquium Comput. Complex.},
  volume       = {{TR15-148}},
  year         = {2015}
}

@article{DBLP:journals/ipl/GolovnevKM14,
  author       = {Alexander Golovnev and
                  Alexander S. Kulikov and
                  Ivan Mihajlin},
  title        = {Solving {SCS} for bounded length strings in fewer than 2\({}^{\mbox{n}}\)
                  steps},
  journal      = {Inf. Process. Lett.},
  volume       = {114},
  number       = {8},
  pages        = {421--425},
  year         = {2014}
}

@inproceedings{DBLP:conf/icalp/GolovnevKM14,
  author       = {Alexander Golovnev and
                  Alexander S. Kulikov and
                  Ivan Mihajlin},
  title        = {Families with Infants: {A} General Approach to Solve Hard Partition
                  Problems},
  booktitle    = {{ICALP} {(1)}},
  series       = {Lecture Notes in Computer Science},
  volume       = {8572},
  pages        = {551--562},
  publisher    = {Springer},
  year         = {2014}
}

@article{DBLP:journals/corr/GolovnevKM14,
  author       = {Alexander Golovnev and
                  Alexander S. Kulikov and
                  Ivan Mihajlin},
  title        = {Families with infants: speeding up algorithms for NP-hard problems
                  using {FFT}},
  journal      = {CoRR},
  volume       = {abs/1410.2209},
  year         = {2014}
}

@inproceedings{DBLP:conf/cpm/GolovnevKM13,
  author       = {Alexander Golovnev and
                  Alexander S. Kulikov and
                  Ivan Mihajlin},
  title        = {Approximating Shortest Superstring Problem Using de Bruijn Graphs},
  booktitle    = {{CPM}},
  series       = {Lecture Notes in Computer Science},
  volume       = {7922},
  pages        = {120--129},
  publisher    = {Springer},
  year         = {2013}
}

@inproceedings{DBLP:conf/mfcs/GolovnevKM13,
  author       = {Alexander Golovnev and
                  Alexander S. Kulikov and
                  Ivan Mihajlin},
  title        = {Solving 3-Superstring in 3 n/3 Time},
  booktitle    = {{MFCS}},
  series       = {Lecture Notes in Computer Science},
  volume       = {8087},
  pages        = {480--491},
  publisher    = {Springer},
  year         = {2013}
}

@article{DBLP:journals/corr/GolovnevKM13,
  author       = {Alexander Golovnev and
                  Alexander S. Kulikov and
                  Ivan Mihajlin},
  title        = {Families with infants: a general approach to solve hard partition
                  problems},
  journal      = {CoRR},
  volume       = {abs/1311.2456},
  year         = {2013}
}

@inproceedings{DBLP:conf/cie/KulikovMM12,
  author       = {Alexander S. Kulikov and
                  Olga Melanich and
                  Ivan Mihajlin},
  title        = {A 5n - o(n) Lower Bound on the Circuit Size over {U} 2 of a Linear
                  Boolean Function},
  booktitle    = {CiE},
  series       = {Lecture Notes in Computer Science},
  volume       = {7318},
  pages        = {432--439},
  publisher    = {Springer},
  year         = {2012}
}

@inproceedings{DBLP:conf/csr/DemenkovKMM12,
  author       = {Evgeny Demenkov and
                  Alexander S. Kulikov and
                  Ivan Mihajlin and
                  Hiroki Morizumi},
  title        = {Computing All MOD-Functions Simultaneously},
  booktitle    = {{CSR}},
  series       = {Lecture Notes in Computer Science},
  volume       = {7353},
  pages        = {81--88},
  publisher    = {Springer},
  year         = {2012}
}

manage site settings

To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.