Sotabase

Career

· Visiting Professor, National University of Singapore2023–
· Assistant Professor, Georgetown University2020–
· Rabin Postdoctoral Fellow, Harvard University2018–2020
· Postdoctoral Researcher, Columbia University2017–2018
· Research Scientist, Yahoo Research2017–2018
· Ph.D. in Discrete Mathematics, Belarusian Academy of Sciences2012–2015
· PhD in Computer Science, New York University2012–2017
· M.Sc., St. Petersburg Academic University of the Russian Academy of Sciences2010–2012
· Specialist (M.Sc.), Belarusian State University2005–2010

Publications (71)

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
Lecture Notes in Computer Science · 2004
138
cited
Brakedown: Linear-Time and Field-Agnostic SNARKs for R1CS
Annual International Cryptology Conference · 2023
100
cited
A Formal Treatment of Backdoored Pseudorandom Generators
International Conference on the Theory and Application of Cryptographic Techniques · 2015
81
cited
Brakedown: Linear-time and post-quantum SNARKs for R1CS
IACR Cryptology ePrint Archive · 2021
60
cited
A Better-Than-3n Lower Bound for the Circuit Complexity of an Explicit Function
IEEE Annual Symposium on Foundations of Computer Science · 2016
58
cited
On the Quantitative Hardness of CVP
IEEE Annual Symposium on Foundations of Computer Science · 2017
42
cited
Optimal Streaming Approximations for all Boolean Max-2CSPs and Max-ksat
IEEE Annual Symposium on Foundations of Computer Science · 2020
33
cited
AC0[p] Lower Bounds against MCSP via the Coin Problem
Electron. Colloquium Comput. Complex. · 2019
32
cited
Fine-grained hardness of CVP(P) - Everything that we can prove (and nothing else)
ACM-SIAM Symposium on Discrete Algorithms · 2019
30
cited
Range Avoidance for Constant-Depth Circuits: Hardness and Algorithms
Electron. Colloquium Comput. Complex. · 2023
30
cited
Static data structure lower bounds imply rigidity
Electron. Colloquium Comput. Complex. · 2018
29
cited
The Minrank of Random Graphs
IEEE Transactions on Information Theory · 2016
28
cited
Tight Bounds for Graph Homomorphism and Subgraph Isomorphism
ACM-SIAM Symposium on Discrete Algorithms · 2016
26
cited
Tight Lower Bounds on Graph Embedding Problems
Journal of the ACM · 2016
23
cited
Approximating Shortest Superstring Problem Using de Bruijn Graphs
Annual Symposium on Combinatorial Pattern Matching · 2013
22
cited
Circuit Depth Reductions
Electron. Colloquium Comput. Complex. · 2018
21
cited
Linear space streaming lower bounds for approximating CSPs
Electron. Colloquium Comput. Complex. · 2021
21
cited
Data structures meet cryptography: 3SUM with preprocessing
Symposium on the Theory of Computing · 2019
20
cited
A New Algorithm for Parameterized MAX-SAT
International Symposium on Parameterized and Exact Computation · 2012
18
cited
Sketching approximability of all finite CSPs
2021
18
cited
Sotabase