516 citations · 2.7k across the 47 of their papers we have counts for
Showing 2023Show all
2 papers · 1 filter
cs.CC2023
Low-Degree Testing Over Grids
Prashanth Amireddy, Srikanth Srinivasan, Madhu Sudan
We study the question of local testability of low (constant) degree functions from a product domain to a field , where ${S_i} \subseteq…
cs.CC2023
Towards Optimal Depth-Reductions for Algebraic Formulas
Hervé Fournier, Nutan Limaye, Guillaume Malod +2
Classical results of Brent, Kuck and Maruyama (IEEE Trans. Computers 1973) and Brent (JACM 1974) show that any algebraic formula of size s can be converted to one of depth O(log s)…