Change search
Refine search result
1 - 23 of 23
CiteExportLink to result list
Permanent link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Rows per page
  • 5
  • 10
  • 20
  • 50
  • 100
  • 250
Sort
  • Standard (Relevance)
  • Author A-Ö
  • Author Ö-A
  • Title A-Ö
  • Title Ö-A
  • Publication type A-Ö
  • Publication type Ö-A
  • Issued (Oldest first)
  • Issued (Newest first)
  • Created (Oldest first)
  • Created (Newest first)
  • Last updated (Oldest first)
  • Last updated (Newest first)
  • Disputation date (earliest first)
  • Disputation date (latest first)
  • Standard (Relevance)
  • Author A-Ö
  • Author Ö-A
  • Title A-Ö
  • Title Ö-A
  • Publication type A-Ö
  • Publication type Ö-A
  • Issued (Oldest first)
  • Issued (Newest first)
  • Created (Oldest first)
  • Created (Newest first)
  • Last updated (Oldest first)
  • Last updated (Newest first)
  • Disputation date (earliest first)
  • Disputation date (latest first)
Select
The maximal number of hits you can export is 250. When you want to export more records please use the 'Create feeds' function.
  • 1. Adamaszek, Michal
    et al.
    Barmak, Jonathan Ariel
    KTH, School of Engineering Sciences (SCI), Mathematics (Dept.).
    On a lower bound for the connectivity of the independence complex of a graph2011In: Discrete Mathematics, ISSN 0012-365X, E-ISSN 1872-681X, Vol. 311, no 21, p. 2566-2569Article in journal (Refereed)
    Abstract [en]

    Aharoni, Berger and Ziv proposed a function which is a lower bound for the connectivity of the independence complex of a graph. They conjectured that this bound is optimal for every graph. We give two different arguments which show that the conjecture is false.

  • 2.
    Austrin, Per
    et al.
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Kaski, P.
    Koivisto, M.
    Nederlöf, J.
    Dense Subset Sum may be the hardest2016In: Leibniz International Proceedings in Informatics, LIPIcs, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing , 2016Conference paper (Refereed)
    Abstract [en]

    The Subset Sum problem asks whether a given set of n positive integers contains a subset of elements that sum up to a given target t. It is an outstanding open question whether the O∗(2n/2)-time algorithm for Subset Sum by Horowitz and Sahni [J. ACM 1974] can be beaten in the worst-case setting by a "truly faster", O∗(2(0.5-δ)n)-time algorithm, with some constant δ > 0. Continuing an earlier work [STACS 2015], we study Subset Sum parameterized by the maximum bin size β, defined as the largest number of subsets of the n input integers that yield the same sum. For every ∈ > 0 we give a truly faster algorithm for instances with β ≤ 2(0.5-∈)n, as well as instances with β ≥ 20.661n. Consequently, we also obtain a characterization in terms of the popular density parameter n/log2 t: if all instances of density at least 1.003 admit a truly faster algorithm, then so does every instance. This goes against the current intuition that instances of density 1 are the hardest, and therefore is a step toward answering the open question in the affirmative. Our results stem from a novel combinatorial analysis of mixings of earlier algorithms for Subset Sum and a study of an extremal question in additive combinatorics connected to the problem of Uniquely Decodable Code Pairs in information theory.

  • 3. Ayyer, Arvind
    et al.
    Bouttier, Jeremie
    Linusson, Svante
    KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Mathematics (Div.).
    Nunzi, Francois
    Some genelalized juggling processes (extended abstract)2015In: DMTCS proc. FPSAC'15, Nancy, France, 2015, p. 925-936Conference paper (Refereed)
    Abstract [en]

    We consider generalizations of juggling Markov chains introduced by Ayyer, Bouttier, Corteel and Nunzi. We first study multispecies generalizations of all the finite models therein, namely the MJMC, the add-drop and the annihilation models. We then consider the case of several jugglers exchanging balls. In all cases, we give explicit product formulas for the stationary probability and closed-form expressions for the normalization factor if known.

  • 4. Barak, B.
    et al.
    Gopalan, P.
    Håstad, Johan
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Meka, R.
    Raghavendra, P.
    Steurer, D.
    Making the long code shorter2015In: SIAM journal on computing (Print), ISSN 0097-5397, E-ISSN 1095-7111, Vol. 44, no 5, p. 1287-1324Article in journal (Refereed)
    Abstract [en]

    The long code is a central tool in hardness of approximation especially in questions related to the Unique Games Conjecture. We construct a new code that is exponentially more efficient but can still be used in many of these applications. Using the new code we obtain exponential improvements over several known results including the following: (1) For any ε > 0, we show the existence of an n-vertex graph G where every set of o(n) vertices has expansion 1-ε but G's adjacency matrix has more than exp(logδ n) eigenvalues larger than 1 - ε, where δ depends only on ε. This answers an open question of Arora, Barak, and Steurer [Proceedings of the 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, 2010, pp. 563-572] who asked whether one can improve over the noise graph on the Boolean hypercube that has poly(log n) such eigenvalues. (2) A gadget that reduces Unique Games instances with linear constraints modulo K into instances with alphabet k with a blowup of kpolylog(K) , improving over the previously known gadget with blowup of kω(K). (3) An n-variable integrality gap for Unique Games that survives exp(poly(log log n)) rounds of the semidefinite programming version of the Sherali-Adams hierarchy, improving on the previously known bound of poly(log log n). We show a connection between the local testability of linear codes and Small-Set Expansion in certain related Cayley graphs and use this connection to derandomize the noise graph on the Boolean hypercube.

  • 5. Bhattacharya, S.
    et al.
    Henzinger, M.
    Na Nongkai, Danupon
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    New deterministic approximation algorithms for fully dynamic matching2016Conference paper (Refereed)
    Abstract [en]

    We present two deterministic dynamic algorithms for the maximum matching problem. (1) An algorithm that maintains a (2 + ϵ)-approximate maximum matching in general graphs with O(poly(log n, 1/ϵ)) update time. (2) An algorithm that maintains an αk approximation of the value of the maximum matching with O(n2/K) update time in bipartite graphs, for every sufficiently large constant positive integer K. Here, 1 ≤ αk ≤ 2 is a constant determined by the value of K. Result (1) is the first deterministic algorithm that can maintain an o(log n)-approximate maximum matching with polylogarithmic update time, improving the seminal result of Onak et al. [STOC 2010]. Its approximation guarantee almost matches the guarantee of the best randomized polylogarithmic update time algorithm [Baswana et al. FOCS 2011]. Result (2) achieves a better-than-two approximation with arbitrarily small polynomial update time on bipartite graphs. Previously the best update time for this problem was O(m1/4) [Bernstein et al. ICALP 2015], where m is the current number of edges in the graph.

  • 6.
    Björnberg, Jakob Erik
    KTH, School of Engineering Sciences (SCI), Mathematics (Dept.).
    Graphical representations of Ising and Potts models: Stochastic geometry of the quantum Ising model and the space-time Potts model2009Doctoral thesis, monograph (Other academic)
    Abstract [en]

    HTML clipboard Statistical physics seeks to explain macroscopic properties of matter in terms of microscopic interactions. Of particular interest is the phenomenon of phase transition: the sudden changes in macroscopic properties as external conditions are varied. Two models in particular are of great interest to mathematicians, namely the Ising model of a magnet and the percolation model of a porous solid. These models in turn are part of the unifying framework of the random-cluster representation, a model for random graphs which was first studied by Fortuin and Kasteleyn in the 1970’s. The random-cluster representation has proved extremely useful in proving important facts about the Ising model and similar models.

    In this work we study the corresponding graphical framework for two related models. The first model is the transverse field quantum Ising model, an extension of the original Ising model which was introduced by Lieb, Schultz and Mattis in the 1960’s. The second model is the space–time percolation process, which is closely related to the contact model for the spread of disease. In Chapter 2 we define the appropriate space–time random-cluster model and explore a range of useful probabilistic techniques for studying it. The space– time Potts model emerges as a natural generalization of the quantum Ising model. The basic properties of the phase transitions in these models are treated in this chapter, such as the fact that there is at most one unbounded fk-cluster, and the resulting lower bound on the critical value in .

    In Chapter 3 we develop an alternative graphical representation of the quantum Ising model, called the random-parity representation. This representation is based on the random-current representation of the classical Ising model, and allows us to study in much greater detail the phase transition and critical behaviour. A major aim of this chapter is to prove sharpness of the phase transition in the quantum Ising model—a central issue in the theory— and to establish bounds on some critical exponents. We address these issues by using the random-parity representation to establish certain differential inequalities, integration of which gives the results.

    In Chapter 4 we explore some consequences and possible extensions of the results established in Chapters 2 and 3. For example, we determine the critical point for the quantum Ising model in and in ‘star-like’ geometries.

  • 7.
    Björner, Anders
    et al.
    KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Mathematics (Div.).
    Vorwerk, Kathrin
    KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Mathematics (Div.).
    On the connectivity of manifold graphs2015In: Proceedings of the American Mathematical Society, ISSN 0002-9939, E-ISSN 1088-6826, Vol. 143, no 10, p. 4123-4132Article in journal (Refereed)
    Abstract [en]

    This paper is concerned with lower bounds for the connectivity of graphs (one-dimensional skeleta) of triangulations of compact manifolds. We introduce a structural invariant b_M for simplicial d-manifolds M taking values in the range 0 <= b_M <= d-1. The main result is that b_M influences connectivity in the following way: The graph of a d-dimensional simplicial compact manifold M is (2d - b_M)-connected. The parameter b_M has the property that b_M = 0 if the complex M is flag. Hence, our result interpolates between Barnette's theorem (1982) that all d-manifold graphs are (d+1)-connected and Athanasiadis' theorem (2011) that flag d-manifold graphs are 2d-connected. The definition of b_M involves the concept of banner triangulations of manifolds, a generalization of flag triangulations.

  • 8. Chalermsook, Parinya
    et al.
    Cygan, Marek
    Kortsarz, Guy
    Laekhanukit, Bundit
    Manurangsi, Pasin
    Na Nongkai, Danupon
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Trevisan, Luca
    From Gap-ETH to FPT-Inapproximability: Clique, Dominating Set, and More2017In: 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), IEEE Computer Society, 2017, Vol. 2017, p. 743-754Conference paper (Refereed)
    Abstract [en]

    We consider questions that arise from the intersection between the areas of approximation algorithms, subexponential-time algorithms, and fixed-parameter tractable algorithms. The questions, which have been asked several times (e.g., [1], [2], [3]) are whether there is a non-trivial FPT-approximation algorithm for the Maximum Clique (Clique) and Minimum Dominating Set (DomSet) problems parameterized by the size of the optimal solution. In particular, letting OPT be the optimum and N be the size of the input, is there an algorithm that runs in t(OPT) poly(N) time and outputs a solution of size f(OPT), for any functions t and f that are independent of N (for Clique, we want f(OPT) = omega(1))? In this paper, we show that both Clique and DomSet admit no non-trivial FPT-approximation algorithm, i.e., there is no o(OPT)-FPT-approximation algorithm for Clique and no f(OPT)-FPT-approximation algorithm for DomSet, for any function f (e.g., this holds even if f is an exponential or the Ackermann function). In fact, our results imply something even stronger: The best way to solve Clique and DomSet, even approximately, is to essentially enumerate all possibilities. Our results hold under the Gap Exponential Time Hypothesis (Gap-ETH) [4], [5], which states that no 2(o(n))-time algorithm can distinguish between a satisfiable 3SAT formula and one which is not even (1 - epsilon)-satisfiable for some constant epsilon > 0. Besides Clique and DomSet, we also rule out non-trivial FPT-approximation for Maximum Balanced Biclique, the problem of finding maximum subgraphs with hereditary properties (e.g., Maximum Induced Planar Subgraph), and Maximum Induced Matching in bipartite graphs. Previously only exact versions of these problems were known to be W[1]-hard [6], [7], [8]. Additionally, we rule out k(o(1))-FPT-approximation algorithm for Densest k-Subgraph although this ratio does not yet match the trivial O(k)-approximation algorithm. To the best of our knowledge, prior results only rule out constant factor approximation for Clique [9], [10] and log(1/4+epsilon) (OPT) approximation for DomSet for any constant epsilon > 0 [11]. Our result on Clique significantly improves on [9], [10]. However, our result on DomSet is incomparable to [11] since their results hold under ETH while our results hold under Gap-ETH, which is a stronger assumption.

  • 9. Deng, J.
    et al.
    Song, Wenjun
    KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Optimization and Systems Theory.
    Liu, Z.
    Baras, J. S.
    Pose synchronization of rigid body networks with switching topologies2015In: 2015 34th Chinese Control Conference (CCC), IEEE Computer Society, 2015, Vol. 2015, p. 7639-7644Conference paper (Refereed)
    Abstract [en]

    Coordination control of multiple rigid bodies attracts much attention of researchers due to its wide applications. This paper presents the pose synchronization problem of the moving rigid bodies whose dynamics is described by the group SE(3). The case of bidirectional neighbor graphs with switching interconnection topologies is considered. We design a distributed control law based on relative rotation matrices and relative positions between the neighboring rigid bodies, and show that the SE(3) reaches pose synchronization if and only if the neighbor graphs are infinitely jointly connected, which relaxes the theoretical results in the existing literature.

  • 10.
    Engardt, Max
    KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Mathematics (Div.).
    Structure Learning of Bayesian Networks with Bounded Treewidth Using Mixed Integer Linear Programming2014Independent thesis Advanced level (degree of Master (Two Years)), 20 credits / 30 HE creditsStudent thesis
    Abstract [en]

    When given a Bayesian network, a common use of it is calculating conditional probabilities. This is known as inference. In order to be able to infer effectively, the structure of the Bayesian network is required to have low treewidth. Therefore, the problem of learning the structure of Bayesian networks with bounded treewidth is studied in this thesis. This is solved by reducing the problem to a mixed integer linear problem using several formulation for the structure of the Bayesian network as well as for bounding the treewidth of the structure. Solving the problem in this way gives an algorithm known as an anytime algorithm which can be aborted during the run and return a solution as well as an upper bound for the value of the best possible solution. Tests show that several of these formulations are of practical use as implementations of them prove solutions to be optimal or nearly optimal for several data sets.

  • 11. Eriksen, Niklas
    et al.
    Sjöstrand, Jonas
    KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Mathematics (Div.).
    Equidistributed Statistics on Matchings and Permutations2014In: The Electronic Journal of Combinatorics, ISSN 1097-1440, E-ISSN 1077-8926, Vol. 21, no 4, article id P4.43Article in journal (Refereed)
    Abstract [en]

    We show that the bistatistic of right nestings and right crossings in matchings without left nestings is equidistributed with the number of occurrences of two certain patterns in permutations, and furthermore that this equidistribution holds when refined to positions of these statistics in matchings and permutations. For this distribution we obtain a non-commutative generating function which specializes to Zagier's generating function for the Fishburn numbers after abelianization. As a special case we obtain proofs of two conjectures of Claesson and Linusson. Finally, we conjecture that our results can be generalized to involving left crossings of matchings too.

  • 12.
    Eriksson, Kimmo
    et al.
    Mälardalen University, School of Education, Culture and Communication.
    Sjöstrand, Jonas
    KTH, School of Engineering Sciences (SCI), Mathematics (Dept.).
    Limiting shapes of birth-and-death processes on Young diagrams2012In: Advances in Applied Mathematics, ISSN 0196-8858, E-ISSN 1090-2074, Vol. 48, no 4, p. 575-602Article in journal (Refereed)
    Abstract [en]

    We consider a family of birth processes and birth-and-death processes on Young diagrams of integer partitions of n. This family incorporates three famous models from very different fields: Rost's totally asymmetric particle model (in discrete time), Simon's urban growth model, and Moran's infinite alleles model. We study stationary distributions and limit shapes as n tends to infinity, and present a number of results and conjectures.

  • 13.
    Eriksson, Kimmo
    et al.
    Malardalen Univ, Dept Math & Phys.
    Sjöstrand, Jonas
    Malardalen Univ, Dept Math & Phys.
    Strimling, Pontus
    Malardalen Univ, Dept Math & Phys.
    Optimal expected rank in a two-sided secretary problem2007In: Operations Research, ISSN 0030-364X, E-ISSN 1526-5463, Vol. 55, no 5, p. 921-931Article in journal (Refereed)
    Abstract [en]

    In a two-sided version of the famous secretary problem, employers search for a secretary at the same time as secretaries search for an employer. Nobody accepts being put on hold, and nobody is willing to take part in more than N interviews. Preferences are independent, and agents seek to optimize the expected rank of the partner they obtain among the N potential partners. We find that in any subgame perfect equilibrium, the expected rank grows as the square root of N (whereas it tends to a constant in the original secretary problem). We also compute how much agents can gain by cooperation.

  • 14. Hachem, Walid
    et al.
    Hardy, Adrien
    KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Mathematics (Div.).
    Najim, Jamal
    Large complex correlated wishart matrices: Fluctuations and asymptotic independence at the edges2016In: Annals of Probability, ISSN 0091-1798, E-ISSN 2168-894X, Vol. 44, no 3, p. 2264-2348Article in journal (Refereed)
    Abstract [en]

    We study the asymptotic behavior of eigenvalues of large complex correlated Wishart matrices at the edges of the limiting spectrum. In this setting, the support of the limiting eigenvalue distribution may have several connected components. Under mild conditions for the population matrices, we show that for every generic positive edge of that support, there exists an extremal eigenvalue which converges almost surely toward that edge and fluctuates according to the Tracy-Widom law at the scale N-2/3. Moreover, given several generic positive edges, we establish that the associated extremal eigenvalue fluctuations are asymptotically independent. Finally, when the leftmost edge is the origin ( hard edge), the fluctuations of the smallest eigenvalue are described by mean of the Bessel kernel at the scale N-2.

  • 15.
    Hultman, Axel
    et al.
    KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Mathematics (Div.).
    Jonsson, Jakob
    KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Mathematics (Div.).
    The topology of the space of matrices of Barvinok rank two2010In: Beiträge zur Algebra und Geometrie, ISSN 0138-4821, Vol. 51, no 2, p. 373-390Article in journal (Refereed)
    Abstract [en]

    The Barvinok rank of a d x n matrix is the minimum number of  points in Rd such that the tropical convex hull of the points contains all columns of the matrix. The concept originated in work by Barvinok and others on the travelling salesman problem. Our object of study is the space of real d x n matrices of Barvinok rank two. Let Bd,n denote this space modulo rescaling and translation. We show that Bd,n is a manifold, thereby settling a  conjecture due to Develin. In fact, Bd,n is homeomorphic to the quotient of the product of spheres Sd-2 x Sn-2 under the involution which sends each point to its antipode simultaneously in both  components.  In addition, using discrete Morse theory, we compute the integral homology of Bd,n. Assuming d \ge n, for odd d the homology turns out to be   isomorphic to that of Sd-2 x RPn-2. This  is true also for even d up to degree d-3, but the two cases differ from degree d-2 and up. The homology computation straightforwardly extends to more general  complexes of the form (Sd-2 x X)//Z2, where X is a finite cell  complex of dimension at most d-2 admitting a free  Z2-action.

  • 16. Kennedy, J. B.
    et al.
    Kurasov, P.
    Malenova, Gabriela
    KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Numerical Analysis, NA.
    Mugnolo, D.
    On the Spectral Gap of a Quantum Graph2016In: Annales de l'Institute Henri Poincare. Physique theorique, ISSN 1424-0637, E-ISSN 1424-0661, p. 1-35Article in journal (Refereed)
    Abstract [en]

    We consider the problem of finding universal bounds of “isoperimetric” or “isodiametric” type on the spectral gap of the Laplacian on a metric graph with natural boundary conditions at the vertices, in terms of various analytical and combinatorial properties of the graph: its total length, diameter, number of vertices and number of edges. We investigate which combinations of parameters are necessary to obtain non-trivial upper and lower bounds and obtain a number of sharp estimates in terms of these parameters. We also show that, in contrast to the Laplacian matrix on a combinatorial graph, no bound depending only on the diameter is possible. As a special case of our results on metric graphs, we deduce estimates for the normalised Laplacian matrix on combinatorial graphs which, surprisingly, are sometimes sharper than the ones obtained by purely combinatorial methods in the graph theoretical literature.

  • 17.
    Lundman, Anders
    KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Mathematics (Div.).
    Computing Seshardi constants on smooth toric surfacesManuscript (preprint) (Other academic)
    Abstract [en]

    In this paper we compute the Seshadri constants at the general point on many smooth polarized toric surfaces. We consider the case when the degree of jet separation is small or the core of the associated polygon is a line segment. Our main result is that in this case the Seshadri constant at the general point can often be determined in terms of easily computable invariants of the surfaces at hand. Lastly we consider the case that the core of the associated polygon is a point for a smooth polarized toric surface (X, L ). We show that in this case X can be constructed via consecutive equivariant blow-ups of either P^2 or P^1 x P^1. 

  • 18.
    Lundman, Anders
    et al.
    KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Mathematics (Div.).
    Di Rocco, Sandra
    KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Mathematics (Div.).
    Jabbusch, Kelly
    Department of mathematics & statistics, University of Michigan-Dearborn.
    A note on higher order Gauss MapsManuscript (preprint) (Other academic)
    Abstract [en]

    We study Gauss maps of order k, associated to a projective variety X embedded in projective space via a line bundle L. We show that if X is a smooth, complete complex variety and L is a k-jet spanned line bundle on X, with k > 1, then the Gauss map of order k has finite fibers, unless X = P^n is embedded by the Veronese embedding of order k. In the case where X is a toric variety, we give a combinatorial description of the Gauss maps of order k, its image and the general fibers. 

  • 19. Shi, Guodong
    et al.
    Anderson, Brian D. O.
    Johansson, Karl Henrik
    KTH, School of Electrical Engineering (EES), Automatic Control. KTH, School of Electrical Engineering (EES), Centres, ACCESS Linnaeus Centre.
    Consensus Over Random Graph Processes: Network Borel-Cantelli Lemmas for Almost Sure Convergence2015In: IEEE Transactions on Information Theory, ISSN 0018-9448, E-ISSN 1557-9654, Vol. 61, no 10, p. 5690-5707Article in journal (Refereed)
    Abstract [en]

    Distributed consensus computation over random graph processes is considered. The random graph process is defined as a sequence of random variables which take values from the set of all possible digraphs over the node set. At each time step, every node updates its state based on a Bernoulli trial, independent in time and among different nodes: either averaging among the neighbor set generated by the random graph, or sticking with its current state. The connectivity-independence and arc-independence are introduced to capture the fundamental influence of the random graphs on the consensus convergence. Necessary and/or sufficient conditions are presented on the success probabilities of the Bernoulli trials for the network to reach a global almost sure consensus, with some sharp threshold established revealing a consensus zero-one law. Convergence rates are established by the lower and upper bounds of the epsilon-computation time. We also generalize the concepts of connectivity/arc independence to their analogues from the *-mixing point of view, so that our results apply to a very wide class of graphical models, including the majority of random graph models in the literature, e.g., Erdos-Renyi, gossiping, and Markovian random graphs. We show that under *-mixing, our convergence analysis continues to hold and the corresponding almost sure consensus conditions are established. Finally, we further investigate almost sure finite-time convergence of random gossiping algorithms, and prove that the Bernoulli trials play a key role in ensuring finite-time convergence. These results add to the understanding of the interplay between random graphs, random computations, and convergence probability for distributed information processing.

  • 20.
    Shirabe, Takeshi
    KTH, School of Architecture and the Built Environment (ABE), Urban Planning and Environment, Geoinformatics.
    A method for finding a least-cost wide path in raster space2016In: International Journal of Geographical Information Science, ISSN 1365-8816, E-ISSN 1365-8824, Vol. 30, no 8, p. 1469-1485Article in journal (Refereed)
    Abstract [en]

    Given a grid of cells each having an associated cost value, a raster version of the least-cost path problem seeks a sequence of cells connecting two specified cells such that its total accumulated cost is minimized. Identifying least-cost paths is one of the most basic functions of raster-based geographic information systems. Existing algorithms are useful if the path width is assumed to be zero or negligible compared to the cell size. This assumption, however, may not be valid in many real-world applications ranging from wildlife corridor planning to highway alignment. This paper presents a method to solve a raster-based least-cost path problem whose solution is a path having a specified width in terms of Euclidean distance (rather than by number of cells). Assuming that all cell values are positive, it does so by transforming the given grid into a graph such that each node represents a neighborhood of a certain form determined by the specified path width, and each arc represents a possible transition from one neighborhood to another. An existing shortest path algorithm is then applied to the graph. This method is highly efficient, as the number of nodes in the transformed graph is not more than the number of cells in the given grid and decreases with the specified path width. However, a shortcoming of this method is the possibility of generating a self-intersecting path which occurs only when the given grid has an extremely skewed distribution of cost values.

  • 21. Strimling, Pontus
    et al.
    Sjöstrand, Jonas
    Centre for the Study of Cultural Evolution, Stockholm University.
    Accumulation of independent cultural traits2009In: Theoretical Population Biology, ISSN 0040-5809, E-ISSN 1096-0325, Vol. 76, no 2, p. 77-83Article in journal (Refereed)
    Abstract [en]

    In a species capable of (imperfect) social learning, how much culture can a population of a given size carry? And what is the relationship between the individual and the population? In the first study of these novel questions, here we develop a mathematical model of the accumulation of independent cultural traits in a finite population with overlapping generations.

  • 22. Tancer, Martin
    et al.
    Vorwerk, Kathrin
    KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Mathematics (Div.).
    Non-embeddability of geometric lattices and buildings2014In: Discrete & Computational Geometry, ISSN 0179-5376, E-ISSN 1432-0444, Vol. 51, no 4, p. 779-801Article in journal (Refereed)
    Abstract [en]

    A fundamental question for simplicial complexes is to find the lowest dimensional Euclidean space in which they can be embedded. We investigate this question for order complexes of posets. We show that order complexes of thick geometric lattices as well as several classes of finite buildings, all of which are order complexes, are hard to embed. That means that such -dimensional complexes require -dimensional Euclidean space for an embedding. (This dimension is always sufficient for any -complex.) We develop a method to show non-embeddability for general order complexes of posets.

  • 23.
    Thunberg, Hans
    KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Mathematics (Div.).
    Tonsättaren Per Nörgårds ''oändlighetsserie"2013In: Normat, ISSN 0801-3500, Vol. 61, no 1, p. 33-47Article in journal (Refereed)
    Abstract [en]

    This article presents a mathematical description, in terms of recursively defined number sequences, of the algorithms devised by the Danish composer Nørgård. The ambition of the latter was to generate from a very short sequence of tones melodies rich in symmetries and selfsimilarities, melodies which could be aperiodic and hence infinite in length. Given the mathematical presentation a variety of results can be formulated and proved. Note that the well-known Thue-Morse sequence is essentially a special case.

1 - 23 of 23
CiteExportLink to result list
Permanent link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf