4 papers
Query Complexity of Testing Structured Parenthesis Languages
Tim Jackman, Diptaksho Palit, Sofya Raskhodnikova
We study the query complexity of testing membership in structured string languages, focusing on Dyck languages and natural generalizations. A tester receives query access to a word…
Constructive Separations from Gate Elimination
Marco Carmosino, Ngu Dang, Tim Jackman
Gate elimination is the primary technique for proving explicit lower bounds against general Boolean circuits, including Li and Yang's state-of-the-art bound for affin…
Convergent Gate Elimination and Constructive Circuit Lower Bounds
Marco Carmosino, Ngu Dang, Tim Jackman
Towards better understanding of gate elimination, the only method known that can prove complexity lower bounds for explicit functions against unrestricted Boolean circuits, this wo…
Simple Circuit Extensions for XOR in PTIME
Marco Carmosino, Ngu Dang, Tim Jackman
The Minimum Circuit Size Problem for Partial Functions () is hard assuming the Exponential Time Hypothesis (ETH) (Ilango, 2020). This breakthrough hardness result leveraged…