Ivan Mihajlin

Available identifiers

zbMath Open mihajlin.ivanMaRDI QIDQ2354590

List of research outcomes

Publication	Date of Publication	Type
Computations with polynomial evaluation oracle: ruling out superlinear SETH-based lower bounds	2024-11-28	Paper
CNF encodings of symmetric functions	2024-11-12	Paper
Super-cubic lower bound for generalized Karchmer-Wigderson games	2024-09-11	Paper
CNF encodings of parity	2024-08-06	Paper
A better-than-\(3\log(n)\) Depth lower bound for De Morgan formulas with restrictions on top gates	2024-07-05	Paper
If Edge Coloring is hard under SETH, then SETH is false	2024-05-29	Paper
Polynomial formulations as a barrier for reduction-based hardness proofs	2024-05-14	Paper
https://portal.mardi4nfdi.de/entity/Q6075924	2023-09-20	Paper
Toward better depth lower bounds: the XOR-KRW conjecture	2023-07-12	Paper
Collapsing Superstring Conjecture	2023-02-03	Paper
https://portal.mardi4nfdi.de/entity/Q5091000	2022-07-21	Paper
Computation of Hadwiger Number and Related Contraction Problems	2022-03-22	Paper
https://portal.mardi4nfdi.de/entity/Q5121900	2020-09-22	Paper
Families with Infants	2018-11-05	Paper
Tight Bounds for Graph Homomorphism and Subgraph Isomorphism	2018-07-16	Paper
Tight Lower Bounds on Graph Embedding Problems	2018-05-17	Paper
Nondeterministic extensions of the strong exponential time hypothesis and consequences for non-reducibility	2016-04-15	Paper
Lower Bounds for the Graph Homomorphism Problem	2015-10-27	Paper
New lower bounds on circuit size of multi-output functions	2015-07-20	Paper
Families with Infants: A General Approach to Solve Hard Partition Problems	2014-07-01	Paper
Solving SCS for bounded length strings in fewer than \(2^n\) steps	2014-04-30	Paper
Solving 3-Superstring in 3 n/3 Time	2013-09-20	Paper
Approximating Shortest Superstring Problem Using de Bruijn Graphs	2013-06-14	Paper
Computing All MOD-Functions Simultaneously	2012-09-10	Paper
A 5n − o(n) Lower Bound on the Circuit Size over U 2 of a Linear Boolean Function	2012-08-14	Paper

Research outcomes over time

This page was built for person: Ivan Mihajlin