Gleb Posobin

Publication Activity (10 Years)

Years Active: 2017-2020
Publications (10 Years): 7

Top Topics

Kolmogorov Complexity

Top Venues

Electron. Colloquium Comput. Complex.

Publications

Alexander Golovnev, Gleb Posobin, Oded Regev, Omri Weinstein
Polynomial Data Structure Lower Bounds in the Group Model. Electron. Colloquium Comput. Complex. 27 (2020)
Alexander Golovnev, Gleb Posobin, Oded Regev, Omri Weinstein
Polynomial Data Structure Lower Bounds in the Group Model. FOCS (2020)
Gleb Posobin, Alexander Shen
Random Noise Increases Kolmogorov Complexity and Hausdorff Dimension. STACS (2019)
Mikhail Andreev, Gleb Posobin, Alexander Shen
Plain Stopping Time and Conditional Complexities Revisited. MFCS (2018)
Gleb Posobin, Alexander Shen
Random noise increases Kolmogorov complexity and Hausdorff dimension. CoRR (2018)
Gleb Posobin
Computing majority with low-fan-in majority queries. CoRR (2017)
Mikhail Andreev, Gleb Posobin, Alexander Shen
Plain stopping time and conditional complexities revisited. CoRR (2017)