### Abstract

We introduce a class of polynomials, which we call U-polynomials, and show that the problem of explicitly constructing a rigid matrix can be reduced to the problem of explicitly constructing a small hitting set for this class. We prove that small-bias sets are hitting sets for the class of U-polynomials, though their size is larger than desired. Furthermore, we give two alternative proofs for the fact that small-bias sets induce rigid matrices. Finally, we construct rigid matrices from unbalanced expanders, with essentially the same size as the construction via small-bias sets.

Original language | English (US) |
---|---|

Pages (from-to) | 851-879 |

Number of pages | 29 |

Journal | Computational Complexity |

Volume | 24 |

Issue number | 4 |

DOIs | |

State | Published - Dec 1 2015 |

### All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Mathematics(all)
- Computational Theory and Mathematics
- Computational Mathematics

### Keywords

- Matrix rigidity
- small-bias sets
- unbalanced expanders

## Fingerprint Dive into the research topics of 'On Rigid Matrices and U-Polynomials'. Together they form a unique fingerprint.

## Cite this

Alon, N., & Cohen, G. (2015). On Rigid Matrices and U-Polynomials.

*Computational Complexity*,*24*(4), 851-879. https://doi.org/10.1007/s00037-015-0112-9