21 citations · 31 across the 5 of their papers we have counts for
Showing cs.CCShow all
3 papers · 1 filter
cs.CC2022
On the Number of Quantifiers as a Complexity Measure
Ronald Fagin, Jonathan Lenchner, Nikhil Vyas +1
In 1981, Neil Immerman described a two-player game, which he called the "separability game" \cite{Immerman81}, that captures the number of quantifiers needed to describe a property…
cs.CC2020★ 2 cited
Lower Bounds Against Sparse Symmetric Functions of ACC Circuits: Expanding the Reach of SAT Algorithms
Nikhil Vyas, Ryan Williams
We continue the program of proving circuit lower bounds via circuit satisfiability algorithms. So far, this program has yielded several concrete results, proving that functions in…
cs.CC2019
Imperfect Gaps in Gap-ETH and PCPs
Mitali Bafna, Nikhil Vyas
We study the role of perfect completeness in probabilistically checkable proof systems (PCPs) and give a new way to transform a PCP with imperfect completeness to a PCP with perfec…