## Abstract

In this paper, we show how one may (efficiently) construct two types of extremal combinatorial objects whose existence was previously conjectural. •Panchromatic Graphs: For fixed k in N, a k-panchromatic graph is, roughly speaking, a balanced bipartite graph with one partition class equipartitioned into k colour classes in which the common neighbourhoods of panchromatic k-sets of vertices are much larger than those of k-sets that repeat a colour. The question of their existence was raised by Karthik and Manurangsi [Combinatorica 2020]. •Threshold Graphs: For fixed k in N, a k-threshold graph is, roughly speaking, a balanced bipartite graph in which the common neighbourhoods of k-sets of vertices on one side are much larger than those of (k+1)-sets. The question of their existence was raised by Lin [JACM 2018]. Concretely, we provide probability distributions over graphs from which we can efficiently sample these objects in near linear time. These probability distributions are defined via varieties cut out by (carefully chosen) random polynomials, and the analysis of these constructions relies on machinery from algebraic geometry (such as the Lang-Weil estimate, for example). The technical tools developed to accomplish this might be of independent interest. As applications of our constructions, we show the following conditional time lower bounds on the parameterized set intersection problem where, given a collection of n sets over universe [n] and a parameter k, the goal is to find k sets with the largest intersection. •Assuming ETH, for any computable function F:Nrightarrow N, no n o(k)-time algorithm can approximate the parameterized set intersection problem up to factor F(k). This improves considerably on the previously best-known result under ETH due to Lin [JACM 2018], who ruled out any n o(√k}) time approximation algorithm for this problem. •Assuming SETH, for every > 0 and any computable function F:n N, no n k-time algorithm can approximate the parameterized set intersection problem up to factor F(k). No result of comparable strength was previously known under SETH, even for solving this problem exactly. Both these time lower bounds are obtained by composing panchromatic graphs with instances of the coloured variant of the parameterized set intersection problem (for which tight lower bounds were previously known).

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

Title of host publication | Proceedings - 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science, FOCS 2021 |

Publisher | IEEE Computer Society |

Pages | 237-244 |

Number of pages | 8 |

ISBN (Electronic) | 9781665420556 |

DOIs | |

State | Published - 2022 |

Event | 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021 - Virtual, Online, United States Duration: Feb 7 2022 → Feb 10 2022 |

### Publication series

Name | Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS |
---|---|

Volume | 2022-February |

### Conference

Conference | 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021 |
---|---|

Country/Territory | United States |

City | Virtual, Online |

Period | 2/7/22 → 2/10/22 |

## ASJC Scopus subject areas

- Computer Science(all)

## Keywords

- Colour Coding
- Fine-Grained Complexity
- Hardness of Approximation
- Parameterized Complexity
- Random Algebraic Construction