Data Structures And Algorithms

---

Better Sample -- Random Subset Sum in and its Impact on Decoding Random Linear Codes (1907.04295v1)

Andre Esser, Alexander May

2019-07-09

We propose a new heuristic algorithm for solving random subset sum instances , which play a crucial role in cryptographic constructions. Our algorithm is search tree-based and solves the instances in a divide-and-conquer method using the representation method. From a high level perspective, our algorithm is similar to the algorithm of Howgrave-Graham-Joux (HGJ) and Becker-Coron-Joux (BCJ), but instead of enumerating the initial lists we sample candidate solutions. So whereas HGJ and BCJ are based on combinatorics, our analysis is stochastic. Our sampling technique introduces variance that increases the amount of representations and gives our algorithm more optimization flexibility. This results in the remarkable and natural property that we improve with increasing search tree depth. Whereas BCJ achieves the currently best known (heuristic) run time for random subset sum, we improve (heuristically) down to using a search tree of depth at least . We also apply our subset algorithm to the decoding of random binary linear codes, where we improve the best known run time of the Becker-Joux-May-Meurer algorithm from in the half distance decoding setting down to .

Multiple Knapsack-Constrained Monotone DR-Submodular Maximization on Distributive Lattice --- Continuous Greedy Algorithm on Median Complex --- (1907.04279v1)

Takanori Maehara, So Nakashima, Yutaro Yamaguchi

2019-07-09

We consider a problem of maximizing a monotone DR-submodular function under multiple order-consistent knapsack constraints on a distributive lattice. Since a distributive lattice is used to represent a dependency constraint, the problem can represent a dependency constrained version of a submodular maximization problem on a set. We propose a approximation algorithm for this problem. To achieve this result, we generalize the continuous greedy algorithm to distributive lattices: We choose a median complex as a continuous relaxation of a distributive lattice and define the multilinear extension on it. We show that the median complex admits special curves, named uniform linear motions, such that the multilinear extension of a DR-submodular function is concave along a positive uniform linear motion, which is a key property of the continuous greedy algorithm.

Reconstruction under outliers for Fourier-sparse functions (1907.04274v1)

Xue Chen, Anindya De

2019-07-09

We consider the problem of learning an unknown with a sparse Fourier spectrum in the presence of outlier noise. In particular, the algorithm has access to a noisy oracle for (an unknown) such that (i) the Fourier spectrum of is -sparse; (ii) at any query point , the oracle returns such that with probability , . However, with probability , the error can be arbitrarily large. We study Fourier sparse functions over both the discrete cube and the torus and for both these domains, we design efficient algorithms which can tolerate any fraction of outliers. We note that the analogous problem for low-degree polynomials has recently been studied in several works~[AK03, GZ16, KKP17] and similar algorithmic guarantees are known in that setting. While our main results pertain to the case where the location of the outliers, i.e., such that is randomly distributed, we also study the case where the outliers are adversarially located. In particular, we show that over the torus, assuming that the Fourier transform satisfies a certain \emph{granularity} condition, there is a sample efficient algorithm to tolerate fraction of outliers and further, that this is not possible without such a granularity condition. Finally, while not the principal thrust, our techniques also allow us non-trivially improve on learning low-degree functions on the hypercube in the presence of adversarial outlier noise. Our techniques combine a diverse array of tools from compressive sensing, sparse Fourier transform, chaining arguments and complex analysis.

Constant Amortized Time Enumeration of Independent Sets for Graphs with Bounded Clique Number (1906.09680v2)

Kazuhiro Kurita, Kunihiro Wasa, Hiroki Arimura, Takeaki Uno

2019-06-24

In this study, we address the independent set enumeration problem. Although several efficient enumeration algorithms and careful analyses have been proposed for maximal independent sets, no fine-grained analysis has been given for the non-maximal variant. From the main result, we propose an algorithm for the non-maximal variant that runs in amortized time and linear space, where is the clique number, i.e., the maximum size of a clique in an input graph. Note that works correctly even if the exact value of is unknown. Despite its simplicity, is optimal for graphs with a bounded clique number, such as, triangle-free graphs, planar graphs, bounded degenerate graphs, locally bounded expansion graphs, and -free graphs for any fixed graph , where a -free graph is a graph that has no copy of as a subgraph.

Linear MIM-Width of Trees (1907.04132v1)

Svein Høgemo, Jan Arne Telle, Erlend Raa Vågset

2019-07-09

We provide an algorithm computing the linear maximum induced matching width of a tree and an optimal layout.

-Gather Clustering and -Gathering on Spider: FPT Algorithms and Hardness (1907.04088v1)

