193 citations · 549 across the 24 of their papers we have counts for
Showing math.COShow all
2 papers · 1 filter
math.CO2010★ 1 cited
Rank Bounds for Design Matrices with Applications to Combinatorial Geometry and Locally Correctable Codes
Boaz Barak, Zeev Dvir, Avi Wigderson +1
A (q,k,t)-design matrix is an m x n matrix whose pattern of zeros/non-zeros satisfies the following design-like condition: each row has at most q non-zeros, each column has at leas…
math.CO2006
A Simple Explicit Construction of an $n^{\Tilde{O}(\log n)}$-Ramsey Graph
Boaz Barak
We show a simple explicit construction of an $2^{\Tilde{O}(\sqrt{\log n})}$ Ramsey graph. That is, we provide a $\poly(n)$-time algorithm to output the adjacency matrix of an undir…