3 citations · 3 across the 2 of their papers we have counts for
5 papers
Karchmer-Wigderson Games for Hazard-free Computation
Christian Ikenmeyer, Balagopal Komarath, Nitin Saurabh
We present a Karchmer-Wigderson game to study the complexity of hazard-free formulas. This new game is both a generalization of the monotone Karchmer-Wigderson game and an analog o…
On the complexity of detecting hazards
Balagopal Komarath, Nitin Saurabh
Detecting and eliminating logic hazards in Boolean circuits is a fundamental problem in logic circuit design. We show that there is no time algorithm…
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…
Lower Bounds for Linear Decision Lists
Arkadev Chattopadhyay, Meena Mahajan, Nikhil Mande +1
We demonstrate a lower bound technique for linear decision lists, which are decision lists where the queries are arbitrary linear threshold functions. We use this technique to prov…
Some Complete and Intermediate Polynomials in Algebraic Complexity Theory
Meena Mahajan, Nitin Saurabh
We provide a list of new natural -intermediate polynomial families, based on basic (combinatorial) -complete problems that are complete under parsimoniou…