Applications of Random Algebraic Constructions to Hardness of Approximation

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 languageEnglish (US)
Title of host publicationProceedings - 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science, FOCS 2021
PublisherIEEE Computer Society
Pages237-244
Number of pages8
ISBN (Electronic)9781665420556
DOIs
StatePublished - 2022
Event62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021 - Virtual, Online, United States
Duration: Feb 7 2022Feb 10 2022

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
Volume2022-February

Conference

Conference62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021
Country/TerritoryUnited States
CityVirtual, Online
Period2/7/222/10/22

ASJC Scopus subject areas

  • Computer Science(all)

Keywords

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

Fingerprint

Dive into the research topics of 'Applications of Random Algebraic Constructions to Hardness of Approximation'. Together they form a unique fingerprint.

Cite this