Farzan Byramji

I am a third year PhD student in the UCSD theory group, where I am fortunate to be advised by Shachar Lovett and Russell Impagliazzo. Previously, I was a student in the CSE department of IIT Kanpur, where I worked with Rajat Mittal and got a BT-MT dual degree.

My research interests lie broadly in complexity theory and combinatorics. I am particularly interested in questions about propositional proof systems, Boolean circuits, decision trees and communication protocols.

Email: fbyramji at ucsd dot edu

Research

• On the Advantage of Adaptivity for Sampling with Cell Probes
  with Daniel M. Kane, Jackson Morris, and Anthony Ostuni
  Manuscript, 2026
  [arXiv | ECCC]

• Hard-to-Sample Distributions from Robust Extractors
  with Daniel M. Kane, Jackson Morris, and Anthony Ostuni
  Manuscript, 2026
  [arXiv | ECCC]

• Quantum-Classical Equivalence for AND-Functions
  with Sreejata K. Bhattacharya, Arkadev Chattopadhyay, Yogesh Dahiya, and Shachar Lovett
  CCC 2026
  [arXiv | ECCC]

• Lower Bounds for Near-Quadratic-Depth Resolution over Parities
  with Sreejata K. Bhattacharya, Arkadev Chattopadhyay, and Russell Impagliazzo
  STOC 2026
  Merge of the following two papers:
  • Exponential Lower Bounds on the Size of ResLin Proofs of Nearly Quadratic Depth
    Sreejata K. Bhattacharya, Arkadev Chattopadhyay
    [arXiv | ECCC]
  • Lower Bounds for Bit Pigeonhole Principles in Bounded-Depth Resolution over Parities
    Farzan Byramji, Russell Impagliazzo
    [arXiv | ECCC]

• Lifting to Randomized Parity Decision Trees
  with Russell Impagliazzo
  RANDOM 2025
  [ECCC]

• Relations between monotone complexity measures based on decision tree complexity
  with Vatsal Jha, Chandrima Kayal, and Rajat Mittal
  COCOON 2024
  [arXiv | ECCC]

• Query complexity of Boolean functions on slices
  Discrete Mathematics, 2024
  [arXiv]

• A bijection between symmetric valleys in Dyck paths and even degree internal vertices in ordered trees
  INTEGERS, 2022