7 citations · 25 across the 10 of their papers we have counts for
14 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…
On (Simple) Decision Tree Rank
Yogesh Dahiya, Meena Mahajan
In the decision tree computation model for Boolean functions, the depth corresponds to query complexity, and size corresponds to storage space. The depth measure is the most well-s…
QBF Merge Resolution is powerful but unnatural
Meena Mahajan, Gaurav Sood
The Merge Resolution proof system (M-Res) for QBFs, proposed by Beyersdorff et al. in 2019, explicitly builds partial strategies inside refutations. The original motivation for thi…
Hard QBFs for Merge Resolution
Olaf Beyersdorff, Joshua Blinkhorn, Meena Mahajan +2
We prove the first genuine QBF proof size lower bounds for the proof system Merge Resolution (MRes [Olaf Beyersdorff et al., 2020]), a refutational proof system for prenex quantifi…
MaxSAT Resolution and Subcube Sums
Yuval Filmus, Meena Mahajan, Gaurav Sood +1
We study the MaxRes rule in the context of certifying unsatisfiability. We show that it can be exponentially more powerful than tree-like resolution, and when augmented with weaken…
Algebraic Branching Programs, Border Complexity, and Tangent Spaces
Markus Bläser, Christian Ikenmeyer, Meena Mahajan +2
Nisan showed in 1991 that the width of a smallest noncommutative single-(source,sink) algebraic branching program (ABP) to compute a noncommutative polynomial is given by the ranks…