Sotabase

Career

· Associate Professor, University of Warwick2019–
· Researcher, UC Berkeley, Simons Institute for the Theory of Computing2017–2018
· Postdoctoral Researcher, University of Oxford2017–2019
· Postdoctoral Researcher, Charles University in Prague2016–2017
· Teaching Assistant, Columbia University2011–2013
· PhD in Computer Science, Columbia University2010–2015
· Master's Degree in Computer Science, University of Campinas2008–2010
· Teaching Assistant, University of Campinas2008–

Publications (0)

Conspiracies between Learning Algorithms, Circuit Lower Bounds and Pseudorandomness
Cybersecurity and Cyberforensics Conference · 2016
74
cited
Hardness Magnification for Natural Problems
IEEE Annual Symposium on Foundations of Computer Science · 2018
57
cited
NP-hardness of circuit minimization for multi-output functions
Electron. Colloquium Comput. Complex. · 2020
53
cited
Hardness magnification near state-of-the-art lower bounds
Electron. Colloquium Comput. Complex. · 2019
52
cited
Beyond Natural Proofs: Hardness Magnification and Locality
Electron. Colloquium Comput. Complex. · 2019
46
cited
Unprovability of circuit upper bounds in Cook's theory PV
Electron. Colloquium Comput. Complex. · 2016
45
cited
Pseudodeterministic constructions in subexponential time
Symposium on the Theory of Computing · 2016
44
cited
NP-hardness of Minimum Circuit Size Problem for OR-AND-MOD Circuits
Electron. Colloquium Comput. Complex. · 2018
34
cited
Randomness and Intractability in Kolmogorov Complexity
Electron. Colloquium Comput. Complex. · 2019
34
cited
Learning circuits with few negations
Electron. Colloquium Comput. Complex. · 2014
33
cited
The Power of Negations in Cryptography
Theory of Cryptography Conference · 2015
29
cited
Pseudodeterministic algorithms and the structure of probabilistic time
Empirical Software Engineering · 2021
28
cited
Algorithms versus Circuit Lower Bounds
Electron. Colloquium Comput. Complex. · 2013
26
cited
Constructing Hard Functions Using Learning Algorithms
2013 IEEE Conference on Computational Complexity · 2013
26
cited
Optimal Coding Theorems in Time-Bounded Kolmogorov Complexity
International Colloquium on Automata, Languages and Programming · 2022
24
cited
Probabilistic Kolmogorov complexity with applications to average-case complexity
Electron. Colloquium Comput. Complex. · 2022
24
cited
Near-optimal small-depth lower bounds for small distance connectivity
Symposium on the Theory of Computing · 2015
22
cited
An Average-Case Lower Bound against ACC 0
2017
19
cited
An Efficient Coding Theorem via Probabilistic Representations and its Applications
Empirical Software Engineering · 2021
17
cited
Parity helps to compute majority
Electron. Colloquium Comput. Complex. · 2019
16
cited
Sotabase