Fetching the paper…
Reading the bibliography…
We consider a notion of probabilistic rank and probabilistic sign-rank of a matrix, which measures the extent to which a matrix can be probabilistically represented by low-rank matrices.
Graph-theoretic arguments in low-level complexity
Leslie G. Valiant · 1977
Earlier work this paper cites.
Lower bounds by probabilistic arguments (extended abstract)
Andrew C. Yao · 1983
Earlier work this paper cites.
Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
A. A. Razborov · 1987
Earlier work this paper cites.
Algebraic methods in the theory of lower bounds for Boolean circuit complexity
Roman Smolensky · 1987
Earlier work this paper cites.
Private communication, cited in [ Raz89 ] , 1988
P. Pudlak and P. Savicky · 1988
Earlier work this paper cites.
On rigid matrices (in Russian)
A. A. Razborov · 1989
Earlier work this paper cites.
On the rigidity of an Hadamard matrix
Noga Alon · 1990
Earlier work this paper cites.
Random-self-reducibility of complete sets
Joan Feigenbaum and Lance Fortnow · 1993
Earlier work this paper cites.
A note on matrix rigidity
Joel Friedman · 1993
Earlier work this paper cites.
Threshold circuits of bounded depth
András Hajnal, Wolfgang Maass, Pavel Pudlák, Mario Szegedy, and György Turán · 1993
Earlier work this paper cites.
Probabilistic polynomials, AC0 functions and the polynomial-time hierarchy
Jun Tarui · 1993
Earlier work this paper cites.
A remark on matrix rigidity
M.A. Shokrollahi, D.A. Spielman, and V. Stemann · 1997
Earlier work this paper cites.
Improved lower bounds on the rigidity of Hadamard matrices
B. S. Kashin and A. A. Razborov · 1998
Earlier work this paper cites.
Threshold circuits of small majority-depth
Alexis Maciel and Denis Thérien · 1998
Earlier work this paper cites.
Matrix rigidity
Bruno Codenotti · 2000
Earlier work this paper cites.
On the rigidity of vandermonde matrices
Satyanarayana V. Lokam · 2000
Earlier work this paper cites.
Communication complexity lower bounds by polynomials
Harry Buhrman and Ronald de Wolf · 2001
Earlier work this paper cites.
Relations between communication complexity, linear arrangements, and computational complexity
Jürgen Forster, Matthias Krause, Satyanarayana V. Lokam, Rustam Mubarakzjanov, Niels Schmitt, and Hans Ulrich Simon · 2001
Cited alongside, same era.
Extremal Combinatorics, With Applications in Computer Science
Stasys Jukna · 2001
Cited alongside, same era.
Spectral methods for matrix rigidity with applications to size-depth tradeoffs and communication complexity
Satyanarayana V. Lokam · 2001
Cited alongside, same era.
A linear lower bound on the unbounded error probabilistic communication complexity
Jürgen Forster · 2002
Cited alongside, same era.
The geometry of matrix rigidity
JM Landsberg, J. Taylor, and N.K. Vishnoi · 2003
Cited alongside, same era.
Three lines proof of the lower bound for the matrix rigidity
Gatis Midrijanis · 2005
Candidate weak pseudorandom functions in AC 0 {}^{\mbox{0}} o MOD 2 {}_{\mbox{2}}
Adi Akavia, Andrej Bogdanov, Siyao Guo, Akshay Kamath, and Alon Rosen · 2014
Later among the works it cites.
Using elimination theory to construct rigid matrices
Abhinav Kumar, Satyanarayana V. Lokam, Vijay M. Patankar, and M. N. Jayalal Sarma · 2014
Later among the works it cites.
Exercises on matrix rigidity
Satyanarayana V. Lokam · 2014
Later among the works it cites.
The polynomial method in circuit complexity applied to algorithm design (invited talk)
Richard Ryan Williams · 2014
Later among the works it cites.
Faster all-pairs shortest paths via circuit complexity
Ryan Williams · 2014
Later among the works it cites.
Probabilistic polynomials and hamming nearest neighbors
Josh Alman and Ryan Williams · 2015
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Cited alongside, same era.
Lower bounds on matrix rigidity via a quantum argument
Ronald de Wolf · 2006
Cited alongside, same era.
Quadratic lower bounds on matrix rigidity
Satyanarayana V. Lokam · 2006
Cited alongside, same era.
Algebrization: A new barrier in complexity theory
Scott Aaronson and Avi Wigderson · 2009
Cited alongside, same era.
Complexity lower bounds using linear algebra
Satyanarayana V. Lokam · 2009
Cited alongside, same era.
Learning complexity vs communication complexity
Nathan Linial and Adi Shraibman · 2009
Cited alongside, same era.
Lower bounds for agnostic learning via approximate rank
Adam R Klivans and Alexander A Sherstov · 2010
Cited alongside, same era.
More applications of the polynomial method to algorithm design
Amir Abboud, Richard Ryan Williams, and Huacheng Yu · 2015
Later among the works it cites.
Polynomial representations of threshold functions and algorithmic applications
Josh Alman, Timothy Chan, and Ryan Williams · 2016
Closest in time.
Sign rank versus VC dimension
Noga Alon, Shay Moran, and Amir Yehudayoff · 2016
Closest in time.
ACˆ0 o MOD2 lower bounds for the boolean inner product
Mahdi Cheraghchi, Elena Grigorescu, Brendan Juba, Karl Wimmer, and Ning Xie · 2016
Closest in time.
On the non-rigidity of generating matrices of good codes
Zeev Dvir · 2016
Closest in time.
Zero-information protocols and unambiguity in arthur-merlin communication
Mika Göös, Toniann Pitassi, and Thomas Watson · 2016
Closest in time.
Matrix rigidity of random toeplitz matrices
Oded Goldreich and Avishay Tal · 2016
Closest in time.
Super-linear gate and super-quadratic wire lower bounds for depth-two and depth-three threshold circuits
Daniel M. Kane and Ryan Williams · 2016
Closest in time.
Bounded matrix rigidity and John’s theorem
Cyrus Rashtchian · 2016
Closest in time.
Beating brute force for systems of polynomial equations over finite fields
Daniel Lokshtanov, Ramamohan Paturi, Suguru Tamaki, Ryan Williams, and Huacheng Yu · 2017
Closest in time.