Marcin Pilipczuk ; Manuel Sorge - A Double Exponential Lower Bound for the Distinct Vectors Problem

dmtcs:6072 - Discrete Mathematics & Theoretical Computer Science, September 18, 2020, vol. 22 no. 4 - https://doi.org/10.23638/DMTCS-22-4-7
A Double Exponential Lower Bound for the Distinct Vectors Problem

Authors: Marcin Pilipczuk ; Manuel Sorge

    In the (binary) Distinct Vectors problem we are given a binary matrix A with pairwise different rows and want to select at most k columns such that, restricting the matrix to these columns, all rows are still pairwise different. A result by Froese et al. [JCSS] implies a 2^2^(O(k)) * poly(|A|)-time brute-force algorithm for Distinct Vectors. We show that this running time bound is essentially optimal by showing that there is a constant c such that the existence of an algorithm solving Distinct Vectors with running time 2^(O(2^(ck))) * poly(|A|) would contradict the Exponential Time Hypothesis.


    Volume: vol. 22 no. 4
    Section: Discrete Algorithms
    Published on: September 18, 2020
    Accepted on: September 2, 2020
    Submitted on: February 5, 2020
    Keywords: Computer Science - Computational Complexity,Computer Science - Discrete Mathematics
    Funding:
      Source : OpenAIRE Graph
    • Cuts and decompositions: algorithms and combinatorial properties; Funder: European Commission; Code: 714704

    Linked publications - datasets - softwares

    Source : ScholeXplorer HasVersion DOI 10.48550/arxiv.2002.01293
    • 10.48550/arxiv.2002.01293
    A Double Exponential Lower Bound for the Distinct Vectors Problem
    Pilipczuk, Marcin ; Sorge, Manuel ;

    Consultation statistics

    This page has been seen 358 times.
    This article's PDF has been downloaded 147 times.