Farzan Byramji

dblp:334/7566 · DBLP profile ↗
← Back
4ranked-venue papers
2as first author
4since 2021 · last 2026
0000-0001-6154-0463ORCID · verified

Domains — the database's venue-derived domains; a paper can count in several

Theory of computation · 4 · 2 first-author · 4 since 2021
YearPublicationVenuePosition
2026 Quantum-Classical Equivalence for And-Functions
Sreejata Kishor Bhattacharya, Farzan Byramji, Arkadev Chattopadhyay, Yogesh Dahiya, Shachar Lovett
CCC2
2026 Lower Bounds for Near-Quadratic-Depth Resolution over Parities
abstract
Resolution over parities (Res(⊕)) is a proof system introduced by Itsykson and Sokolov [MFCS ’14] as a stepping stone towards proving AC0[2]-Frege lower bounds. A recent line of work has established lower bounds against depth-restricted Res(⊕) refutations. Prior to this work, the state of the art was exponential lower bounds against depth O(N logN) Res(⊕) proved by Efremenko and Itsykson [CCC ’25], where N is the number of variables in the CNF. In this work we prove exponential lower bounds against depth O(N2−є) Res(⊕) refutations. The lifted Tseitin formula we consider has O(N) clauses of width 6, which lets the allowed depth be almost quadratic not only in the number of variables, but also in the CNF size. We also prove depth-restricted lower bounds for variants of the bit pigeonhole principle (BPHP), including an exponential lower bound for depth O(n2−є) Res(⊕) refutations of BPHP with n+1 pigeons and n holes.
Sreejata Kishor Bhattacharya, Farzan Byramji, Arkadev Chattopadhyay, Russell Impagliazzo
STOC2
2025 Lifting to Randomized Parity Decision Trees
Farzan Byramji, Russell Impagliazzo
APPROX/RANDOM1
2024 Relations Between Monotone Complexity Measures Based on Decision Tree Complexity
Farzan Byramji, Vatsal Jha, Chandrima Kayal, Rajat Mittal 0001
COCOON (1)1