@article{8419, abstract = {In this survey, we provide a concise introduction to convex billiards and describe some recent results, obtained by the authors and collaborators, on the classification of integrable billiards, namely the so-called Birkhoff conjecture. This article is part of the theme issue ‘Finite dimensional integrable systems: new trends and methods’.}, author = {Kaloshin, Vadim and Sorrentino, Alfonso}, issn = {1364-503X}, journal = {Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences}, keywords = {General Engineering, General Physics and Astronomy, General Mathematics}, number = {2131}, publisher = {The Royal Society}, title = {{On the integrability of Birkhoff billiards}}, doi = {10.1098/rsta.2017.0419}, volume = {376}, year = {2018}, } @article{8420, abstract = {We show that in the space of all convex billiard boundaries, the set of boundaries with rational caustics is dense. More precisely, the set of billiard boundaries with caustics of rotation number 1/q is polynomially sense in the smooth case, and exponentially dense in the analytic case.}, author = {Kaloshin, Vadim and Zhang, Ke}, issn = {0951-7715}, journal = {Nonlinearity}, keywords = {Mathematical Physics, General Physics and Astronomy, Applied Mathematics, Statistical and Nonlinear Physics}, number = {11}, pages = {5214--5234}, publisher = {IOP Publishing}, title = {{Density of convex billiards with rational caustics}}, doi = {10.1088/1361-6544/aadc12}, volume = {31}, year = {2018}, } @article{11670, abstract = {Auctions are widely used on the Web. Applications range from sponsored search to platforms such as eBay. In these and in many other applications the auctions in use are single-/multi-item auctions with unit demand. The main drawback of standard mechanisms for this type of auctions, such as VCG and GSP, is the limited expressiveness that they offer to the bidders. The General Auction Mechanism (GAM) of Aggarwal et al. [2009] takes a first step toward addressing the problem of limited expressiveness by computing a bidder optimal, envy-free outcome for linear utility functions with identical slopes and a single discontinuity per bidder-item pair. We show that in many practical situations this does not suffice to adequately model the preferences of the bidders, and we overcome this problem by presenting the first mechanism for piecewise linear utility functions with nonidentical slopes and multiple discontinuities. Our mechanism runs in polynomial time. Like GAM it is incentive compatible for inputs that fulfill a certain nondegeneracy assumption, but our requirement is more general than the requirement of GAM. For discontinuous utility functions that are nondegenerate as well as for continuous utility functions the outcome of our mechanism is a competitive equilibrium. We also show how our mechanism can be used to compute approximately bidder optimal, envy-free outcomes for a general class of continuous utility functions via piecewise linear approximation. Finally, we prove hardness results for even more expressive settings.}, author = {Dütting, Paul and Henzinger, Monika H and Weber, Ingmar}, issn = {2167-8383}, journal = {ACM Transactions on Economics and Computation}, keywords = {Computational Mathematics, Marketing, Economics and Econometrics, Statistics and Probability, Computer Science (miscellaneous)}, number = {1}, publisher = {Association for Computing Machinery}, title = {{An expressive mechanism for auctions on the web}}, doi = {10.1145/2716312}, volume = {4}, year = {2015}, } @article{8498, abstract = {In the present note we announce a proof of a strong form of Arnold diffusion for smooth convex Hamiltonian systems. Let ${\mathbb T}^2$ be a 2-dimensional torus and B2 be the unit ball around the origin in ${\mathbb R}^2$ . Fix ρ > 0. Our main result says that for a 'generic' time-periodic perturbation of an integrable system of two degrees of freedom $H_0(p)+\varepsilon H_1(\theta,p,t),\quad \ \theta\in {\mathbb T}^2,\ p\in B^2,\ t\in {\mathbb T}={\mathbb R}/{\mathbb Z}$ , with a strictly convex H0, there exists a ρ-dense orbit (θε, pε, t)(t) in ${\mathbb T}^2 \times B^2 \times {\mathbb T}$ , namely, a ρ-neighborhood of the orbit contains ${\mathbb T}^2 \times B^2 \times {\mathbb T}$ . Our proof is a combination of geometric and variational methods. The fundamental elements of the construction are the usage of crumpled normally hyperbolic invariant cylinders from [9], flower and simple normally hyperbolic invariant manifolds from [36] as well as their kissing property at a strong double resonance. This allows us to build a 'connected' net of three-dimensional normally hyperbolic invariant manifolds. To construct diffusing orbits along this net we employ a version of the Mather variational method [41] equipped with weak KAM theory [28], proposed by Bernard in [7].}, author = {Kaloshin, Vadim and Zhang, K}, issn = {0951-7715}, journal = {Nonlinearity}, keywords = {Mathematical Physics, General Physics and Astronomy, Applied Mathematics, Statistical and Nonlinear Physics}, number = {8}, pages = {2699--2720}, publisher = {IOP Publishing}, title = {{Arnold diffusion for smooth convex systems of two and a half degrees of freedom}}, doi = {10.1088/0951-7715/28/8/2699}, volume = {28}, year = {2015}, } @article{8459, abstract = {Nuclear magnetic resonance (NMR) is a powerful tool for observing the motion of biomolecules at the atomic level. One technique, the analysis of relaxation dispersion phenomenon, is highly suited for studying the kinetics and thermodynamics of biological processes. Built on top of the relax computational environment for NMR dynamics is a new dispersion analysis designed to be comprehensive, accurate and easy-to-use. The software supports more models, both numeric and analytic, than current solutions. An automated protocol, available for scripting and driving the graphical user interface (GUI), is designed to simplify the analysis of dispersion data for NMR spectroscopists. Decreases in optimization time are granted by parallelization for running on computer clusters and by skipping an initial grid search by using parameters from one solution as the starting point for another —using analytic model results for the numeric models, taking advantage of model nesting, and using averaged non-clustered results for the clustered analysis.}, author = {Morin, Sébastien and Linnet, Troels E and Lescanne, Mathilde and Schanda, Paul and Thompson, Gary S and Tollinger, Martin and Teilum, Kaare and Gagné, Stéphane and Marion, Dominique and Griesinger, Christian and Blackledge, Martin and d’Auvergne, Edward J}, issn = {1367-4803}, journal = {Bioinformatics}, keywords = {Statistics and Probability, Computational Theory and Mathematics, Biochemistry, Molecular Biology, Computational Mathematics, Computer Science Applications}, number = {15}, pages = {2219--2220}, publisher = {Oxford University Press}, title = {{Relax: The analysis of biomolecular kinetics and thermodynamics using NMR relaxation dispersion data}}, doi = {10.1093/bioinformatics/btu166}, volume = {30}, year = {2014}, } @article{8500, abstract = {The main model studied in this paper is a lattice of pendula with a nearest‐neighbor coupling. If the coupling is weak, then the system is near‐integrable and KAM tori fill most of the phase space. For all KAM trajectories the energy of each pendulum stays within a narrow band for all time. Still, we show that for an arbitrarily weak coupling of a certain localized type, the neighboring pendula can exchange energy. In fact, the energy can be transferred between the pendula in any prescribed way.}, author = {Kaloshin, Vadim and Levi, Mark and Saprykina, Maria}, issn = {0010-3640}, journal = {Communications on Pure and Applied Mathematics}, keywords = {Applied Mathematics, General Mathematics}, number = {5}, pages = {748--775}, publisher = {Wiley}, title = {{Arnol′d diffusion in a pendulum lattice}}, doi = {10.1002/cpa.21509}, volume = {67}, year = {2014}, } @article{8501, abstract = {In this paper, we study small perturbations of a class of non-convex integrable Hamiltonians with two degrees of freedom, and we prove a result of diffusion for an open and dense set of perturbations, with an optimal time of diffusion which grows linearly with respect to the inverse of the size of the perturbation.}, author = {Bounemoura, Abed and Kaloshin, Vadim}, issn = {1609-3321}, journal = {Moscow Mathematical Journal}, keywords = {General Mathematics}, number = {2}, pages = {181--203}, publisher = {Independent University of Moscow}, title = {{Generic fast diffusion for a class of non-convex Hamiltonians with two degrees of freedom}}, doi = {10.17323/1609-4514-2014-14-2-181-203}, volume = {14}, year = {2014}, } @article{9166, abstract = {Light-activated self-propelled colloids are synthesized and their active motion is studied using optical microscopy. We propose a versatile route using different photoactive materials, and demonstrate a multiwavelength activation and propulsion. Thanks to the photoelectrochemical properties of two semiconductor materials (α-Fe2O3 and TiO2), a light with an energy higher than the bandgap triggers the reaction of decomposition of hydrogen peroxide and produces a chemical cloud around the particle. It induces a phoretic attraction with neighbouring colloids as well as an osmotic self-propulsion of the particle on the substrate. We use these mechanisms to form colloidal cargos as well as self-propelled particles where the light-activated component is embedded into a dielectric sphere. The particles are self-propelled along a direction otherwise randomized by thermal fluctuations, and exhibit a persistent random walk. For sufficient surface density, the particles spontaneously form ‘living crystals’ which are mobile, break apart and reform. Steering the particle with an external magnetic field, we show that the formation of the dense phase results from the collisions heads-on of the particles. This effect is intrinsically non-equilibrium and a novel principle of organization for systems without detailed balance. Engineering families of particles self-propelled by different wavelength demonstrate a good understanding of both the physics and the chemistry behind the system and points to a general route for designing new families of self-propelled particles.}, author = {Palacci, Jérémie A and Sacanna, S. and Kim, S.-H. and Yi, G.-R. and Pine, D. J. and Chaikin, P. M.}, issn = {1471-2962}, journal = {Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences}, keywords = {General Engineering, General Physics and Astronomy, General Mathematics}, number = {2029}, publisher = {The Royal Society}, title = {{Light-activated self-propelled colloids}}, doi = {10.1098/rsta.2013.0372}, volume = {372}, year = {2014}, } @article{8504, abstract = {In this paper we present a surprising example of a Cr unimodal map of an interval f:I→I whose number of periodic points Pn(f)=∣{x∈I:fnx=x}∣ grows faster than any ahead given sequence along a subsequence nk=3k. This example also shows that ‘non-flatness’ of critical points is necessary for the Martens–de Melo–van Strien theorem [M. Martens, W. de Melo and S. van Strien. Julia–Fatou–Sullivan theory for real one-dimensional dynamics. Acta Math.168(3–4) (1992), 273–318] to hold.}, author = {Kaloshin, Vadim and KOZLOVSKI, O. S.}, issn = {0143-3857}, journal = {Ergodic Theory and Dynamical Systems}, keywords = {Applied Mathematics, General Mathematics}, number = {1}, pages = {159--165}, publisher = {Cambridge University Press}, title = {{A Cr unimodal map with an arbitrary fast growth of the number of periodic points}}, doi = {10.1017/s0143385710000817}, volume = {32}, year = {2012}, } @article{8505, abstract = {The classical principle of least action says that orbits of mechanical systems extremize action; an important subclass are those orbits that minimize action. In this paper we utilize this principle along with Aubry-Mather theory to construct (Birkhoff) regions of instability for a certain three-body problem, given by a Hamiltonian system of 2 degrees of freedom. We believe that these methods can be applied to construct instability regions for a variety of Hamiltonian systems with 2 degrees of freedom. The Hamiltonian model we consider describes dynamics of a Sun-Jupiter-comet system, and under some simplifying assumptions, we show the existence of instabilities for the orbit of the comet. In particular, we show that a comet which starts close to an orbit in the shape of an ellipse of eccentricity e=0.66 can increase in eccentricity up to e=0.96. In the sequels to this paper, we extend the result to beyond e=1 and show the existence of ejection orbits. Such orbits are initially well within the range of our solar system. This might give an indication of why most objects rotating around the Sun in our solar system have relatively low eccentricity.}, author = {Galante, Joseph and Kaloshin, Vadim}, issn = {0012-7094}, journal = {Duke Mathematical Journal}, keywords = {General Mathematics}, number = {2}, pages = {275--327}, publisher = {Duke University Press}, title = {{Destruction of invariant curves in the restricted circular planar three-body problem by using comparison of action}}, doi = {10.1215/00127094-1415878}, volume = {159}, year = {2011}, } @article{8508, abstract = {We study generic unfoldings of homoclinic tangencies of two-dimensional area-preserving diffeomorphisms (conservative New house phenomena) and show that they give rise to invariant hyperbolic sets of arbitrarily large Hausdorff dimension. As applications, we discuss the size of the stochastic layer of a standard map and the Hausdorff dimension of invariant hyperbolic sets for certain restricted three-body problems. We avoid involved technical details and only concentrate on the ideas of the proof of the presented results.}, author = {Gorodetski, Anton and Kaloshin, Vadim}, issn = {0081-5438}, journal = {Proceedings of the Steklov Institute of Mathematics}, keywords = {Mathematics (miscellaneous)}, number = {1}, pages = {76--90}, publisher = {Springer Nature}, title = {{Conservative homoclinic bifurcations and some applications}}, doi = {10.1134/s0081543809040063}, volume = {267}, year = {2009}, } @article{8509, abstract = {The goal of this paper is to present to nonspecialists what is perhaps the simplest possible geometrical picture explaining the mechanism of Arnold diffusion. We choose to speak of a specific model—that of geometric rays in a periodic optical medium. This model is equivalent to that of a particle in a periodic potential in ${\mathbb R}^{n}$ with energy prescribed and to the geodesic flow in a Riemannian metric on ${\mathbb R}^{n} $.}, author = {Kaloshin, Vadim and Levi, Mark}, issn = {0036-1445}, journal = {SIAM Review}, keywords = {Theoretical Computer Science, Applied Mathematics, Computational Mathematics}, number = {4}, pages = {702--720}, publisher = {Society for Industrial & Applied Mathematics}, title = {{Geometry of Arnold diffusion}}, doi = {10.1137/070703235}, volume = {50}, year = {2008}, } @article{8510, abstract = {In this paper, using the ideas of Bessi and Mather, we present a simple mechanical system exhibiting Arnold diffusion. This system of a particle in a small periodic potential can be also interpreted as ray propagation in a periodic optical medium with a near-constant index of refraction. Arnold diffusion in this context manifests itself as an arbitrary finite change of direction for nearly constant index of refraction.}, author = {Kaloshin, Vadim and Levi, Mark}, issn = {0273-0979}, journal = {Bulletin of the American Mathematical Society}, keywords = {Applied Mathematics, General Mathematics}, number = {3}, pages = {409--427}, publisher = {American Mathematical Society}, title = {{An example of Arnold diffusion for near-integrable Hamiltonians}}, doi = {10.1090/s0273-0979-08-01211-1}, volume = {45}, year = {2008}, } @article{8511, abstract = {Here we study an amazing phenomenon discovered by Newhouse [S. Newhouse, Non-density of Axiom A(a) on S2, in: Proc. Sympos. Pure Math., vol. 14, Amer. Math. Soc., 1970, pp. 191–202; S. Newhouse, Diffeomorphisms with infinitely many sinks, Topology 13 (1974) 9–18; S. Newhouse, The abundance of wild hyperbolic sets and nonsmooth stable sets of diffeomorphisms, Publ. Math. Inst. Hautes Études Sci. 50 (1979) 101–151]. It turns out that in the space of Cr smooth diffeomorphisms Diffr(M) of a compact surface M there is an open set U such that a Baire generic diffeomorphism f ∈ U has infinitely many coexisting sinks. In this paper we make a step towards understanding “how often does a surface diffeomorphism have infinitely many sinks.” Our main result roughly says that with probability one for any positive D a surface diffeomorphism has only finitely many localized sinks either of cyclicity bounded by D or those whose period is relatively large compared to its cyclicity. It verifies a particular case of Palis’ Conjecture saying that even though diffeomorphisms with infinitely many coexisting sinks are Baire generic, they have probability zero. One of the key points of the proof is an application of Newton Interpolation Polynomials to study the dynamics initiated in [V. Kaloshin, B. Hunt, A stretched exponential bound on the rate of growth of the number of periodic points for prevalent diffeomorphisms I, Ann. of Math., in press, 92 pp.; V. Kaloshin, A stretched exponential bound on the rate of growth of the number of periodic points for prevalent diffeomorphisms II, preprint, 85 pp.].}, author = {Gorodetski, A. and Kaloshin, Vadim}, issn = {0001-8708}, journal = {Advances in Mathematics}, keywords = {General Mathematics}, number = {2}, pages = {710--797}, publisher = {Elsevier}, title = {{How often surface diffeomorphisms have infinitely many sinks and hyperbolicity of periodic points near a homoclinic tangency}}, doi = {10.1016/j.aim.2006.03.012}, volume = {208}, year = {2007}, } @article{8517, abstract = {We consider the evolution of a connected set on the plane carried by a space periodic incompressible stochastic flow. While for almost every realization of the stochastic flow at time t most of the particles are at a distance of order equation image away from the origin, there is a measure zero set of points that escape to infinity at the linear rate. We study the set of points visited by the original set by time t and show that such a set, when scaled down by the factor of t, has a limiting nonrandom shape.}, author = {Dolgopyat, Dmitry and Kaloshin, Vadim and Koralov, Leonid}, issn = {0010-3640}, journal = {Communications on Pure and Applied Mathematics}, keywords = {Applied Mathematics, General Mathematics}, number = {9}, pages = {1127--1158}, publisher = {Wiley}, title = {{A limit shape theorem for periodic stochastic dispersion}}, doi = {10.1002/cpa.20032}, volume = {57}, year = {2004}, } @article{8519, author = {Kaloshin, Vadim}, issn = {0020-9910}, journal = {Inventiones mathematicae}, keywords = {General Mathematics}, number = {3}, pages = {451--512}, publisher = {Springer Nature}, title = {{The existential Hilbert 16-th problem and an estimate for cyclicity of elementary polycycles}}, doi = {10.1007/s00222-002-0244-9}, volume = {151}, year = {2003}, } @article{8521, abstract = {We continue the previous article's discussion of bounds, for prevalent diffeomorphisms of smooth compact manifolds, on the growth of the number of periodic points and the decay of their hyperbolicity as a function of their period $n$. In that article we reduced the main results to a problem, for certain families of diffeomorphisms, of bounding the measure of parameter values for which the diffeomorphism has (for a given period $n$) an almost periodic point that is almost nonhyperbolic. We also formulated our results for $1$-dimensional endomorphisms on a compact interval. In this article we describe some of the main techniques involved and outline the rest of the proof. To simplify notation, we concentrate primarily on the $1$-dimensional case.}, author = {Kaloshin, Vadim and Hunt, Brian R.}, issn = {1079-6762}, journal = {Electronic Research Announcements of the American Mathematical Society}, keywords = {General Mathematics}, number = {5}, pages = {28--36}, publisher = {American Mathematical Society}, title = {{A stretched exponential bound on the rate of growth of the number of periodic points for prevalent diffeomorphisms II}}, doi = {10.1090/s1079-6762-01-00091-9}, volume = {7}, year = {2001}, } @article{8522, abstract = {For diffeomorphisms of smooth compact manifolds, we consider the problem of how fast the number of periodic points with period $n$grows as a function of $n$. In many familiar cases (e.g., Anosov systems) the growth is exponential, but arbitrarily fast growth is possible; in fact, the first author has shown that arbitrarily fast growth is topologically (Baire) generic for $C^2$ or smoother diffeomorphisms. In the present work we show that, by contrast, for a measure-theoretic notion of genericity we call ``prevalence'', the growth is not much faster than exponential. Specifically, we show that for each $\delta > 0$, there is a prevalent set of ( $C^{1+\rho}$ or smoother) diffeomorphisms for which the number of period $n$ points is bounded above by $\operatorname{exp}(C n^{1+\delta})$ for some $C$ independent of $n$. We also obtain a related bound on the decay of the hyperbolicity of the periodic points as a function of $n$. The contrast between topologically generic and measure-theoretically generic behavior for the growth of the number of periodic points and the decay of their hyperbolicity shows this to be a subtle and complex phenomenon, reminiscent of KAM theory.}, author = {Kaloshin, Vadim and Hunt, Brian R.}, issn = {1079-6762}, journal = {Electronic Research Announcements of the American Mathematical Society}, keywords = {General Mathematics}, number = {4}, pages = {17--27}, publisher = {American Mathematical Society}, title = {{A stretched exponential bound on the rate of growth of the number of periodic points for prevalent diffeomorphisms I}}, doi = {10.1090/s1079-6762-01-00090-7}, volume = {7}, year = {2001}, } @article{11683, abstract = {The vertex connectivity κ of a graph is the smallest number of vertices whose deletion separates the graph or makes it trivial. We present the fastest known deterministic algorithm for finding the vertex connectivity and a corresponding separator. The time for a digraph having n vertices and m edges is O(min{κ3 + n, κn}m); for an undirected graph the term m can be replaced by κn. A randomized algorithm finds κ with error probability 1/2 in time O(nm). If the vertices have nonnegative weights the weighted vertex connectivity is found in time O(κ1nmlog(n2/m)) where κ1 ≤ m/n is the unweighted vertex connectivity or in expected time O(nmlog(n2/m)) with error probability 1/2. The main algorithm combines two previous vertex connectivity algorithms and a generalization of the preflow-push algorithm of Hao and Orlin (1994, J. Algorithms17, 424–446) that computes edge connectivity.}, author = {Henzinger, Monika H and Rao, Satish and Gabow, Harold N.}, issn = {0196-6774}, journal = {Journal of Algorithms}, keywords = {Computational Theory and Mathematics, Computational Mathematics, Control and Optimization}, number = {2}, pages = {222--250}, publisher = {Elsevier}, title = {{Computing vertex connectivity: New bounds from old techniques}}, doi = {10.1006/jagm.1999.1055}, volume = {34}, year = {2000}, } @article{8527, abstract = {We introduce a new potential-theoretic definition of the dimension spectrum of a probability measure for q > 1 and explain its relation to prior definitions. We apply this definition to prove that if and is a Borel probability measure with compact support in , then under almost every linear transformation from to , the q-dimension of the image of is ; in particular, the q-dimension of is preserved provided . We also present results on the preservation of information dimension and pointwise dimension. Finally, for and q > 2 we give examples for which is not preserved by any linear transformation into . All results for typical linear transformations are also proved for typical (in the sense of prevalence) continuously differentiable functions.}, author = {Hunt, Brian R and Kaloshin, Vadim}, issn = {0951-7715}, journal = {Nonlinearity}, keywords = {Mathematical Physics, General Physics and Astronomy, Applied Mathematics, Statistical and Nonlinear Physics}, number = {5}, pages = {1031--1046}, publisher = {IOP Publishing}, title = {{How projections affect the dimension spectrum of fractal measures}}, doi = {10.1088/0951-7715/10/5/002}, volume = {10}, year = {1997}, }