Hello!

I am a postdoctoral researcher at the University of Warwick, hosted by Igor Carboni Oliveira.

Previously, I held positions as a postdoctoral researcher at the University of Oxford, hosted by Rahul Santhanam, and as a Research Fellow for the Meta-Complexity program at the Simons Institute for the Theory of Computing. I obtained my Ph.D. from Simon Fraser University, where I was advised by Valentine Kabanets and Andrei Bulatov. I did my Bachelor's in Computer Science at the University of British Columbia.

Research Interests

• Computational Complexity

• Circuit Complexity

• Randomness in Computation

• Meta-Complexity

• Connections between Lower Bounds and Algorithms

Papers

• One-Way Functions and pKt Complexity

[ECCC]

with Shuichi Hirahara and Igor C. Oliveira

TCC 2024




• Optimal Coding for Randomized Kolmogorov Complexity and Its Applications

with Shuichi Hirahara and Mikito Nanashima

FOCS 2024




• On the Complexity of Avoiding Heavy Elements

[ECCC]

with Igor C. Oliveira, Hanlin Ren, and Rahul Santhanam

FOCS 2024




• Exact Search-to-Decision Reductions for Time-Bounded Kolmogorov Complexity

[ECCC]

with Shuichi Hirahara, Valentine Kabanets, and Igor C. Oliveira

CCC 2024




• Impagliazzo's Worlds Through the Lens of Conditional Kolmogorov Complexity

[ECCC]

with Rahul Santhanam

ICALP 2024




• Polynomial-Time Pseudodeterministic Construction of Primes

[ECCC] [Quanta] [Computational Complexity Blog] [Oded's Choices]

with Lijie Chen, Igor C. Oliveira, Hanlin Ren, and Rahul Santhanam

FOCS 2023




• Bounded Relativization

[ECCC]

with Shuichi Hirahara and Hanlin Ren

CCC 2023




• A Duality Between One-Way Functions and Average-Case Symmetry of Information

[ECCC]

with Shuichi Hirahara, Rahul Ilango, Mikito Nanashima, and Igor C. Oliveira

STOC 2023




• Theory and Applications of Probabilistic Kolmogorov Complexity

[ECCC]

with Igor C. Oliveira

The Computational Complexity Column - Bulletin of EATCS No 137, 2022




• Probabilistic Kolmogorov Complexity with Applications to Average-Case Complexity

[ECCC]

with Halley Goldberg, Valentine Kabanets, and Igor C. Oliveira

CCC 2022




• Optimal Coding Theorems in Time-Bounded Kolmogorov Complexity

[arXiv]

with Igor C. Oliveira and Marius Zimand

ICALP 2022




• Algorithms and Lower Bounds for Comparator Circuits from Shrinkage

[ECCC]

with Bruno P. Cavalar

ITCS 2022




• Majority vs. Approximate Linear Sum and Average-Case Complexity below NC1

[ECCC]

with Lijie Chen, Xin Lyu, and Igor C. Oliveira

ICALP 2021




• An Efficient Coding Theorem via Probabilistic Representations and its Applications

[ECCC]

with Igor C. Oliveira

ICALP 2021




• Pseudodeterministic Algorithms and the Structure of Probabilistic Time

[ECCC]

with Igor C. Oliveira and Rahul Santhanam

STOC 2021




• Algorithms and Lower Bounds for De Morgan Formulas of Low-Communication Leaf Gates

[ECCC]

with Valentine Kabanets, Sajin Koroth, Dimitrios Myrisiotis, and Igor C. Oliveira

CCC 2020




• Circuit Lower Bounds for MCSP from Local Pseudorandom Generators

[ECCC]

with Mahdi Cheraghchi, Valentine Kabanets, and Dimitrios Myrisiotis

ICALP 2019




• Satisfiability and Derandomization for Small Polynomial Threshold Circuits

[ECCC]

with Valentine Kabanets

RANDOM 2018




• A Polynomial Restriction Lemma with Applications

[ECCC]

with Valentine Kabanets and Daniel Kane

STOC 2017