49 citations · 287 across the 45 of their papers we have counts for
5 papers · 1 filter
Counting Subgraphs in Degenerate Graphs
Suman K. Bera, Lior Gishboliner, Yevgeny Levanzov +2
We consider the problem of counting the number of copies of a fixed graph within an input graph . This is one of the most well-studied algorithmic graph problems, with many…
A Lower Bound for Nonadaptive, One-Sided Error Testing of Unateness of Boolean Functions over the Hypercube
Roksana Baleshzar, Deeparnab Chakrabarty, Ramesh Krishnan S. Pallavoor +2
A Boolean function is unate if, along each coordinate, the function is either nondecreasing or nonincreasing. In this note, we prove that any nonadapt…
Blackbox identity testing for bounded top fanin depth-3 circuits: the field doesn't matter
Nitin Saxena, C. Seshadhri
Let C be a depth-3 circuit with n variables, degree d and top fanin k (called sps(k,d,n) circuits) over base field F. It is a major open problem to design a deterministic polynomia…
From Sylvester-Gallai Configurations to Rank Bounds: Improved Black-box Identity Test for Depth-3 Circuits
Nitin Saxena, C. Seshadhri
We study the problem of identity testing for depth-3 circuits of top fanin k and degree d. We give a new structure theorem for such identities. A direct application of our theorem…
An Almost Optimal Rank Bound for Depth-3 Identities
Nitin Saxena, C. Seshadhri
We show that the rank of a depth-3 circuit (over any field) that is simple, minimal and zero is at most k^3\log d. The previous best rank bound known was 2^{O(k^2)}(\log d)^{k-2} b…