565 citations · 2.3k across the 68 of their papers we have counts for
Showing cs.CCShow all
2 papers · 1 filter
cs.CC2022★ 2 cited
The Parallelism Tradeoff: Limitations of Log-Precision Transformers
William Merrill, Ashish Sabharwal
Despite their omnipresence in modern NLP, characterizing the computational power of transformer neural nets remains an interesting open question. We prove that transformers whose a…
cs.CC2015★ 12 cited
Closing the Gap Between Short and Long XORs for Model Counting
Shengjia Zhao, Sorathan Chaturapruek, Ashish Sabharwal +1
Many recent algorithms for approximate model counting are based on a reduction to combinatorial searches over random subsets of the space defined by parity or XOR constraints. Long…