More Like this

1. Regular Sequential Serializability and Regular Sequential Consistency

   https://doi.org/10.1145/3477132.3483566  

   Helt, Jeffrey; Burke, Matthew; Levy, Amit; Lloyd, Wyatt (October 2021, ACM Symposium on Operating Systems Principles)

   Strictly serializable (linearizable) services appear to execute transactions (operations) sequentially, in an order consistent with real time. This restricts a transaction's (operation's) possible return values and in turn, simplifies application programming. In exchange, strictly serializable (linearizable) services perform worse than those with weaker consistency. But switching to such services can break applications. This work introduces two new consistency models to ease this trade-off: regular sequential serializability (RSS) and regular sequential consistency (RSC). They are just as strong for applications: we prove any application invariant that holds when using a strictly serializable (linearizable) service also holds when using an RSS (RSC) service. Yet they relax the constraints on services---they allow new, better-performing designs. To demonstrate this, we design, implement, and evaluate variants of two systems, Spanner and Gryff, relaxing their consistency to RSS and RSC, respectively. The new variants achieve better read-only transaction and read tail latency than their counterparts. 

   more » « less
2. Another construction of edge-regular graphs with regular cliques

   https://doi.org/10.1016/j.disc.2018.09.032  

   Greaves, Gary R.W.; Koolen, Jack H. (November 2018, Discrete Mathematics)
3. Streamable regular transductions

   https://doi.org/10.1016/j.tcs.2019.11.018  

   Alur, Rajeev; Fisman, Dana; Mamouras, Konstantinos; Raghothaman, Mukund; Stanford, Caleb (February 2020, Theoretical Computer Science)
4. Regular Supercuspidal Representations

   Tasho Kaletha (July 2019, Journal of the American Mathematical Society)

   We show that, in good residual characteristic, most supercuspidal representations of a tamely ramified reductive p-adic group G arise from pairs (S,\theta), where S is a tame elliptic maximal torus of G, and \theta is a character of S satisfying a simple root-theoretic property. We then give a new expression for the roots of unity that appear in the Adler-DeBacker-Spice character formula for these supercuspidal representations and use it to show that this formula bears a striking resemblance to the character formula for discrete series representations of real reductive groups. Led by this, we explicitly construct the local Langlands correspondence for these supercuspidal representations and prove stability and endoscopic transfer in the case of toral representations. In large residual characteristic this gives a construction of the local Langlands correspondence for almost all supercuspidal representations of reductive p-adic groups. 

   more » « less
5. Continuous Regular Functions

   https://doi.org/https://doi.org/10.23638/LMCS-16(1:17)2020  

   Block Gorman, Alexi Block; Hieronymi, Philipp; Kaplan, Elliot; Meng, Ruoyu; Walsberg, Erik; Wang, Zihe; Xiong, Ziqin; Yang, Hongru (January 2020, Logical methods in computer science)

   Following Chaudhuri, Sankaranarayanan, and Vardi, we say that a function f:[0,1]→[0,1] is r-regular if there is a Büchi automaton that accepts precisely the set of base r∈N representations of elements of the graph of f. We show that a continuous r-regular function f is locally affine away from a nowhere dense, Lebesgue null, subset of [0,1]. As a corollary we establish that every differentiable r-regular function is affine. It follows that checking whether an r-regular function is differentiable is in PSPACE. Our proofs rely crucially on connections between automata theory and metric geometry developed by Charlier, Leroy, and Rigo. 

   more » « less