### 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) |
---|---|

Title of host publication | Proceedings - 2013 IEEE Conference on Computational Complexity, CCC 2013 |

Pages | 197-206 |

Number of pages | 10 |

DOIs | |

State | Published - 2013 |

Event | 2013 IEEE Conference on Computational Complexity, CCC 2013 - Palo Alto, CA, United States Duration: Jun 5 2013 → Jun 7 2013 |

### Publication series

Name | Proceedings of the Annual IEEE Conference on Computational Complexity |
---|---|

ISSN (Print) | 1093-0159 |

### Other

Other | 2013 IEEE Conference on Computational Complexity, CCC 2013 |
---|---|

Country | United States |

City | Palo Alto, CA |

Period | 6/5/13 → 6/7/13 |

### All Science Journal Classification (ASJC) codes

- Software
- Theoretical Computer Science
- Computational Mathematics

### Keywords

- U-polynomials
- 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. (2013). On rigid matrices and U-polynomials. In

*Proceedings - 2013 IEEE Conference on Computational Complexity, CCC 2013*(pp. 197-206). [6597762] (Proceedings of the Annual IEEE Conference on Computational Complexity). https://doi.org/10.1109/CCC.2013.28