On the complexity of partial derivatives

A certain class of incidence matrices

D. H. Gottlieb · 1966

Earlier work this paper cites.

The complexity of computing the permanent

Original

L. G. Valiant · 1979

Earlier work this paper cites.

The complexity of counting cuts and of computing the probability that a graph is connected

J Scott Provan and Michael O Ball · 1983

Earlier work this paper cites.

Lower bounds on arithmetic circuits via partial derivatives

N. Nisan and A. Wigderson · 1996

Earlier work this paper cites.

Communication Complexity

E Kushilevitz and N Nisan · 1997

Earlier work this paper cites.

Approximately counting up to four

Michael Luby and Eric Vigoda · 1997

Earlier work this paper cites.

On Markov chains for independent sets

Martin Dyer and Catherine Greenhill · 2000

Earlier work this paper cites.

The complexity of counting colourings and independent sets in sparse graphs and hypergraphs

Catherine Greenhill · 2000

Cited alongside, same era.

The complexity of counting in sparse, regular, and planar graphs

Salil Vadhan · 2001

Cited alongside, same era.

On counting independent sets in sparse graphs

Martin Dyer, Alan Frieze, and Mark Jerrum · 2002

Cited alongside, same era.

Perturbed identity matrices have high rank: Proof and applications

Noga Alon · 2009

Cited alongside, same era.

Arithmetic circuits: A survey of recent results and open questions

Amir Shpilka and Amir Yehudayoff · 2010

Cited alongside, same era.

Partial derivatives in arithmetic complexity and beyond

Xi Chen, Neeraj Kayal, and Avi Wigderson · 2011

Cited alongside, same era.

Most tensor problems are NP-hard

Christopher J Hillar and Lek-Heng Lim · 2013

Later among the works it cites.

Complexity and algorithms for Euler characteristic of simplicial complexes

Bjarke Hammersholt Roune and Eduardo Sáenz-de Cabezón · 2013

Later among the works it cites.

An exponential lower bound for homogeneous depth four arithmetic formulas

Neeraj Kayal, Nutan Limaye, Chiranjib Saha, and Sudarshan Srinivasan · 2014

Later among the works it cites.

The shifted partial derivative complexity of elementary symmetric polynomials

Hervé Fournier, Nutan Limaye, Meena Mahajan, and Srikanth Srinivasan · 2015

Later among the works it cites.

Lower bounds for depth three arithmetic circuits with small bottom fanin

Neeraj Kayal and Chandan Saha · 2015

Later among the works it cites.

How hard is the tensor rank?

Original