Many problems in diverse areas of mathematics and modern physical sciences can be formulated as a Convex Feasibility Problem, consisting of finding a point in the intersection of finitely many closed convex sets. Two other related problems are the Split Feasibility Problem and the Multiple-Sets Split Feasibility Problem, both very useful when solving inverse problems where constraints are imposed in the domain as well as in the range of a linear operator. We present some recent contributions concerning these problems in the setting of Hilbert spaces along with some numerical experiments to illustrate the implementation of some iterative methods in signal processing.
Motivated by laboratory studies on the distribution of brain synapses, the classical theory of box integrals - being expectations on unit hypercubes - is extended to a new class of fractal "string-generated Cantor sets" that facilitate fine-tuning of their fractal dimension through a suitable choice of generating string. Closed forms for certain statistical moments on these fractal sets will be presented, together with a precision algorithm for higher embedding dimensions. This is based on joint work with Laur. Prof. Jon Borwein, Prof. David Bailey and Dr. Richard Crandall.
Parameterised approximation is a relatively new but growing field of interest. It merges two ways of dealing with NP-hard optimisation problems, namely polynomial approximation and exact parameterised (exponential-time) algorithms.
We explore opportunities for parameterising constant factor approximation algorithms for vertex cover, and we provide a simple algorithm that works on any approximation ratio of the form $\frac{2l+1}{l+1}$, $l=1,2,\dots$, and has complexity that outperforms previously published algorithms by Bourgeois et al. based on sophisticated exact parameterised algorithms. In particular, for $l=1$ (factor-$1.5$ approximation) our algorithm runs in time $\text{O}^*(\text{simpleonefiveapproxbase}^k)$, where parameter $k \leq \frac{2}{3}\tau$, and $\tau$ is the size of a minimum vertex cover.
Additionally, we present an improved polynomial-time approximation algorithm for graphs of average degree at most four and a limited number of vertices with degree less than two.
This is the second part of the informal seminar on an introduction to symbolic convex analysis. The published paper on which this seminar is mainly based on can be found at http://www.carma.newcastle.edu.au/jon/fenchel.pdf.
Nonexpansive operators in Banach spaces are of utmost importance in Nonlinear Analysis and Optimization Theory. We are concerned in this talk with classes of operators which are, in some sense, nonexpansive not with respect to the norm, but with respect to Bregman distances. Since these distances are not symmetric in general, it seems natural to distinguish between left and right Bregman nonexpansive operators. Some left classes have already been studied quite intensively, so this talk is mainly devoted to right Bregman nonexpansive operators and the relationship between both classes.
This talk is based on joint works with Prof. Simeon Reich and Shoham Sabach from Technion-Israel Institute of Technology, Haifa.
Multi-linear functions appear in many global optimization problems, including reformulated quadratic and polynomial optimization problems. There is a extended formulation for the convex hull of the graph of a multi-linear function that requires the use of an exponential number of variables. Relying on this result, we study an approach that generates relaxations for multiple terms simultaneously, as opposed to methods that relax the nonconvexity of each term individually. In some special cases, we are able to establish analytic bounds on the ratio of the strength of the term-by-term and convex hull relaxations. To our knowledge, these are the first approximation-ratio results for the strength of relaxations of global optimization problems. The results lend insight into the design of practical (non-exponentially sized) relaxations. Computations demonstrate that the bounds obtained in this manner are competitive with the well-known semi-definite programming based bounds for these problems.
Joint work with Jim Luedtke, University of Wisconsin-Madison, and Mahdi Namazifar, now with Opera Solutions.
This talk is an introduction to symbolic convex analysis.
I will discuss a new algorithm for counting points on hyperelliptic curves over finite fields.
In this talk, we present our ongoing efforts in solving a number of continuous facility location problems that involve sets using recently developed tools of variational analysis and generalized differentiation. Subgradients of a class of nonsmooth functions called minimal time functions are developed and employed to study these problems. Our approach advances the applications of variational analysis and optimization to a well-developed field of facility location, while shedding new light on well-known classical geometry problems such as the Fermat-Torricelli problem, the Sylvester smallest enclosing circle problem, and the problem of Apollonius.
Automata groups are a class of groups generated by recursively defined automorphisms of a regular rooted tree. Associated to each automata group is an object known as the self-similarity graph. Nekrashevych showed that in the case where the group satisfies a natural condition known as contracting, the self-similarity graph is Gromov-hyperbolic and has boundary homeomorphic to the limit space of the group action. I will talk about self-similarity graphs of automata groups that do not satisfy the contracting condition.
Giuga's conjecture will be introduced, and we will discuss what's changed in the computation of a counterexample in the last 17 years.
Infecting aedes aegypti with Wolbachia has been proposed as an alternative in reducing dengue transmission. If Wolbachia-infected mosquitoes can invade and dominate the population of aedes aegypti mosquitoes, they can reduce dengue transmission. Cytoplasmic Incompatibility (CI) provides the reproductive advantage for Wolbachia-infected mosquitoes with which they can reproduce more and dominate the population. A mosquito population model is developed in order to determine the survival of Wolbachia-infected mosquiotes when they are released into the wild. The model has two physically stable realistic steady states. The model reveals that once the Wolbachia-infected mosquitoes survive, they ultimately dominate the population.
We study the problem of finding an interpolating curve passing through prescribed points in the Euclidean space. The interpolating curve minimizes the pointwise maximum length, i.e., L∞-norm, of its acceleration. We re-formulate the problem as an optimal control problem and employ simple but effective tools of optimal control theory. We characterize solutions associated with singular (of infinite order) and nonsingular controls. We reduce the infinite dimensional interpolation problem to an ensuing finite dimensional one and derive closed form expressions for interpolating curves. Consequently we devise numerical techniques for finding interpolating curves and illustrate these techniques on examples.
I will give an extended version of my talk at the AustMS meeting about some ongoing work with Pierre-Emmanuel Caprace and George Willis.
Given a locally compact topological group G, the connected component of the identity is a closed normal subgroup G_0 and the quotient group is totally disconnected. Connected locally compact groups can be approximated by Lie groups, and as such are relatively well-understood. By contrast, totally disconnected locally compact (t.d.l.c.) groups are a more difficult class of objects to understand. Unlike in the connected case, it is probably hopeless to classify the simple t.d.l.c. groups, because this would include for instance all simple groups (equipped with the discrete topology). Even classifying the finitely generated simple groups is widely regarded as impossible. However, we can prove some general results about broad classes of (topologically) simple t.d.l.c. groups that have a compact generating set.
Given a non-discrete t.d.l.c. group, there is always an open compact subgroup. Compact totally disconnected groups are residually finite, so have many normal subgroups. Our approach is to analyse a t.d.l.c. group G (which may itself be simple) via normal subgroups of open compact subgroups. From these we obtain lattices and Cantor sets on which G acts, and we can use properties of these actions to demonstrate properties of G. For instance, we have made some progress on the question of whether a compactly generated topologically simple t.d.l.c. group is abstractly simple, and found some necessary conditions for G to be amenable.
We discuss how the title is related to π.
In 1966 Gallai conjectured that a connected graph of order n can be decomposed into n/2 or fewer paths when n is even, or (n+1)/2 or fewer paths when n is odd. We shall discuss old and new work on this as yet unsolved conjecture.
Many cognitive models derive their predictions through simulation. This means that it is difficult or impossible to write down a probability distribution or likelihood that characterizes the random behavior of the data as a function of the model's parameters. In turn, the lack of a likelihood means that standard Bayesian analyses of such models are impossible. In this presentation we demonstrate a procedure called approximate Bayesian computation (ABC), a method for Bayesian analysis that circumvents the evaluation of the likelihood. Although they have shown great promise for likelihood-free inference, current ABC methods suffer from two problems that have largely revented their mainstream adoption: long computation time and an inability to scale beyond models with few parameters. We introduce a new ABC algorithm, called ABCDE, that includes differential evolution as a computationally efficient genetic algorithm for proposal generation. ABCDE is able to obtain accurate posterior estimates an order of magnitude faster than a popular rejection-based method and scale to high-dimensional parameter spaces that have proven difficult for the current rejection-based ABC methods. To illustrate its utility we apply ABCDE to several well-established simulation-based models of memory and decision-making that have never been fit in a Bayesian framework.
AUTHORS: Brandon M. Turner (Stanford University) Per B. Sederberg (The Ohio State University)
Motivated by the desire to visualise large mathematical data sets, especially in number theory, we offer various tools for representing floating point numbers as planar walks and for quantitatively measuring their “randomness”.
What to expect: some interesting ideas, many beautiful pictures (including a 108-gigapixel picture of π), and some easy-to-understand maths.
What you won’t get: too many equations, difficult proofs, or any “real walking”.
This is a joint work with David Bailey, Jon Borwein and Peter Borwein.
In 1966 Gallai conjectured that a connected graph of order n can be decomposed into n/2 or fewer paths when n is even, or (n+1)/2 or fewer paths when n is odd. We shall discuss old and new work on this as yet unsolved conjecture.
In this talk, we will show that a D-finite Mahler function is necessarily rational. This gives a new proof of the rational-transcendental dichotomy of Mahler functions due to Nishioka. Using our method of proof, we also provide a new proof of a Pólya-Carlson type result for Mahler functions due to Randé; that is, a Mahler function which is meromorphic in the unit disk is either rational or has the unit circle as a natural boundary. This is joint work with Jason Bell and Eric Rowland.
If some arithmetical sums are small then the complex zeroes of the zeta-function are linearly dependent. Since we don't believe the conclusion we ought not to believe the premise. I will show that the zeroes are 'almost linearly independent' which implies, in particular, that the Mertens conjecture fails more drastically than was previously known.
In this talk projection algorithms for solving (nonconvex) feasibility problems in Euclidian spaces are considered. Of special interest are the Method of Alternating Projections (MAP) and the Averaged Alternating Reflection Algorithm (AAR) which cover some of the state of the art algorithms for our intended application, the phase retrieval problem. In the case of convex feasibility, firm nonexpansiveness of projection mappings is a global property that yields global convergence of MAP, and, for consistent problems, AAR. Based on epsilon-delta-regularity of sets (Bauschke, Luke, Phan, Wang 2012) a relaxed local version of firm nonexpansiveness with respect to the intersection is introduced for consistent feasibility problems. This combined with a type of coercivity condition, which relates to the regularity of the intersection, yields local linear convergence of MAP for a wide class of nonconvex problems, and even local linear convergence of AAR in more limited nonconvex settings.
In this talk, we study the properties of integral functionals induced on the Banach space of integrable functions by closed convex functions on a Euclidean space.
We give sufficient conditions for such integral functions to be strongly rotund (well-posed). We show that in this generality functions such as the Boltzmann-Shannon entropy and the Fermi-Dirac entropy are strongly rotund. We also study convergence in measure and give various limiting counter-example.
We consider the problem of characterising embeddings of an abstract group into totally disconnected locally compact (tdlc) groups. Specifically, for each pair of nonzero integers $m,n$ we construct a tdlc group containing the Baumslag-Solitar group $BS(m,n)$ as a dense subgroup, and compute the scales of elements and flat rank of the tdlc group.
This is joint work with George Willis.
Linear Water Wave theory is one of the most important branches on fluid mechanics. Practically it underpins most of the engineering design of ships, offshore structures, etc. It also has a very rich history in the development of applied mathematics. In this talk I will focus on the connection between solutions in the frequency and time-domains and show how we can use various formulations to make numerical calculations and to construct approximate solutions. I will illustrate these methods with application to some simple wave scattering problems.
I will discuss four much abused words Interdisciplinarity, Innovation, Collaboration and Creativity. I will describe what they mean for different stakeholder groups and will speak about my own experiences as a research scientist, as a scientific administrator, as an educator and even as a small high-tech businessman. I will also offer advice that can of course be ignored.
George continues his series of talks on the embedding of Higman-Thompson groups into the groups of almost automorphisms of trees, structure theorems and scale calculations for these examples.
In this talk, we study the properties of integral functionals induced on $L_\text{E}^1(S,\mu)$ by closed convex functions on a Euclidean space E. We give sufficient conditions for such integral functions to be strongly rotund (well-posed). We show that in this generality functions such as the Boltzmann-Shannon entropy and the Fermi-Dirac entropy are strongly rotund. We also study convergence in measure and give various limiting counter-example.
This is joint work with Jon Borwein.
Recently the Alternating Projection Algorithm was extended into CAT(0) spaces. We will look at this and also current work on extending the Douglas Rachford Algorithm into CAT(0) spaces. By using CAT(0) spaces the underlying linear structure of the space is dispensable and this allows certain algorithms to be extended to spaces such as classical hyperbolic spaces, simply connected Riemannian manifolds of non-positive curvature, R-trees and Euclidean buildings.
This week Brian Alspach will complete the discussion on Burnside's Theorem and vertex-transitive graphs of prime order.
George continues his series of talks on the embedding of Higman-Thompson groups into the groups of almost automorphisms of trees, structure theorems and scale calculations for these examples.
A frequent theme of 21st century experimental math is the computer discovery of identities, typically done by means of computing some mathematical entity (a sum, limit, integral, etc) to very high numeric precision, then using the PSLQ algorithm to identify the entity in terms of well known constants.
Perhaps the most successful application of this methodology has been to identify integrals arising in mathematical physics. This talk will present numerous examples of this type, including integrals from quantum field theory, Ising theory, random walks, 3D lattice problems, and even mouse brains. In some cases, it is necessary to compute these integrals to 3000-digit precision, and developing techniques to do such computations is a daunting technical challenge.
Given a positive integer b, we say that a mathematical constant alpha is "b-normal" or "normal base b" if every m-long string of digits appears in the base-b expansion of alpha with precisely the limiting frequency 1/b^m. Although it is well known from measure theory that almost all real numbers are b-normal for all integers b > 1, nonetheless proving normality (or nonnormality) for specific constants, such as pi, e and log(2), has been very difficult.
In the 21st century, a number of different approaches have been attempted on this problem. For example, a recent study employed a Poisson model of normality to conclude that based on the first four trillion hexadecimal digits of pi, it is exceedingly unlikely that pi is not normal. In a similar vein, graphical techniques, in most cases based on the digit-generated "random" walks, have been successfully employed to detect certain nonnormality in some cases.
On the analytical front, it was shown in 2001 that the normality of certain reals, including log(2) and pi (or any other constant given by a BBP formula), could be reduced to a question about the behavior of certain specific pseudorandom number generators. Subsequently normality was established for an uncountable class of reals (the "Stoneham numbers"), the simplest of which is: alpha_{2,3} = Sum_{n >= 0} 1/(3^n 2^(3^n)), which is provably normal base 2. Just as intriguing is a recent result that alpha_{2,3}, for instance, is provably NOT normal base 6. These results have now been generalized to some extent, although many open cases remain.
In this talk I will present an introduction to the theory of normal numbers, including brief mention of new graphical- and statistical-based techniques. I will then sketch a proof of the normality base 2 (and nonnormality base 6) of Stoneham numbers, then suggest some additional lines of research. Various parts of this research were conducted in collaboration with Richard Crandall, Jonathan and Peter Borwein, Francisco Aragon, Cristian Calude, Michael Dinneen, Monica Dumitrescu and Alex Yee.
We shall continue exploring implications of Burnside's Theorem for vertex-transitive graphs.
George is going to continue his series of talks on the embedding of Higman-Thompson groups into the groups of almost automorphisms of trees, and over several weeks look at the structure theorems and scale calculations for these examples.
Variational methods have been used to derive symmetric solutions for many problems related to real world applications. To name a few we mention periodic solutions to ODEs related to N-body problems and electrical circuits, symmetric solutions to PDEs, and symmetry in derivatives of spectral functions. In this talk we examine the commonalities of using variational methods in the presence of symmetry.
This is an ongoing collaborative research project with Jon Borwein. So far our questions still outnumber our answers.
Groundwater makes up nearly 30% of the entire world’s freshwater but the mathematical models for the better understanding of the system are difficult to validate due to the disordered nature of the porous media and the complex geometry of the channels of flow. In this seminar, after establishing the statistical macroscopic equivalent of the Navier-Stokes equations for the groundwater hydrodynamic and its consequences in term of Laplace and diffusion equations, some cases will be solved in term of special functions by using the modern Computer Algebra System.
We shall continue exploring implications of Burnside's Theorem for vertex-transitive graphs.
George is going to start giving some talks on the embedding of Higman-Thompson groups into the groups of almost automorphisms of trees, and over several weeks will look at the structure theorems and scale calculations for these examples.
We are holding an afternoon mini-conference, in conjunction with the School of Mathematical and Physical Sciences.
If you are engaged in any of the many Outreach Activities in the Mathematical Sciences that people from CARMA, our School and beyond contribute to, for example visiting primary or secondary schools, presenting to schools who visit us, public lectures, media interviews, helping run maths competitions, etc etc, and would like to share what you're doing, please let us know. Also if you're not currently engaged in an outreach activity but have an idea that you would like to try, and want to use a talk about your idea as a "sounding board", please feel free to do so.
There will be some very short talks: 5 minutes, and some longer talks: 20 minutes, with time for discussion in between. We'll be serving afternoon tea throughout the afternoon; and will have an open discussion forum near the end of the day. If you're interested in giving a talk please contact Judy-anne.Osborn@newcastle.edu.au, indicating whether you'd prefer a 5-minute or a 20-minute slot. If you're simply interested in attending, please let us know as well for catering purposes. The event will be held in one of the function rooms in the Shortland building.
12:05 — Begin, with welcome and lunch
15:45 — Last talk finishes
15:45-16:15 — Open discussion
Burnside's Theorem characterising transitive permutation groups of prime degree has some wonderful applications for graphs. This week we start an exploration of this topic.
(Joint speakers, Jon Borwein and Michael Rose)
p>Using fractal self-similarity and functional-expectation relations, the classical theory of box integrals is extended to encompass a new class of fractal “string-generated Cantor sets” (SCSs) embedded in unit hypercubes of arbitrary dimension. Motivated by laboratory studies on the distribution of brain synapses, these SCSs were designed for dimensional freedom: a suitable choice of generating string allows for fine-tuning the fractal dimension of the corresponding set. We also establish closed forms for certain statistical moments on SCSs and report various numerical results. The associated paper is at http://www.carma.newcastle.edu.au/jon/papers.html#PAPERS.Let $F(z)$ be a power series, say with integer coefficients. In the late 1920s and early 1930s, Kurt Mahler discovered that for $F(z)$ satisfying a certain type of functional equation (now called Mahler functions), the transcendence of the function $F(z)$ could be used to prove the transcendence of certain special values of $F(z)$. Mahler's main application at the time was to prove the transcendence of the Thue-Morse number $\sum_{n\geq 0}t(n)/2^n$ where $t(n)$ is either 0 or 1 depending on the parity of the number of 1s in the base 2 expansion of $n$. In this talk, I will talk about some of the connections between Mahler functions and finite automata and highlight some recent approaches to large problems in the area. If time permits, I will outline a new proof of a version of Carlson's theorem for Mahler functions; that is, a Mahler function is either rational or it has the unit circle as a natural boundary.
Snarks are 3-regular graphs that are not 3-edge-colourable and are cyclically 4-edge-connected. They exist but are hard to find. On the other hand, it is believed that Cayley graphs can never be snarks. The latter is the subject of the next series of talks.
Snarks are 3-regular graphs that are not 3-edge-colourable and are cyclically 4-edge-connected. They exist but are hard to find. On the other hand, it is believed that Cayley graphs can never be snarks. The latter is the subject of the next series of talks.
Hajek proved that a WUR Banach space is an Asplund space. This result suggests that the WUR property might have interesting consequences as a dual property. We show that
(i) every Banach Space with separable second dual can be equivalently renormed to have WUR dual,
(ii) under certain embedding conditions a Banach space with WUR dual is reflexive.
Snarks are 3-regular graphs that are not 3-edge-colourable and are cyclically 4-edge-connected. They exist but are hard to find. On the other hand, it is believed that Cayley graphs can never be snarks. The latter is the subject of the next series of talks.
We consider the bipartite version of the degree/diameter problem; namely, find the maximum number Nb(d,D) of vertices in a bipartite graph of maximum degree d>2 and diameter D>2. The actual value of Nb(d,D) is still unknown for most (d,D) pairs.
The well-known Moore bound Mb(d,D) gives a general upper bound for Nb(d,D); graphs attaining this bound are called Moore (bipartite) graphs. Moore bipartite graphs are very scarce; they may only exist for D=3,4 or 6, but no other diameters. Interest has then shifted to investigate the existence or otherwise of graphs missing the Moore bound by a few vertices. A graph with order Mb(d,D)-e is called a graph of defect e.
It has been proved that bipartite graphs of defect 2 do not exist when D>3. In our paper we 'almost' prove that bipartite graphs of defect 4 cannot exist when D>4, thereby establishing a new upper bound on Nb(d,D) for more than 2/3 of all (d,D) combinations.
Dr Koerber will speak about the experience of using MapleTA extensively in undergraduate teaching at the University of Adelaide, and demonstrate how they have been using the system there. Bio: Adrian Koerber is Director of First Year Studies in Mathematics at the University of Adelaide. His mathematical research is in the area of modelling gene networks.
We present a nonconvex bundle technique where function and subgradient values are available only up to an error tolerance which remains unknown to the user. The challenge is to develop an algorithm which converges to an approximate solution which, despite the lack of information, is as good as one can hope for. For instance, if data are known up to the error $O(\epsilon)$, the solution should also be accurate up to $O(\epsilon)$. We show that the oracle of downshifted tangents is an excellent tool to deal with this difficult situation.
We consider the bipartite version of the degree/diameter problem; namely, find the maximum number Nb(d,D) of vertices in a bipartite graph of maximum degree d>2 and diameter D>2. The actual value of Nb(d,D) is still unknown for most (d,D) pairs.
The well-known Moore bound Mb(d,D) gives a general upper bound for Nb(d,D); graphs attaining this bound are called Moore (bipartite) graphs. Moore bipartite graphs are very scarce; they may only exist for D=3,4 or 6, but no other diameters. Interest has then shifted to investigate the existence or otherwise of graphs missing the Moore bound by a few vertices. A graph with order Mb(d,D)-e is called a graph of defect e.
It has been proved that bipartite graphs of defect 2 do not exist when D>3. In our paper we 'almost' prove that bipartite graphs of defect 4 cannot exist when D>4, thereby establishing a new upper bound on Nb(d,D) for more than 2/3 of all (d,D) combinations.
Motivated by questions of algorithm analysis, we provide several distinct approaches to determining convergence and limit values for a class of linear iterations.
This is joint work with D. Borwein and B. Sims.
A body moves in a rarefied medium of resting particles and at the same time very slowly rotates (somersaults). Each particle of the medium is reflected elastically when hitting the body boundary (multiple reflections are possible). The resulting resistance force acting on the body depends on the time; we are interested in minimizing the time-averaged value of resistance (which is called $R$). The value $R(B)$ is well defined in terms of billiard in the complement of $B$, for any bounded body $B \subset \mathbb{R}^d$, $d\geq 2$ with piecewise smooth boundary.
Let $C\subset\mathbb{R}^d$ be a bounded convex body and $C_1\subset C$ be another convex body with $\partial C_1 \cap C=\varnothing$. It would be interesting to get an estimate for $$R(C1_,C)= \inf_{C_1\subset B \subset C} R(B) .................. (1)$$ If $\partial C_1$ is close to $\partial C$, problem (1) can be referred to as minimizing the resistance of the convex body $C$ by "roughening" its surface. We cannot solve problem (1); however we can find the limit $$\lim_{\text{dist}(\partial C_1,\partial C)\rightarrow 0} \frac{R(C_1,C)}{R(C)}. .................. (2) $$
It will be explained that problem (2) can be solved by reduction to a special problem of optimal mass transportation, where the initial and final measurable spaces are complementary hemispheres, $X=\{x=(x_1,...,x_d)\in S^{d-1}: x_1\geq 0\}$ and $Y=\{x\in S^{d-1}:x_1\leq 0\}$. The transportation cost is the squared distance, $c(x,y)=\frac{1}{2}|x-y|^2$, and the measures in $X$ and $Y$ are obtained from the $(d-1)$-dimensional Lebesgue measure on the equatorial circle $\{x=(x_1,...,x_d):|x|\leq 1,x_1=0\}$ by parallel translation along the vector $e_1=(1,0,...,0)$. Let $C(\nu)$ be the total cost corresponding to the transport plan $\nu$ and let $\nu_0$ be the transport plan generated by parallel translation along $e_1$; then the value $\frac{\inf C(\nu)}{C(\nu_0)}$ coincides with the limit in (2).
Surprisingly, this limit does not depend on the body $C$ and depends only on the dimension $d$.
In particular, if $d=3$ ($d=2$), it equals (approximately) 0.96945 (0.98782). In other words, the resistance of a 3-dimensional (2-dimensional) convex body can be decreased by 3.05% (correspondingly, 1.22%) at most by roughening its surface.
The Douglas-Rachford algorithm is an iterative method for finding a point in the intersection of two (or more) closed sets. It is well-known that the iteration (weakly) converges when it is applied to convex subsets of a Hilbert space. Despite the absence of a theoretical justification, the algorithm has also been successfully applied to various non-convex practical problems, including finding solutions for the eight queens problem, or sudoku puzzles. In particular, we will show how these two problems can be easily modelled.
With the aim providing some theoretical explanation of the convergence in the non-convex case, we have established a region of convergence for the prototypical non-convex Douglas-Rachford iteration which finds a point on the intersection of a line and a circle. Previous work was only able to establish local convergence, and was ineffective in that no explicit region of convergence could be given.
PS: Bring your hardest sudoku puzzle :)
Based on generalized backward shift operators we introduce adaptive Fourier decomposition. Then we discuss its relations and applications to (i) system identification; (2) computation of Hilbert transform; (3) algorithm for the best order-n rational approximation to functions in the Hardy space H2; (4) forward and backward shift invariant spaces; (5) band preserving in filter designing; (6) phase retrieving; and (7) the Bedrosian identity. The talk also concerns possible generalizations of the theory and applications to higher dimensional spaces.
I will give a brief introduction to the theory of self-similar groups, focusing on a couple of pertinent examples: Grigorchuk's group of intermediate growth, and the basilica group.
This week the speaker in the Discrete Mathematics Instructional Seminar is Judy-anne Osborn who will be discussing Hadamard matrices.
TBA
The double zeta values are one natural way to generalise the Riemann zeta function at the positive integers; they are defined by $\zeta(a,b) = \sum_{n=1}^\infty \sum_{m=1}^{n-1} 1/n^a/m^b$. We give a unified and completely elementary method to prove several sum formulae for the double zeta values. We also discuss an experimental method for discovering such formulae.
Moreover, we use a reflection formula and recursions involving the Riemann zeta function to obtain new relations of closely related functions, such as the Witten zeta function, alternating double zeta values, and more generally, character sums.
There is a high prevalence of tuberculosis (TB) in Papua New Guinea (PNG), which is exacerbated by the presence of drug-resistant TB strains and HIV infection. This is an important public health issue not only locally within PNG, but also in Australia due to the high cross-border traffic in the Torres Strait Island–Western Province (PNG) treaty region. A metapopulation model is used to evaluate the effect of varying control strategies in the region, and some initial cost-benefit analysis figures are presented.
This week the speaker in the Discrete Mathematics Instructional Seminar is Judy-anne Osborn who will be discussing Hadamard matrices.
A graph on v vertices is called pancyclic if it contains cycles of every length from 3 to v. Obviously such graphs exist — the complete graph on v vertices is an example. We shall look at the question, what is the minimum number of edges in a pancyclic graph? Interestingly, this question was "solved", incorrectly, in 1978. A complete solution is not yet known.
This week Brian Alspach concludes his series of talks entitled "The Anatomy Of A Famous Conjecture." We shall be in V27 - note room change.
This involves (in pre-nonstandard analysis times) the development of a simple system of infinites and infinitesmals that help to clarify Cantor's Ternary Set, nonmeasurable sets and Lebesgue integration. The talk will include other memories as a maths student at Newcastle University College, Tighes Hill, from 1959 to 1961.
Brian Alspach will continue his discussion "The Anatomy Of A Famous Conjecture."
This talk will survey some of the classical and recent results concerning operators composed of a projection onto a compact set in time, followed by a projection onto a compact set in frequency. Such "time- and band-limiting" operators were studied by Landau, Slepian, and Pollak in a series of papers published in the Bell Systems Tech. Journal in the early 1960s identifying the eigenfunctions, providing eigenvalue estimates, and describing spaces of "essentially time- and band-limited signals."
Further progress on time- and band-limiting has been intermittent, but genuine recent progress has been made in terms of numerical analysis, sampling theory, and extensions to multiband signals, all driven to some extent by potential applications in communications. After providing an outline of the historical developments in the mathematical theory of time- and bandlimiting, some details of the sampling theory and multiband setting will be given. Part of the latter represents joint work with Jeff Hogan and Scott Izu.
Brian Alspach will continue his discussion "The Anatomy Of A Famous Conjecture."
This talk will discuss opportunities and challenges related to the development and application of operations research techniques to transportation and logistics problems in non-profit settings. Much research has been conducted on transportation and logistics problems in commercial settings where the goal is either to maximize profit or to minimize cost. Significantly less work has been conducted for non-profit applications. In such settings, the objectives are often more difficult to quantify since issues such as equity and sustainability must be considered, yet efficient operations are still crucial. This talk will present several research projects that introduce new approaches tailored to the objectives and constraints unique to non-profit agencies, which are often concerned with obtaining equitable solutions given limited, and often uncertain, budgets, rather than with maximizing profits.
This talk will assess the potential of operations research to address the problems faced by non-profit agencies and attempt to understand why these problems have been understudied within the operations research community. To do so, we will ask the following questions: Are non-profit operations problems rich enough for academic study? and Are solutions to non-profit operations problems applicable to real communities?
Brian Alspach will continue his discussion "The Anatomy Of A Famous Conjecture."
We consider some fundamental generalized Mordell-Tornheim-Witten (MTW) zeta-function values along with their derivatives, and explore connections with multiple-zeta values (MZVs). To achieve these results, we make use of symbolic integration, high precision numerical integration, and some interesting combinatorics and special-function theory.
Our original motivation was to represent previously unresolved constructs such as Eulerian log-gamma integrals. Indeed, we are able to show that all such integrals belong to a vector space over an MTW basis, and we also present, for a substantial subset of this class, explicit closed-form expressions. In the process, we significantly extend methods for high-precision numerical computation of polylogarithms and their derivatives with respect to order. That said, the focus of our paper is the relation between MTW sums and classical polylogarithms. It is the adumbration of these relationships that makes the study significant.
The associated paper (with DH Bailey and RE Crandall) is at http://carmasite.newcastle.edu.au/jon/MTW1.pdf.
Approximation theory is a classical part of the analysis of functions defined on an Euclidean space or its subset and the foundation of its applications, while the problems related to high or infinite dimensions create known challenges even in the setting of Hilbert spaces. The stability (uniform continuity) of a mapping is one of the traditional properties investigated in various branches of pure and applied mathematics and further applications in engineering. Examples include analysis of linear and non-linear PDEs, (short-term) prediction problems and decision-making and data evolution.
We describe the uniform approximation properties of the uniformly continuous mappings between the pairs of Banach and, occasionally, metric spaces from various wide parameterised and non-parameterised classes of spaces with or without the local unconditional structure in a quantitative manner. The striking difference with the finite-dimensional setting is represented by the presence of Tsar'kov's phenomenon. Many tools in use are developed under the scope of our quasi-Euclidean approach. Its idea seems to be relatively natural in light of the compressed sensing and distortion phenomena.
We consider some fundamental generalized Mordell-Tornheim-Witten (MTW) zeta-function values along with their derivatives, and explore connections with multiple-zeta values (MZVs). To achieve these results, we make use of symbolic integration, high precision numerical integration, and some interesting combinatorics and special-function theory.
Our original motivation was to represent previously unresolved constructs such as Eulerian log-gamma integrals. Indeed, we are able to show that all such integrals belong to a vector space over an MTW basis, and we also present, for a substantial subset of this class, explicit closed-form expressions. In the process, we significantly extend methods for high-precision numerical computation of polylogarithms and their derivatives with respect to order. That said, the focus of our paper is the relation between MTW sums and classical polylogarithms. It is the adumbration of these relationships that makes the study significant.
The associated paper (with DH Bailey and RE Crandall) is at http://carmasite.newcastle.edu.au/jon/MTW1.pdf.
The talk will outline some topics associated with constructions for Hadamard matrices, in particular, a relatively simple construction, given by a sum of Kronecker products of ingredient matrices obeying certain conditions. Consideration of the structure of the ingredient matrices leads, on the one hand, to consideration of division algebras and Clifford algebras, and on the other hand, to searching for multisets of {-1,1} ingredient matrices. Structures within the sets of ingredient matrices can make searching more efficent.
In this talk, we consider a general convex feasibility problem in Hilbert space, and analyze a primal-dual pair of problems generated via a duality theory introduced by Svaiter. We present some algorithms and their convergence properties. The focus is a general primal-dual principle for strong convergence of some classes of algorithms. In particular, we give a different viewpoint for the weak-to-strong principle of Bauschke and Combettes. We also discuss how subgradient and proximal type methods fit in this primal-dual setting.
Joint work with Maicon Marques Alves (Universidade Federal de Santa Catarina-Brazil)
Brian Alspach will continue with "The Anatomy Of A Famous Conjecture" this Thursday. One can easily pick up the thread this week without having attended last week, but if you miss this week it will not be easy to join in next week.
12:00-1:00 | Michael Coons (University of Waterloo) |
1:00-2:00 | Claus Koestler (Aberystwyth University) |
2:00-3:00 | Eric Mortenson (The University of Queensland) |
3:00-4:00 | Ekaterina Shemyakova (University of Western Ontario) |
Exceptional Lie group $G_2$ is a beautiful 14-dimensional continuous group, having relations with such diverse notions as triality, 7-dimensional cross product and exceptional holonomy. It was found abstractly by Killing in 1887 (complex case) and then realized as a symmetry group by Engel and Cartan in 1894 (real split case). Later in 1910 Cartan returned to the topic and realized split $G_2$ as the maximal finite-dimensional symmetry algebra of a rank 2 distribution in $\mathbb{R}^5$. In other words, Cartan classified all symmetry groups of Monge equations of the form $y'=f(x,y,z,z',z'')$. I will discuss the higher-dimensional generalization of this fact, based on the joint work with Ian Anderson. Compact real form of $G_2$ was realized by Cartan as the automorphism group of octonions in 1914. In the talk I will also explain how to realize this $G_2$ as the maximal symmetry group of a geometric object.
I have embarked on a project of looking for Hamilton paths in Cayley graphs on finite Coxeter groups. This talk is a report on the progress thus far.
Brian Alspach will continue with "The Anatomy of a Famous Conjecture" this Thursday. One can easily pick up the thread this week without having attended last week, but if you miss this week it will not be easy to join in next week.
In this talk, we consider the structure of maximally monotone operators in Banach space whose domains have nonempty interior and we present new and explicit structure formulas for such operators. Along the way, we provide new proofs of the norm-to-weakstar closedness and property (Q) of these operators (recently established by Voisei). Various applications and limiting examples are given. This is the joint work with Jon Borwein.
This will be an introductory talk which begins by describing the four colour theorem and finite projective planes in the setting of graph decompositions. A problem posed by Ringel at a graph theory meeting in Oberwolfach in 1967 will then be discussed. This problem is now widely known as the Oberwolfach Problem, and is a generalisation of a question asked by Kirkman in 1850. It concerns decompositions of complete graphs into isomorphic copies of spanning regular graphs of degree two.
In my opinion, the most significant unsolved problem in graph decompositions is the cycle double conjecture. This begins a series of talks on this conjecture in terms of background, relations to other problems and partial results.
Simultaneous Localisation and Mapping (SLAM) has become prominent in the field of robotics over the last decade, particularly in application to autonomous systems. SLAM enables any system equipped with exteroceptive (and often inertial) sensors to simultaneously update its own positional estimate and map of the environment by utilising information collected from the surroundings. The solution to the probabilistic SLAM problem can be derived using Bayes Theorem to yield estimates of the system state and covariance. In recursive form, the basic prediction-correction algorithm employs an Extended Kalman Filter (EKF) with Cholesky decomposition for numerical stability during inversion. This talk will present the mathematical formulation and solution of the SLAM problem, along with some algorithms used in implementation. We will then look at some applications of SLAM in the real world and discuss some of the challenges for future development.
We investigate various properties of the sublevel set $\{x : g(x) \leq 1\}$ and the integration of $h$ on this sublevel set when $g$ and $h$ are positively homogeneous functions. For instance, the latter integral reduces to integrating $h\exp(- g)$ on the whole space $\mathbb{R}^n$ (a non-Gaussian integral) and when $g$ is a polynomial, then the volume of the sublevel set is a convex function of its coefficients.
In fact, whenever $h$ is non-negative, the functional $\int \phi(g)h dx$ is a convex function of $g$ for a large class of functions $\phi:\mathbb{R}_{+} \to \mathbb{R}$. We also provide a numerical approximation scheme to compute the volume or integrate $h$ (or, equivalently, to approximate the associated non-Gaussian integral). We also show that finding the sublevel set $\{x : g(x) \leq 1\}$ of minimum volume that contains some given subset $K$ is a (hard) convex optimization problem for which we also propose two convergent numerical schemes. Finally, we provide a Gaussian-like property of non-Gaussian integrals for homogeneous polynomials that are sums of squares and critical points of a specific function.
In this talk, we consider the automorphism groups of the Cayley graph with respect to the Coxeter generators and the Davis complex of an arbitrary Coxeter group. We determine for which Coxeter groups these automorphism groups are discrete. In the case where they are discrete, we express them as semidirect products of two obvious families of automorphisms. This extends a result of Haglund and Paulin.
In this paper, we construct maximally monotone operators that are not of Gossez's dense-type (D) in many nonreflexive spaces. Many of these operators also fail to possess the Brønsted-Rockafellar (BR) property. Using these operators, we show that the partial inf-convolution of two BC-functions will not always be a BC-function. This provides a negative answer to a challenging question posed by Stephen Simons. Among other consequences, we deduce that every Banach space which contains an isomorphic copy of the James space J or its dual $J^*$, or of $c_0$ or its dual $l^1$ admits a non type (D) operator.
The problem posed by Hilbert in 1900 was resolved in the 1930s independently by A. Gelfond and Th. Schneider. The statement is that $a^b$ is transcendental for algebraic $a \ne 0,1$ and irrational algebraic $b$. The aim of the two 2-hour lectures is to give a proof of this result using the so-called method of interpolation determinants.
The modernization of infrastructure networks requires coordinated planning and control. Considering traffic networks and electricity grids raises similar issues on how to achieve substantial new capabilities of effectiveness and efficiency. For instance, power grids need to integrate renewable energy sources and electric vehicles. It is clear that all this can only be achieved by greater reliance on systematic planning in the presence of uncertainty and sensing, communications, computing and control on an unprecedented scale, these days captured in the term "smart grids". This talk will outline current research on planning future grids and control of smart grids. In particular, the possible roles of network science will be emphasized and the challenges arising.
The Mathematics and Statistics Learning Centre was established at the University of Melbourne over a decade ago, to respond to the needs of, initially, first year students of mathematics and statistics. The role of the centre and its Director has grown. The current Director, Dr Deborah King, will expound upon her role in the Centre.
Symbolic and numeric computation have been distinguished by definition: numeric computation puts numerical values in its variables as soon as possible, symbolic computation as late as possible. Chebfun blurs this distinction, aiming for the speed of numerics with the generality and flexibility of symbolics. What happens when someone who has used both Maple and Matlab for decades, and has thereby absorbed the different fundamental assumptions into a "computational stance", tries to use Chebfun to solve a variety of computational problems? This talk reports on some of the outcomes.
In this talk, we present a numerical method for a class of generalized inequality constrained integer linear programming (GILP) problems that includes the usual mixed-integer linear programming (MILP) problems as special cases. Instead of restricting certain variables to integer values as in MILP, we require in these GILP problems that some of the constraint functions take integer values. We present a tighten-and-branch method that has a number of advantages over the usual branch-and-cut algorithms. This includes the ability of keeping the number of constraints unchanged for all subproblems throughout the solution process and the capability of eliminating equality constraints. In addition, the method provides an algorithm framework that allows the existing cutting-plane techniques to be incorporated into the tightening process. As a demonstration, we will solve a well-known "hard ILP problem".
Selection theorems assert that one can pick a well behaved function from a corresponding multifunction. They play a very important role in modern optimization theory. In Part I, I will survey their structure and some applications before sketching some important applications and open research problems in Part II.
The celebrated Littlewood conjecture in Diophantine approximation concerns the simultaneous approximation of two real numbers by rationals with the same denominator. A cousin of this conjecture is the mixed Littlewood conjecture of de Mathan and Teulié, which is concerned with the approximation of a single real number, but where some denominators are preferred to others.
In the talk, we will derive a metrical result extending work of Pollington and Velani on the Littlewood conjecture. Our result implies the existence of an abundance of numbers satisfying both conjectures.
Selection theorems assert that one can pick a well behaved function from a corresponding multifunction. They play a very important role in modern optimization theory. I will survey their structure and some applications before sketching some important open research problems.
Network infrastructures are a common phenomenon. Network upgrades and expansions typically occur over time due to budget constraints. We introduce a class of incremental network design problems that allow investigation of many of the key issues related to the choice and timing of infrastructure expansions and their impact on the costs of the activities performed on that infrastructure. We focus on the simplest variant: incremental network design with shortest paths, and show that even its simplest variant is NP-hard. We investigate structural properties of optimal solutions, we analyze the worst-case performance of natural greedy heuristics, we derive a 4-approximation algorithm, and we present an integer program formulation and conduct a small computational study.
Joint work withParabolic obstacle problems find applications in the financial markets for pricing American put options. We present a mixed and an equivalent variational inequality hp-interior penalty DG (IPDG) method combined with an hp-time DG (TDG) method to solve parabolic obstacle problems approximatively. The contact conditions are resolved by a biorthogonal Lagrange multiplier and are component-wise decoupled. These decoupled contact conditions are equivlent to finding the root of a non-linear complementary function. This non-linear problem can in turn be solved efficiently by a semi-smooth Newton method. For the hp-adaptivity a p-hierarchical error estimator in conjunction with a local analyticity estimate is employed. For the considered stationary problem, this leads to exponential convergence, and for the instationary problem to greatly improved convergence rates. Numerical experiments are given demonstrating the strengths and limitations of the approaches.
The Discrete Mathematics Instructional Seminar will be getting underway again this Thursday.
We start this talk by introducing some basic definitions and properties relative to geodesic in the setting of metric spaces. After showing some important examples of geodesic metric spaces (which will be used through this talk), we shall define the concept of firmly nonexpansive mappings and we shall prove the existence, under mild conditions, of periodic points and fixed points for this class of mappings. Some of these results unify and generalize previous ones. We shall give a result relative to the $\Delta$-convergence to a fixed point of Picard iterates for firmly nonexpansive mappings, which is obtained from the asymptotic regularity of this class of iterates. Moreover, we shall get an effective rate of asymptotic regularity for firmly nonexpansive mappings (this result is new, as far as we know, even in linear spaces). Finally, we shall apply our results to a minimization problem. More precisely, we shall prove the $\Delta$-convergence to a minimizer of a proximal point-like algorithm when applied to a convex proper lower semi-continuous function defined on a CAT(0) space.
We present a technique for enhancing a progressive hedging-based metaheuristic for a network design problem that models demand uncertainty with scenarios. The technique uses machine learning methods to cluster scenarios and, subsequently, the metaheuristic repeatedly solves multi-scenario subproblems (as opposed to single-scenario subproblems as is done in existing work). With a computational study we see that solving multi-scenario subproblems leads to a significant increase in solution quality and that how you construct these multi-scenario subproblems directly impacts solution quality. We also discuss how scenario grouping can be leveraged in a Benders' approach and show preliminary results of its effectiveness. This is joint work with Theo Crainic and Walter Rei at University of Quebec at Montreal.
Power line communication has been proposed as a possible solution to the "last mile" problem in telecommunications i.e. providing economical high speed telecommunications to millions of end users. As well as the usual background interference (noise), two other types of noise must also be considered for any successful practical implementation of power line communication. Coding schemes have traditionally been designed to deal only with background noise, and in such schemes it is often assumed that background noise affects symbols in codewords independently at random. Recently, however, new schemes have been proposed to deal with the extra considerations in power line communication. We introduce neighbour transitive codes as a group theoretic analogue to the assumption that background noise affects symbols independently at random. We also classify a family of neighbour transitive codes, and show that such codes have the necessary properties to be useful in power line communication.
Integrability theory is the area of mathematics in which methods are developed for the exact solution of partial differential equations, as well as for the study of their properties. We concentrate on PDEs appearing in Physics and other applications. Darboux transformations constitute one of the important methods used in integrability theory and, as well as being a method for the exact solution of linear PDEs, they are an essential part of the method of Lax pairs, used for the solution of non-linear PDEs. A large series of Darboux transformations may be constructed using Wronskians built from some number of individual solutions of the original PDE. In this talk we prove a long-standing conjecture that this construction captures all possible Darboux transformations for transformations of order two, while for transformations of order one the construction captures everything but two Laplace transformations. An introduction into the theory will be provided.
Let $K$ be a complete discrete valuation field of characteristic zero with residue field $k_K$ of characteristic $p > 0$. Let $L/K$ be a finite Galois extension with Galois group $G = \text{Gal}(L/K)$ and suppose that the induced extension of residue fields $k_L/k_K$ is separable. Let $W_n(.)$ denote the ring of $p$-typical Witt vectors of length $n$. Hesselholt [Galois cohomology of Witt vectors of algebraic integers, Math. Proc. Cambridge Philos. Soc. 137(3) (2004), 551557] conjectured that the pro-abelian group ${H^1(G,W_n(O_L))}_{n>0}$ is isomorphic to zero. Hogadi and Pisolkar [On the cohomology of Witt vectors of $p$-adic integers and a conjecture of Hesselholt, J. Number Theory 131(10) (2011), 17971807] have recently provided a proof of this conjecture. In this talk, we present a simplified version of the original proof which avoids many of the calculations present in that version.
Two sets of functions are studied to ascertain whether they are Stieltjes functions and whether they are completely monotonic. The first group of functions are all built from the Lambert $W$ function. The $W$ function will be reviewed briefly. It will be shown that $W$ is Bernstein and various functions containing $W$ are Stieltjes. Explicit expressions for the Stieltjes transforms are obtained. We also give some new results regarding general Stieltjes functions.
The second set of functions were posed as a challenge by Christian Berg in 2002. The functions are $(1+a/x)^{(x+b)}$ for various $a$ and $b$. We show that the functions is Stieltjes for some ranges of $a,b$ and investigate experimentally complete monotonicity for a larger range. We claim an accurate experimental value for the range.
My co-authors are Rob Corless, Peter Borwein, German Kalugin and Songxin Liang.
Graph closures became recently an important tool in Hamiltonian Graph Theory since the use of closure techniques often substantially simplifies the structure of a graph under consideration while preserving some of its prescribed properties (usually of Hamiltonian type). In the talk we show basic ideas of construction of some graph closures for claw-free graphs and techniques that allow to reduce the problem to cubic graphs. The approach will be illustrated on a recently introduced closure concept for Hamilton-connectedness in claw-free graphs and, as an application, an asymptotically sharp Ore-type degree condition for Hamilton-connectedness in claw-free graphs will be obtained.
We consider a general class of convex optimization problems in which one seeks to minimize a strongly convex function over a closed and convex set which is by itself an optimal set of another convex problem. We introduce a gradient-based method, called the minimal norm gradient method, for solving this class of problems, and establish the convergence of the sequence generated by the algorithm as well as a rate of convergence of the sequence of function values. A portfolio optimization example is given in order to illustrate our results.
Having been constructed as trading strategies, option spreads are also used in margin calculations for offsetting positions in options. All option spreads that appear in trading and margining practice have two, three or four legs. As shown in Rudd and Schroeder (Management Sci, 1982), the problem of margining option portfolios where option spreads with two legs are used for offsetting can be solved in polynomial time by network flow algorithms. However, spreads with only two legs do not provide sufficient accuracy in measuring risk. Therefore, margining practice also employs spreads with three and four legs. A polynomial-time solution to the extension of the problem where option spreads with three and four legs are also used for offsetting is not known. We propose a heuristic network-flow algorithm for this extension and present a computational study that demonstrates high efficiency of the proposed algorithm in margining practice.
We consider the problem of packing ellipsoids of different size and shape in an ellipsoidal container so as to minimize a measure of total overlap. The motivating application is chromosome organization in the human cell nucleus. A bilevel optimization formulation is described, together with an algorithm for the general case and a simpler algorithm for the special case in which all ellipsoids are in fact spheres. We prove convergence to stationary points of this nonconvex problem, and describe computational experience. The talk describes joint work with Caroline Uhler (IST, Vienna).
We prove the it is NP-hard for a coalition of two manipulators to compute how to manipulate the Borda voting rule. This resolves one of the last open problems in the computational complexity of manipulating common voting rules. Because of this NP-hardness, we treat computing a manipulation as an approximation problem where we try to minimize the number of manipulators. Based on ideas from bin packing and multiprocessor scheduling, we propose two new approximation methods to compute manipulations of the Borda rule. Experiments show that these methods significantly outperform the previous best known approximation method. We are able to find optimal manipulations in almost all the randomly generated elections tested. Our results suggest that, whilst computing a manipulation of the Borda rule by a coalition is NP-hard, computational complexity may provide only a weak barrier against manipulation in practice.
We also consider Nanson’s and Baldwin’s voting rules that select a winner by successively eliminating candidates with low Borda scores. We theoretically and experimentally demonstrate that these rules are significantly more difficult to manipulate compared to Borda rule. In particular, with unweighted votes, it is NP-hard to manipulate either rule with one manipulator, whilst with weighted votes, it is NP-hard to manipulate either rule with a small number of candidates and a coalition of manipulators.