| 1. |
- Austrin, Per, 1981-, et al.
(författare)
-
Sharper Upper Bounds for Unbalanced Uniquely Decodable Code Pairs
- 2018
-
Ingår i: IEEE Transactions on Information Theory. - : IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC. - 0018-9448 .- 1557-9654. ; 64:2, s. 1368-1373
-
Tidskriftsartikel (refereegranskat)abstract
- Two sets of 0-1 vectors of fixed length form a uniquely decodeable code pair if their Cartesian product is of the same size as their sumset, where the addition is pointwise over integers. For the size of the sumset of such a pair, van Tilborg has given an upper bound in the general case. Urbanke and Li, and later Ordentlich and Shayevitz, have given better bounds in the unbalanced case, that is, when either of the two sets is sufficiently large. Improvements to the latter bounds are presented.
|
|
| 2. |
- Bjorklund, Andreas, et al.
(författare)
-
Fast Zeta Transforms for Lattices with Few Irreducibles
- 2016
-
Ingår i: ACM Transactions on Algorithms. - : Association for Computing Machinery (ACM). - 1549-6325 .- 1549-6333. ; 12:1
-
Tidskriftsartikel (refereegranskat)abstract
- We investigate fast algorithms for changing between the standard basis and an orthogonal basis of idempotents for Mobius algebras of finite lattices. We show that every lattice with v elements, n of which are nonzero and join-irreducible (or, by a dual result, nonzero and meet-irreducible), has arithmetic circuits of size O(vn) for computing the zeta transform and its inverse, thus enabling fast multiplication in the Mobius algebra. Furthermore, the circuit construction in fact gives optimal (up to constants) monotone circuits for several lattices of combinatorial and algebraic relevance, such as the lattice of subsets of a finite set, the lattice of set partitions of a finite set, the lattice of vector subspaces of a finite vector space, and the lattice of positive divisors of a positive integer.
|
|
| 3. |
- Björklund, Andreas, et al.
(författare)
-
Computing the Tutte polynomial in vertex-exponential time
- 2008
-
Ingår i: Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science. - 0272-5428. ; , s. 677-686
-
Konferensbidrag (refereegranskat)abstract
- The deletion-contraction algorithm is perhaps the most popular method for computing a host of fundamental graph invariants such as the chromatic, flow, and reliability polynomials in graph theory, the Jones polynomial of an alternating link in knot theory, and the partition functions of the models of Ising, Potts, and Fortuin-Kasteleyn in statistical physics. Prior to this work, deletion-contraction was also the fastest known general-purpose algorithm for these invariants, running in time roughly proportional to the number of spanning trees in the input graph. Here, we give a substantially faster algorithm that computes the Tutte polynomial-and hence, all the aforementioned invariants and more-of an arbitrary graph in time within a polynomial factor of the number of connected vertex sets. The algorithm actually evaluates a multivariate generalization of the Tutte polynomial by making use of an identity due to Fortuin and Kasteleyn. We also provide a polynomial-space variant of the algorithm and give an analogous result for Chung and Graham's cover polynomial.
|
|
| 4. |
- Björklund, Andreas, et al.
(författare)
-
Counting Connected Subgraphs with Maximum-Degree-Aware Sieving
- 2018
-
Ingår i: 29th International Symposium on Algorithms and Computation (ISAAC 2018). - 9783959770941 ; , s. 1-17
-
Konferensbidrag (refereegranskat)abstract
- We study the problem of counting the isomorphic occurrences of a k-vertex pattern graph P as a subgraph in an n-vertex host graph G. Our specific interest is on algorithms for subgraph counting that are sensitive to the maximum degree Delta of the host graph. Assuming that the pattern graph P is connected and admits a vertex balancer of size b, we present an algorithm that counts the occurrences of P in G in O ((2 Delta-2)^{(k+b)/2} 2^{-b} n/(Delta) k^2 log n) time. We define a balancer as a vertex separator of P that can be represented as an intersection of two equal-size vertex subsets, the union of which is the vertex set of P, and both of which induce connected subgraphs of P. A corollary of our main result is that we can count the number of k-vertex paths in an n-vertex graph in O((2 Delta-2)^{floor[k/2]} n k^2 log n) time, which for all moderately dense graphs with Delta <= n^{1/3} improves on the recent breakthrough work of Curticapean, Dell, and Marx [STOC 2017], who show how to count the isomorphic occurrences of a q-edge pattern graph as a subgraph in an n-vertex host graph in time O(q^q n^{0.17q}) for all large enough q. Another recent result of Brand, Dell, and Husfeldt [STOC 2018] shows that k-vertex paths in a bounded-degree graph can be approximately counted in O(4^kn) time. Our result shows that the exact count can be recovered at least as fast for Delta<10. Our algorithm is based on the principle of inclusion and exclusion, and can be viewed as a sparsity-sensitive version of the "counting in halves"-approach explored by Björklund, Husfeldt, Kaski, and Koivisto [ESA 2009].
|
|
| 5. |
- Björklund, Andreas, et al.
(författare)
-
Counting paths and packings in halves
- 2009
-
Ingår i: Algorithms - ESA 2009, Proceedings/Lecture notes in computer science. - Berlin, Heidelberg : Springer Berlin Heidelberg. - 0302-9743 .- 1611-3349. ; 5757, s. 578-586
-
Konferensbidrag (refereegranskat)abstract
- We show that; one can count k-edge paths in an n-vertex graph and m-set k-packings on an n-element universe, respectively, in time (n k/2) and (n mk/2) up to a factor polynomial in n, k, and in: in polynomial space, the bounds hold if multiplied by 3(k/2) or 5(mk/2), respectively. These are implications of a more general result: given two set families on an n-element universe, one can count the disjoint pairs of sets in the Cartesian product of the two families with O(The) basic operations, where e is the number of members in the two families and their subsets.
|
|
| 6. |
- Björklund, Andreas, et al.
(författare)
-
Covering and packing in linear space
- 2011
-
Ingår i: Information Processing Letters. - : Elsevier BV. - 0020-0190. ; 111:21–22, s. 1033-1036
-
Tidskriftsartikel (refereegranskat)
|
|
| 7. |
- Björklund, Andreas, et al.
(författare)
-
Covering and packing in linear space
- 2010
-
Ingår i: Automata, Languages and Programming /Lecture Notes in Computer Science. - Berlin, Heidelberg : Springer Berlin Heidelberg. ; 6198, s. 727-737
-
Konferensbidrag (refereegranskat)
|
|
| 8. |
- Björklund, Andreas, et al.
(författare)
-
Fast zeta transforms for point lattices
- 2012
-
Ingår i: SODA '12 Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete Algorithms. - Philadelphia, PA : Society for Industrial and Applied Mathematics. - 9781611972108 ; , s. 1436-1444
-
Konferensbidrag (refereegranskat)
|
|
| 9. |
- Björklund, Andreas, et al.
(författare)
-
Fourier meets Möbius: fast subset convolution
- 2007
-
Ingår i: Proceedings of the thirty-ninth annual ACM symposium on Theory of computing. - New York, NY, USA : ACM. - 9781595936318 ; , s. 67-74
-
Konferensbidrag (refereegranskat)abstract
- We present a fast algorithm for the subset convolution problem:given functions f and g defined on the lattice of subsets of ann-element set n, compute their subset convolution f*g, defined for S⊆ N by [ (f * g)(S) = [T ⊆ S] f(T) g(S/T),,]where addition and multiplication is carried out in an arbitrary ring. Via Möbius transform and inversion, our algorithm evaluates the subset convolution in O(n2 2n) additions and multiplications, substanti y improving upon the straightforward O(3n) algorithm. Specifically, if the input functions have aninteger range [-M,-M+1,...,M], their subset convolution over the ordinary sum--product ring can be computed in Õ(2n log M) time; the notation Õ suppresses polylogarithmic factors.Furthermore, using a standard embedding technique we can compute the subset convolution over the max--sum or min--sum semiring in Õ(2n M) time. To demonstrate the applicability of fast subset convolution, wepresent the first Õ(2k n2 + n m) algorithm for the Steiner tree problem in graphs with n vertices, k terminals, and m edges with bounded integer weights, improving upon the Õ(3kn + 2k n2 + n m) time bound of the classical Dreyfus-Wagner algorithm. We also discuss extensions to recent Õ(2n)-time algorithms for covering and partitioning problems (Björklund and Husfeldt, FOCS 2006; Koivisto, FOCS 2006).
|
|
| 10. |
- Björklund, Andreas, et al.
(författare)
-
Narrow sieves for parameterized paths and packings
- 2017
-
Ingår i: Journal of Computer and System Sciences. - : Elsevier BV. - 0022-0000. ; 87, s. 119-139
-
Tidskriftsartikel (refereegranskat)abstract
- We present parameterized algorithms for the k-path problem, the p-packing of q-sets problem, and the q-dimensional p-matching problem. Our algorithms solve these problems with high probability in time exponential only in the parameter (k, p, q) and using polynomial space. The constant bases of the exponentials are significantly smaller than in previous works; for example, for the k-path problem the improvement is from 2 to 1.66. We also show how to detect if a d-regular graph admits an edge coloring with d colors in time within a polynomial factor of 2(d-1)n/2. Our techniques generalize an algebraic approach studied in various recent works.
|
|
