## Abstract

The Direct Product encoding of a string a ∈ {0, 1}^{n} on an underlying domain V ⊆ ^{([n}_{k}^{])}, is a function DP_{V} (a) which gets as input a set S ∈ V and outputs a restricted to S. In the Direct Product Testing Problem, we are given a function F : V → {0, 1}^{k}, and our goal is to test whether F is close to a direct product encoding, i.e., whether there exists some a ∈ {0, 1}^{n} such that on most sets S, we have F(S) = DP_{V} (a)(S). A natural test is as follows: select a pair (S, S^{0}) ∈ V according to some underlying distribution over V × V , query F on this pair, and check for consistency on their intersection. Note that the above distribution may be viewed as a weighted graph over the vertex set V and is referred to as a test graph. The testability of direct products was studied over various domains and test graphs: Dinur and Steurer (CCC’14) analyzed it when V equals the k-th slice of the Boolean hypercube and the test graph is a member of the Johnson graph family. Dinur and Kaufman (FOCS’17) analyzed it for the case where V is the set of faces of a Ramanujan complex, where in this case V = O_{k}(n). In this paper, we study the testability of direct products in a general setting, addressing the question: what properties of the domain and the test graph allow one to prove a direct product testing theorem? Towards this goal we introduce the notion of coordinate expansion of a test graph. Roughly speaking a test graph is a coordinate expander if it has global and local expansion, and has certain nice intersection properties on sampling. We show that whenever the test graph has coordinate expansion then it admits a direct product testing theorem. Additionally, for every k and n we provide a direct product domain V ⊆ ^{(n k)} of size n, called the Sliding Window domain for which we prove direct product testability.

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

Title of host publication | 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2018 |

Editors | Sumit Ganguly, Paritosh Pandya |

Publisher | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |

ISBN (Electronic) | 9783959770934 |

DOIs | |

State | Published - Dec 2018 |

Externally published | Yes |

Event | 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2018 - Ahmedabad, India Duration: Dec 11 2018 → Dec 13 2018 |

### Publication series

Name | Leibniz International Proceedings in Informatics, LIPIcs |
---|---|

Volume | 122 |

ISSN (Print) | 1868-8969 |

### Conference

Conference | 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2018 |
---|---|

Country/Territory | India |

City | Ahmedabad |

Period | 12/11/18 → 12/13/18 |

## All Science Journal Classification (ASJC) codes

- Software

## Keywords

- Derandomization
- Direct product
- Johnson graph
- PCP
- Property testing
- Ramanujan complex