| 1. |
- Kurasov, Pavel
(författare)
-
Can One Distinguish Quantum Trees From The Boundary?
- 2012
-
Ingår i: Proceedings of the American Mathematical Society. - 1088-6826 .- 0002-9939. ; 140:7, s. 2347-2356
-
Tidskriftsartikel (refereegranskat)abstract
- Schrodinger operators on metric trees are considered. It is proven that for certain matching conditions the Titchmarsh-Weyl matrix function does not determine the underlying metric tree; i.e. there exist quantum trees with equal Titchmarsh-Weyl functions. The constructed trees form one-parameter families of isospectral and isoscattering graphs.
|
|
| 2. |
- Böiers, Lars-Christer
(författare)
-
Diskret matematik
- 2003
-
Bok (övrigt vetenskapligt/konstnärligt)
|
|
| 3. |
- Danielsson, Joel Larsson, et al.
(författare)
-
Polarised random κ-SAT
- 2023
-
Ingår i: Combinatorics, probability & computing. - : Cambridge University Press. - 0963-5483 .- 1469-2163. ; 32:6, s. 885-899
-
Tidskriftsartikel (refereegranskat)abstract
- In this paper we study a variation of the random κ-SAT problem, called polarised random κ-SAT, which contains both the classical random κ-SAT model and the random version of monotone κ-SAT another well-known NP-complete version of SAT. In this model there is a polarisation parameter p, and in half of the clauses each variable occurs negated with probability p and pure otherwise, while in the other half the probabilities are interchanged. For p = 1/2 we get the classical random κ-SAT model, and at the other extreme we have the fully polarised model where p = 0, or 1. Here there are only two types of clauses: clauses where all κ variables occur pure, and clauses where all κ variables occur negated. That is, for p = 0, and p=1, we get an instance of random monotone κ-SAT. We show that the threshold of satisfiability does not decrease as p moves away from 1/2 and thus that the satisfiability threshold for polarised random κ-SAT with p ≠ 1/2 is an upper bound on the threshold for random κ-SAT. Hence the satisfiability threshold for random monotone κ-SAT is at least as large as for random κ-SAT, and we conjecture that asymptotically, for a fixed κ, the two thresholds coincide.
|
|
| 4. |
- Danielsson, Joel, et al.
(författare)
-
Polarised random k-SAT
- 2022
-
Annan publikation (övrigt vetenskapligt/konstnärligt)abstract
- In this paper we study a variation of the random k-SAT problem, called polarized random k-SAT. In this model there is a polarization parameter p, and in half of the clauses each variable occurs negated with probability p and pure otherwise, while in the other half the probabilities are interchanged. For p=1/2 we get the classical random k-SAT model, and at the other extreme we have the fully polarized model where p=0, or 1. Here there are only two types of clauses: clauses where all k variables occur pure, and clauses where all k variables occur negated. That is, for p=0 we get an instance of random monotone k-SAT. We show that the threshold of satisfiability does not decrease as p moves away from 1/2 and thus that the satisfiability threshold for polarized random k-SAT is an upper bound on the threshold for random k-SAT. In fact, we conjecture that asymptotically the two thresholds coincide.
|
|
| 5. |
- Federico, Lorenzo, et al.
(författare)
-
Minimal H-factors and covers
- 2023
-
Annan publikation (övrigt vetenskapligt/konstnärligt)abstract
- Given a fixed small graph H and a larger graph G, an H-factor is a collection of vertex-disjoint subgraphs H′⊂G, each isomorphic to H, that cover the vertices of G. If G is the complete graph Kn equipped with independent U(0,1) edge weights, what is the lowest total weight of an H-factor? This problem has previously been considered for e.g. H=K2. We show that if H contains a cycle, then the minimum weight is sharply concentrated around some Ln=Θ(n^(1−1/d∗)) (where d∗ is the maximum 1-density of any subgraph of H). Some of our results also hold for H-covers, where the copies of H are not required to be vertex-disjoint.
|
|
| 6. |
|
|
| 7. |
- Atserias, Albert, et al.
(författare)
-
Clique Is Hard on Average for Regular Resolution
- 2021
-
Ingår i: Journal of the ACM. - : Association for Computing Machinery (ACM). - 0004-5411 .- 1557-735X. ; 68:4, s. 1-26
-
Tidskriftsartikel (refereegranskat)abstract
- We prove that for k ≫; 4√n regular resolution requires length nω(k) to establish that an ErdÅ's-Rényi graph with appropriately chosen edge density does not contain a k-clique. This lower bound is optimal up to the multiplicative constant in the exponent and also implies unconditional nω(k) lower bounds on running time for several state-of-the-art algorithms for finding maximum cliques in graphs.
|
|
| 8. |
|
|
| 9. |
- Björklund, Andreas, et al.
(författare)
-
A faster hafnian formula for complex matrices and its benchmarking on a supercomputer
- 2019
-
Ingår i: ACM Journal of Experimental Algorithmics. - : Association for Computing Machinery (ACM). - 1084-6654. ; 24:1
-
Tidskriftsartikel (refereegranskat)abstract
- We introduce new and simple algorithms for the calculation of the number of perfect matchings of complex weighted, undirected graphs with and without loops. Our compact formulas for the hafnian and loop hafnian of n × n complex matrices run in O(n32n/2) time, are embarrassingly parallelizable and, to the best of our knowledge, are the fastest exact algorithms to compute these quantities. Despite our highly optimized algorithm, numerical benchmarks on the Titan supercomputer with matrices up to size 56 × 56 indicate that one would require the 288,000 CPUs of this machine for about 6 weeks to compute the hafnian of a 100 × 100 matrix.
|
|
| 10. |
- Björklund, Andreas, et al.
(författare)
-
Approximate counting of K-paths : Deterministic and in polynomial space
- 2019
-
Ingår i: 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019. - 9783959771092 ; 132
-
Konferensbidrag (refereegranskat)abstract
- A few years ago, Alon et al. [ISMB 2008] gave a simple randomized O((2e)km∊−2)-time exponential-space algorithm to approximately compute the number of paths on k vertices in a graph G up to a multiplicative error of 1 ± ∊. Shortly afterwards, Alon and Gutner [IWPEC 2009, TALG 2010] gave a deterministic exponential-space algorithm with running time (2e)k+O(log3 k)m log n whenever ∊−1 = kO(1). Recently, Brand et al. [STOC 2018] provided a speed-up at the cost of reintroducing randomization. Specifically, they gave a randomized O(4km∊−2)-time exponential-space algorithm. In this article, we revisit the algorithm by Alon and Gutner. We modify the foundation of their work, and with a novel twist, obtain the following results. We present a deterministic 4k+O(√k(log2 k+log2 ∊−1))m log n-time polynomial-space algorithm. This matches the running time of the best known deterministic polynomial-space algorithm for deciding whether a given graph G has a path on k vertices. Additionally, we present a randomized 4k+O(log k(log k+log ∊−1))m log n-time polynomial-space algorithm. While Brand et al. make non-trivial use of exterior algebra, our algorithm is very simple; we only make elementary use of the probabilistic method. Thus, the algorithm by Brand et al. runs in time 4k+o(k)m whenever ∊−1 = 2o(k), while our deterministic and randomized algorithms run in time 4k+o(k)m log n whenever ∊−1 = 2o(k 4 ) and 1 ∊−1 = 2o(log k k ), respectively. Prior to our work, no 2O(k)nO(1)-time polynomial-space algorithm was known. Additionally, our approach is embeddable in the classic framework of divide-and-color, hence it immediately extends to approximate counting of graphs of bounded treewidth; in comparison, Brand et al. note that their approach is limited to graphs of bounded pathwidth.
|
|