Soh Kumabe, Takanori Maehara

2019-07-09

We consider min-max -gather clustering problem and min-max -gathering problem. In the min-max -gather clustering problem, we are given a set of users and divide them into clusters with size at least ; the goal is to minimize the maximum diameter of clusters. In the min-max -gathering problem, we are additionally given a set of facilities and assign each cluster to a facility; the goal is to minimize the maximum distance between the users and the assigned facility. In this study, we consider the case that the users and facilities are located on a ``spider'' and propose the first fixed-parameter tractable (FPT) algorithms for both problems, which are parametrized by only the number of legs. Furthermore, we prove that these problems are NP-hard when the number of legs is arbitrarily large.

PTAS and Exact Algorithms for -Gathering Problems on Tree (1907.04087v1)

Soh Kumabe, Takanori Maehara

2019-07-09

r-gathering problem is a variant of facility location problems. In this problem, we are given a set of users and a set of facilities on same metric space. We open some of the facilities and assign each user to an open facility, so that at least r users are assigned to every open facility. We aim to minimize the maximum distance between user and assigned facility. In general, this problem is NP-hard and admit an approximation algorithm with factor 3. It is known that the problem does not admit any approximation algorithm within a factor less than 3. In our another paper, we proved that this problem is NP-hard even on spider, which is a special case of tree metric. In this paper, we concentrate on the problems on a tree. First, we give a PTAS for r-gathering problem on a tree. Furthermore, we give PTAS for some variants of the problems on a tree, and also give exact polynomial-time algorithms for another variants of r-gathering problem on a tree.

Stochastic Monotone Submodular Maximization with Queries (1907.04083v1)

Takanori Maehara, Yutaro Yamaguchi

2019-07-09

We study a stochastic variant of monotone submodular maximization problem as follows. We are given a monotone submodular function as an objective function and a feasible domain defined on a finite set, and our goal is to find a feasible solution that maximizes the objective function. A special part of the problem is that each element in the finite set has a random hidden state, active or inactive, only the active elements contribute to the objective value, and we can conduct a query to an element to reveal its hidden state. The goal is to obtain a feasible solution having a large objective value by conducting a small number of queries. This is the first attempt to consider nonlinear objective functions in such a stochastic model. We prove that the problem admits a good query strategy if the feasible domain has a uniform exchange property. This result generalizes Blum et al.'s result on the unweighted matching problem and Behnezhad and Reyhani's result on the weighted matching problem in both objective function and feasible domain.

Trustworthy Graph Algorithms (1907.04065v1)

Mohammad Abdulaziz, Kurt Mehlhorn, Tobias Nipkow

2019-07-09

The goal of the LEDA project was to build an easy-to-use and extendable library of correct and efficient data structures, graph algorithms and geometric algorithms. We report on the use of formal program verification to achieve an even higher level of trustworthiness. Specifically, we report on an ongoing and largely finished verification of the blossom-shrinking algorithm for maximum cardinality matching.

Complexity of planar signed graph homomorphisms to cycles (1907.03266v2)

François Dross, Florent Foucaud, Valia Mitsou, Pascal Ochem, Théo Pierron

2019-07-07

We study homomorphism problems of signed graphs. A signed graph is an undirected graph where each edge is given a sign, positive or negative. An important concept for signed graphs is the operation of switching at a vertex, which is to change the sign of each incident edge. A homomorphism of a graph is a vertex-mapping that preserves the adjacencies; in the case of signed graphs, we also preserve the edge-signs. Special homomorphisms of signed graphs, called s-homomorphisms, have been studied. In an s-homomorphism, we allow, before the mapping, to perform any number of switchings on the source signed graph. This concept has been extensively studied, and a full complexity classification (polynomial or NP-complete) for s-homomorphism to a fixed target signed graph has recently been obtained. Such a dichotomy is not known when we restrict the input graph to be planar (not even for non-signed graph homomorphisms). We show that deciding whether a (non-signed) planar graph admits a homomorphism to the square of a cycle with , or to the circular clique with , are NP-complete problems. We use these results to show that deciding whether a planar signed graph admits an s-homomorphism to an unbalanced even cycle is NP-complete. (A cycle is unbalanced if it has an odd number of negative edges). We deduce a complete complexity dichotomy for the planar s-homomorphism problem with any signed cycle as a target. We also study further restrictions involving the maximum degree and the girth of the input signed graph. We prove that planar s-homomorphism problems to signed cycles remain NP-complete even for inputs of maximum degree~ (except for the case of unbalanced -cycles, for which we show this for maximum degree~). We also show that for a given integer , the problem for signed bipartite planar inputs of girth is either trivial or NP-complete.

---