skip to main content

Title: Simple Multi-Pass Streaming Algorithms for Skyline Points and Extreme Points
Award ID(s):
Author(s) / Creator(s):
Date Published:
Journal Name:
Proc. Sympos. Theoretical Aspects of Computer Science (STACS)
Page Range / eLocation ID:
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. Research has documented increasing partisan division and extremist positions that are more pronounced among political elites than among voters. Attention has now begun to focus on how polarization might be attenuated. We use a general model of opinion change to see if the self-reinforcing dynamics of influence and homophily may be characterized by tipping points that make reversibility problematic. The model applies to a legislative body or other small, densely connected organization, but does not assume country-specific institutional arrangements that would obscure the identification of fundamental regularities in the phase transitions. Agents in the model have initially random locations in a multidimensional issue space consisting of membership in one of two equal-sized parties and positions on 10 issues. Agents then update their issue positions by moving closer to nearby neighbors and farther from those with whom they disagree, depending on the agents’ tolerance of disagreement and strength of party identification compared to their ideological commitment to the issues. We conducted computational experiments in which we manipulated agents’ tolerance for disagreement and strength of party identification. Importantly, we also introduced exogenous shocks corresponding to events that create a shared interest against a common threat (e.g., a global pandemic). Phase diagrams of political polarization reveal difficult-to-predict transitions that can be irreversible due to asymmetric hysteresis trajectories. We conclude that future empirical research needs to pay much closer attention to the identification of tipping points and the effectiveness of possible countermeasures. 
    more » « less
  2. null (Ed.)
  3. Abstract

    In this paper, we investigate an arithmetic analogue of the gonality of a smooth projective curve $C$ over a number field $k$: the minimal $e$ such that there are infinitely many points $P \in C(\bar{k})$ with $[k(P):k] \leqslant e$. Developing techniques that make use of an auxiliary smooth surface containing the curve, we show that this invariant can take any value subject to constraints imposed by the gonality. Building on work of Debarre–Klassen, we show that this invariant is equal to the gonality for all sufficiently ample curves on a surface $S$ with trivial irregularity.

    more » « less
  4. We define an action of words in[m]n[m]^nonRm{\mathbb {R}}^mto give a new characterization of rational parking functions—they are exactly those words whose action has a fixed point. We use this viewpoint to give a simple definition of Gorsky, Mazin, and Vazirani’s zeta map on rational parking functions whenmmandnnare coprime [Trans. Amer. Math. Soc. 368 (2016), pp. 8403–8445], and prove that this zeta map is invertible. A specialization recovers Loehr and Warrington’s sweep map on rational Dyck paths (see D. Armstrong, N. A. Loehr, and G. S. Warrington [Adv. Math. 284 (2015), pp. 159–185; E. Gorsky, M. Mazin, and M. Vazirani [Electron. J. Combin. 24 (2017), p. 29; H. Thomas and N. Williams, Selecta Math. (N.S.) 24 (2018), pp. 2003–2034]).

    more » « less