14 citations · 30 across the 18 of their papers we have counts for
24 papers
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 several parties. The classical setting deals with Boolean inpu…
New and Improved Concrete Lower Bounds for Orthogonal Vectors
Tameem Choudhury, Nutan Limaye, Karteek Sreenivasaiah +1
The Orthogonal Vectors Problem (OV) takes as input two sets each containing -dimensional Boolean vectors, and outputs if and only if there exists …
Hard CNF Instances for Ideal Proof Systems
Tuomas Hakoniemi, Nutan Limaye, Iddo Tzameret
Since the introduction of the Ideal Proof System (IPS) by Grochow and Pitassi (J. ACM 2018), a substantial body of work has established size lower bounds for IPS and its fragments.…
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…
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…
New Bounds for the Ideal Proof System in Positive Characteristic
Amik Raj Behera, Nutan Limaye, Varun Ramanathan +1
In this work, we prove upper and lower bounds over fields of positive characteristics for several fragments of the Ideal Proof System (IPS), an algebraic proof system introduced by…