TY - GEN
T1 - Applications of Random Algebraic Constructions to Hardness of Approximation
AU - Bukh, Boris
AU - Karthik, C. S.
AU - Narayanan, Bhargav
N1 - Funding Information: Boris Bukh was supported in part by U.S. taxpayers through NSF CAREER grant DMS-1555149. Karthik C. S. was financially supported by Subhash Khot’s Simons Investigator Award and by a grant from the Simons Foundation, Grant Number 825876, Awardee Thu D. Nguyen. Bhargav Narayanan was supported by NSF grants CCF-1814409 and DMS-1800521. Publisher Copyright: © 2022 IEEE.
PY - 2022
Y1 - 2022
N2 - 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).
AB - 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).
KW - Colour Coding
KW - Fine-Grained Complexity
KW - Hardness of Approximation
KW - Parameterized Complexity
KW - Random Algebraic Construction
UR - http://www.scopus.com/inward/record.url?scp=85127107476&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85127107476&partnerID=8YFLogxK
U2 - https://doi.org/10.1109/FOCS52979.2021.00032
DO - https://doi.org/10.1109/FOCS52979.2021.00032
M3 - Conference contribution
T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
SP - 237
EP - 244
BT - Proceedings - 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science, FOCS 2021
PB - IEEE Computer Society
T2 - 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021
Y2 - 7 February 2022 through 10 February 2022
ER -