3 papers
cs.CC2026
Tight Lower Bounds for Algebraic Communication and Applications
Manon Blanc, Prateek Dwivedi, Magnus Rahbek Dalgaard Hansen +2
Communication complexity studies how much information must be exchanged to solve a problem whose input is split among two or more parties. In this work, we study an algebraic varia…
cs.CC2026
Separation Results for Constant-Depth and Multilinear Ideal Proof Systems
Amik Raj Behera, Magnus Rahbek Dalgaard Hansen, Nutan Limaye +1
In this work, we establish separation theorems for several subsystems of the Ideal Proof System (IPS), an algebraic proof system introduced by Grochow and Pitassi (J. ACM, 2018). S…
cs.CC2025
On Closure Properties of Read-Once Oblivious Algebraic Branching Programs
Jules Armand, Prateek Dwivedi, Magnus Rahbek Dalgaard Hansen +3
We investigate the closure properties of read-once oblivious Algebraic Branching Programs (roABPs) under various natural algebraic operations and prove the following. - Non-closure…