Showing cs.CCShow all
2 papers · 1 filter
cs.CC2025
Recent Advances in Debordering Methods
Pranjal Dutta, Vladimir Lysikov
Border complexity captures functions that can be approximated by low-complexity ones. Debordering is the task of proving an upper bound on some non-border complexity measure in ter…
cs.CC2024
Algebraic metacomplexity and representation theory
Maxim van den Berg, Pranjal Dutta, Fulvio Gesmundo +2
In the algebraic metacomplexity framework we prove that the decomposition of metapolynomials into their isotypic components can be implemented efficiently, namely with only a quasi…