Lewis-Pye, Andrew

Number of items: 76.
None
  • Barmpalias, George, Lewis-Pye, Andrew (2015). The information content of typical reals. In Sommaruga, Giovanni, Strahm, Thomas (Eds.), Turing’s revolution: the impact of his ideas about computability (pp. 207-224). Springer Berlin / Heidelberg. https://doi.org/10.1007/978-3-319-22156-4
  • Barmpalias, George, Day, Adam R., Lewis-Pye, Andrew (2014). The typical Turing degree. Proceedings of the London Mathematical Society, 109(1), 1-39. https://doi.org/10.1112/plms/pdt065
  • Jockush, Carl G., Lewis-Pye, Andrew (2014). Diagonally non-computable functions and bi-immunity. Journal of Symbolic Logic, 78(3), 977-988. https://doi.org/10.2178/jsl.7803150
  • Barmpalias, G., Hölzl, R., Lewis-Pye, Andrew, Merkle, W. (2013). Analogues of Chaitinʼs Omega in the computably enumerable sets. Information Processing Letters, 113(5-6), 171-178. https://doi.org/10.1016/j.ipl.2013.01.007
  • Downey, Rod, Greenberg, Noam, Lewis-Pye, Andrew, Montalbán, Antonio (2013). On the degree spectrum of a π01 class. Transactions of the American Mathematical Society, 365(06), 2977-3018. https://doi.org/10.1090/S0002-9947-2012-05660-1
  • Kent, Thomas F., Lewis-Pye, Andrew, Sorbi, Andrea (2012). Empty intervals in the enumeration degrees. Annals of Pure and Applied Logic, 163(5), 567-574. https://doi.org/10.1016/j.apal.2011.06.012
  • Barmpalias, George, Lewis-Pye, Andrew (2012). Measure and cupping in the Turing degrees. Proceedings of the American Mathematical Society, 140(10), 3607-3622. https://doi.org/10.1090/S0002-9939-2012-11183-9
  • Lewis-Pye, Andrew (2012). Properties of the jump classes. Journal of Logic and Computation, 22(4), 845-855. https://doi.org/10.1093/logcom/exq047
  • Lewis-Pye, Andrew (2012). A note on the join property. Proceedings of the American Mathematical Society, 140(2), 707-714. https://doi.org/10.1090/S0002-9939-2011-10908-0
  • Barmpalias, George, Lewis-Pye, Andrew (2011). Chaitin's halting probability and the compression of strings using oracles. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 467(2134), 2912-2926. https://doi.org/10.1098/rspa.2011.0031
  • Lewis-Pye, Andrew, Shore, Richard A., Sorbi, Andrea (2011). Topological aspects of the Medvedev lattice. Archive for Mathematical Logic, 50(3-4), 319-340. https://doi.org/10.1007/s00153-010-0215-6
  • Ellison, Philip, Lewis-Pye, Andrew (2010). Joining up to the generalized high degrees. Proceedings of the American Mathematical Society, 138(8), 2949-2960. https://doi.org/10.1090/S0002-9939-10-10299-8
  • Kent, Thomas, Lewis-Pye, Andrew (2010). On the degree spectrum of a π01 class. Transactions of the American Mathematical Society, 362(10), 5283-5319. https://doi.org/10.1090/S0002-9947-10-05037-3
  • Barmapalias, George, Lewis-Pye, Andrew, Meng Ng, Keng (2010). The importance of π⁰₁ classes in effective randomness. Journal of Symbolic Logic, 75(1), 387-400. https://doi.org/10.2178/jsl/1264433928
  • Lewis-Pye, Andrew (2009). Strong minimal covers and a question of Yates: the story so far. In Cooper, Barry, Geuvers, Herman, Pillay, Anand, Väänänen, Jouko (Eds.), Logic Colloquium 2006 (pp. 213-228). Cambridge University Press. https://doi.org/10.1017/CBO9780511605321.011
  • Lewis-Pye, Andrew, Nies, André, Sorbi, Andrea (2009). The first order theories of the Medvedev and Muchnik lattices. In Ambos-Spies, Klaus, Löwe, Benedikt, Merkle, Wolfgang (Eds.), Mathematical Theory and Computational Practice: 5th Conference on Computability in Europe, Cie 2009, Heidelberg, Germany, July 1 (pp. 324-331). Springer Berlin / Heidelberg. https://doi.org/10.1007/978-3-642-03073-4_33
  • Kumabe, Masahiro, Lewis-Pye, Andrew (2009). A fixed-point-free minimal degree. Journal of the London Mathematical Society, 80(3), 785-797. https://doi.org/10.1112/jlms/jdp049
  • Barmpalias, George, Lewis-Pye, Andrew, Stephan, Frank (2008). Π10 classes, LR degrees and Turing degrees. Annals of Pure and Applied Logic, 156(1), 21-38. https://doi.org/10.1016/j.apal.2008.06.004
  • Lewis-Pye, Andrew (2008). On a question of Slaman and Groszek. Proceedings of the American Mathematical Society, 136(10), 3663-3668. https://doi.org/10.1090/S0002-9939-08-09345-3
  • Barmpalias, George, Lewis-Pye, Andrew, Soskova, Mariya (2008). Randomness, lowness and degrees. Journal of Symbolic Logic, 73(2), 559-577. https://doi.org/10.2178/jsl/1208359060
  • Lewis-Pye, Andrew (2007). Π10 classes, strong minimal covers and hyperimmune-free degrees. Bulletin of the London Mathematical Society, 39(6), 845-855. https://doi.org/10.1112/blms/bdm083
  • Lewis-Pye, Andrew, Barmpalias, George (2007). Randomness and the linear degrees of computability. Annals of Pure and Applied Logic, 145(3), 252-257. https://doi.org/10.1016/j.apal.2006.08.001
  • Barmpalias, George, Lewis-Pye, Andrew, Soskova, Mariya (2007). Working with the LR degrees. In Cai, Jin-Yi, Cooper, S. Barry, Zhu, Hong (Eds.), Theory and Applications of Models of Computation: 4th International Conference, Tamc 2007, Shanghai, China, May 22-25, 2007 (pp. 89-99). Springer Berlin / Heidelberg. https://doi.org/10.1007/978-3-540-72504-6_8
  • Lewis-Pye, Andrew (2007). A random degree with strong minimal cover. Bulletin of the London Mathematical Society, 39(5), 848-856. https://doi.org/10.1112/blms/bdm074
  • Lewis-Pye, Andrew (2007). A single minimal complement for the c.e. degrees. Transactions of the American Mathematical Society, 359(12), 5817-5865. https://doi.org/10.1090/S0002-9947-07-04331-0
  • Lewis-Pye, Andrew, Montalbán, Antonio, Nies, André (2007). A weakly 2-random set that is not generalized low. In Cooper, S. Barry, Löwe, Benedikt, Sorbi, Andrea (Eds.), Computation and Logic in the Real World: Third Conference on Computability in Europe, Cie 2007, Siena, Italy, June 18-23, 2007 (pp. 474-477). Springer Berlin / Heidelberg. https://doi.org/10.1007/978-3-540-73001-9_49
  • Lewis-Pye, Andrew, Barmpalias, George (2006). Random reals and Lipschitz continuity. Mathematical Structures in Computer Science, 16(5), 737-749. https://doi.org/10.1017/S0960129506005445
  • Barmpalias, George, Lewis-Pye, Andrew (2006). A c.e. real that cannot be sw-computed by any Ω number. Notre Dame Journal of Formal Logic, 47(2), 197-209. https://doi.org/10.1305/ndjfl/1153858646
  • Barmpalias, George, Lewis-Pye, Andrew (2006). The hypersimple-free c.e. wtt degrees are dense in the c.e. wtt degrees. Notre Dame Journal of Formal Logic, 47(3), 361-370. https://doi.org/10.1305/ndjfl/1163775443
  • Barmpalias, George, Lewis-Pye, Andrew (2006). The ibT degrees of computably enumerable sets are not dense. Annals of Pure and Applied Logic, 141(1-2), 51-60. https://doi.org/10.1016/j.apal.2005.10.001
  • Lewis-Pye, Andrew (2006). The jump classes of minimal covers. In Beckmann, Arnold, Berger, Ulrich, Löwe, Benedikt, Tucker, John V. (Eds.), Logical Approaches to Computational Barriers: Second Conference on Computability in Europe, Cie 2006, Swansea, Uk, June 30-July (pp. 307-318). Springer Berlin / Heidelberg. https://doi.org/10.1007/11780342_33
  • Lewis-Pye, Andrew (2005). On a question of sacks: a partial solution on the positive side. In Cooper, S. Barry, Löwe, Benedikt, Torenvliet, Leen (Eds.), New Computational Paradigms: First Conference on Computability in Europe, Cie 2005, Amsterdam, the Netherlands, June 8-12, 2005 (pp. 275-286). Springer Berlin / Heidelberg. https://doi.org/10.1007/11494645_34
  • Cooper, S. Barry, Lewis-Pye, Andrew, Yang, Yue (2005). Properly Σ2 minimal degrees and 0″ complementation. Mathematical Logic Quarterly, 51(3), 274-276. https://doi.org/10.1002/malq.200410027
  • Lewis-Pye, Andrew (2005). The minimal complementation property above 0′. Mathematical Logic Quarterly, 51(5), 470-492. https://doi.org/10.1002/malq.200410044
  • Lewis-Pye, Andrew (2004). Finite cupping sets. Archive for Mathematical Logic, 43(7), 845-858. https://doi.org/10.1007/s00153-004-0215-5
  • Lewis-Pye, Andrew (2004). Minimal complements for degrees below 0'. Journal of Symbolic Logic, 69(4), 937-966. https://doi.org/10.2178/jsl/1102022208
    • Public
  • Lewis-Pye, Andrew, Neu, Joachim, Roughgarden, Tim, Zanolini, Luca (2025). Accountable liveness. In CCS 2025 - Proceedings of the 2025 ACM SIGSAC Conference on Computer and Communications Security (pp. 3431 - 3445). ACM Press. https://doi.org/10.1145/3719027.3765032 picture_as_pdf
  • Lewis-Pye, Andrew, Shapiro, Ehud (2025-12-03 - 2025-12-05) Morpheus consensus: excelling on trails and autobahn [Paper]. 29th International Conference on Principles of Distributed Systems, Alexandru Ioan Cuza University of Iaşi, Iaşi, Romania, ROM. picture_as_pdf
  • Lewis-Pye, Andrew, Roughgarden, Tim (2025). Beyond optimal fault-tolerance. In Avarikioti, Zeta, Christin, Nicolas (Eds.), 7th Conference on Advances in Financial Technologies (AFT 2025) . Schloss Dagstuhl, Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.AFT.2025.15 picture_as_pdf
  • Komatovic, Jovan, Lewis-Pye, Andrew, Neu, Joachim, Roughgarden, Tim, Nusret Tas, Ertem (2025). From permissioned to proof-of-stake consensus. In Avarikioti, Zeta, Christin, Nicolas (Eds.), 7th Conference on Advances in Financial Technologies (AFT 2025) . Schloss Dagstuhl, Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.AFT.2025.18 picture_as_pdf
  • Chou, Brendan Kobayashi, Lewis-Pye, Andrew, O'Grady, Patrick (2026-03-02 - 2026-03-06) Minimmit: fast finality with even faster blocks [Paper]. Financial Cryptography and Data Security 2026. picture_as_pdf
  • Budish, Eric, Lewis-Pye, Andrew, Roughgarden, Tim (2024). The economic limits of permissionless consensus. ACM Transactions on Economics and Computation, 704 - 731. https://doi.org/10.1145/3670865.3673548 picture_as_pdf
  • Buchwald, Aaron, Buttolph, Stephen, Lewis-Pye, Andrew, O'Grady, Patrick, Sekniqi, Kevin (2025-04-14 - 2025-04-18) Frosty: bringing strong liveness guarantees to the Snow family of consensus protocols [Paper]. Financial Cryptography and Data Security 2025, Hotel Shigira Mirage, Miyakojima, Japan, JPN. picture_as_pdf
  • Lewis-Pye, Andrew, Malkhi, Dahlia, Naor, Oded, Nayak, Kartik (2024). Lumiere: making optimal BFT for partial synchrony practica. In PODC 2024 - Proceedings of the 2024 ACM Symposium on Principles of Distributed Computing (pp. 135 - 144). ACM Press. https://doi.org/10.1145/3662158.3662787 picture_as_pdf
  • Lewis-Pye, Andrew, Abraham, Ittai (2024). Fever: optimal responsive view synchronisation. In Bessani, Alysson, Défago, Xavier, Nakamura, Junya, Wada, Koichi, Yamauchi, Yukiko (Eds.), Proceedings of the 27th International Conference on Principles of Distributed Systems (OPODIS 2023) . ACM Press. https://doi.org/10.4230/LIPIcs.OPODIS.2023.14 picture_as_pdf
  • Lewis-Pye, Andrew, Roughgarden, Tim (2023). Byzantine generals in the permissionless setting. In Baldimtsi, Foteini, Cachin, Christian (Eds.), Financial Cryptography and Data Security: 27th International Conference, FC 2023, Bol, Brač, Croatia, May 1–5, 2023, Revised Selected Papers, Part I (pp. 21 - 37). Springer-Verlag. https://doi.org/10.1007/978-3-031-47754-6_2 picture_as_pdf
  • Lewis-Pye, Andrew, Roughgarden, Tim (2021). How does blockchain security dictate blockchain implementation? In CCS 2021 - Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security (pp. 1006 - 1019). ACM Press. https://doi.org/10.1145/3460120.3484752 picture_as_pdf
  • Lewis-Pye, Andrew (2020). Cryptocurrencies: protocols for consensus. Notices of the American Mathematical Society, 67(9), 1307 - 1315. https://doi.org/10.1090/noti2148 picture_as_pdf
  • Barmapalias, George, Fang, Nan, Lewis-Pye, Andrew (2020). Monotonous betting strategies in warped casinos. Information and Computation, 271, https://doi.org/10.1016/j.ic.2019.104480 picture_as_pdf
  • Barmpalias, George, Lewis-Pye, Andrew (2019). Compression of data streams down to their information content. IEEE Transactions on Information Theory, 65(7), 4471-4485. https://doi.org/10.1109/TIT.2019.2896638 picture_as_pdf
  • Barmpalias, George, Huang, Neng, Lewis-Pye, Andrew, Li, Angsheng, Li, Xuechen, Pan, Yicheng, Roughgarden, Tim (2019). The idemetric property: when most distances are (almost) the same. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 475(2222). https://doi.org/10.1098/rspa.2018.0283 picture_as_pdf
  • Barmpalias, George, Elwes, Richard, Lewis-Pye, Andy (2018). Minority population in the one-dimensional Schelling model of segregation. Journal of Statistical Physics, picture_as_pdf
  • Barmpalias, George, Lewis-Pye, Andrew, Li, Angsheng (2018). Pointed computations and Martin-Löf randomnesss. Computability, 7(2-3), 171-177. https://doi.org/10.3233/COM-170076
  • Lewis-Pye, Andrew (2018). The search for natural definability in the Turing degrees. Computability, 7(2-3), 189-235. https://doi.org/10.3233/COM-170068
  • Cooper, Barry, Lewis-Pye, Andrew, Li, Angsheng, Pan, Yicheng, Yong, Xi (2018). Establishing social cooperation: the role of hubs and community structure. Network Science, 6(2), 251-264. https://doi.org/10.1017/nws.2018.3
  • Barmpalias, George, Elwes, Richard, Lewis-Pye, Andrew (2018). Digital morphogenesis via Schelling segregation. Nonlinearity, 31(4), 1593 - 1638. https://doi.org/10.1088/1361-6544/aaa493
  • Barmpalias, George, Lewis-Pye, Andrew (2017). Differences of halting probabilities. Journal of Computer and System Sciences, 89, 349-360. https://doi.org/10.1016/j.jcss.2017.06.002
  • Barmpalias, George, Lewis-Pye, Andrew (2017). Optimal redundancy in computations from random oracles. Journal of Computer and System Sciences, https://doi.org/10.1016/j.jcss.2017.06.009
  • Lewis-Pye, Andrew, Montalbán, Antonio (2017). Sex versus asex: an analysis of the role of variance conversion. Theoretical Population Biology, 114, 128-135. https://doi.org/10.1016/j.tpb.2017.01.002
  • Barmpalias, George, Lewis-Pye, Andrew (2017). Computing halting probabilities from other halting probabilities. Theoretical Computer Science, 660, 16-22. https://doi.org/10.1016/j.tcs.2016.11.013
  • Barmpalias, George, Lewis-Pye, Andrew (2017). A note on the differences of computably enumerable reals. In Day, Adam, Fellows, Michael, Greenberg, Noam, Khoussainov, Bakhadyr, Melnikov, Alexander, Rosamond, Frances (Eds.), Computability and Complexity: Essays Dedicated to Rodney G. Downey on the Occasion of His 60th Birthday (pp. 623-632). Springer International (Firm). https://doi.org/10.1007/978-3-319-50062-1_37
  • Barmpalias, George, Fang, Nan, Lewis-Pye, Andrew (2016). Optimal asymptotic bounds on the oracle use in computations from Chaitin’s Omega. Journal of Computer and System Sciences, 82(8), 1283-1299. https://doi.org/10.1016/j.jcss.2016.05.004
  • Barmpalias, George, Lewis-Pye, Andrew, Teutsch, Jason (2016). Lower bounds on the redundancy in computations from random oracles via betting strategies with restricted wagers. Information and Computation, 251, 287-300. https://doi.org/10.1016/j.ic.2016.09.010
  • Barmpalias, George, Elwes, Richard, Lewis-Pye, Andrew (2016). Unperturbed Schelling segregation in two or three dimensions. Journal of Statistical Physics, 164(6), 1460-1487. https://doi.org/10.1007/s10955-016-1589-6
  • Durrant, Benedict, Lewis-Pye, Andrew, Meng Ng, Keng, Riley, James (2016). Computably enumerable Turing degrees and the meet property. Proceedings of the American Mathematical Society, 144(4), 1735 - 1744. https://doi.org/10.1090/proc/12808
  • Lewis-Pye, Andrew (2016). 5 minutes with Maura Paterson.
  • Lewis-Pye, Andrew (2015). 5 minutes with Frank Wilczek.
  • Lewis-Pye, Andrew (2015). 5 minutes with Andre Nies.
  • Lewis-Pye, Andrew (2015). 5 minutes with Yannai A. Gonczarowski.
  • Lewis-Pye, Andrew (2015). Andy Lewis-Pye: the strange patterns of segregation.
  • Barmpalias, George, Elwes, Richard, Lewis-Pye, Andrew (2015). Tipping points in 1-dimensional Schelling models with switching agents. Journal of Statistical Physics, 158(4), 806-852. https://doi.org/10.1007/s10955-014-1141-5
  • Downey, Rodney G., Kach, Asher M., Lempp, Steffen, Lewis-Pye, Andrew, Montalbán, Antonio, Turetsky, Daniel D. (2015). The complexity of computable categoricity. Advances in Mathematics, 268, 423-466. https://doi.org/10.1016/j.aim.2014.09.022
  • Lewis-Pye, Andrew (2014-05-08) Schelling segregation [Poster]. LSE Research Festival 2014, London, United Kingdom, GBR.
  • Barmpalias, George, Elwes, Richard, Lewis-Pye, Andrew (2014). Digital morphogenesis via Schelling segregation. Foundations of Computer Science (FOCS), 2014 IEEE 55th Annual Symposium, 0(0), 156-165. https://doi.org/10.1109/FOCS.2014.25
    • Restricted
  • Lewis-Pye, Andrew (2022). Cryptocurrencies: protocols for consensus. In Pitici, Mircea (Ed.), The Best Writing on Mathematics 2021 (pp. 9-28). Princeton University Press. picture_as_pdf
  • Barmpalias, George, Lewis-Pye, Andrew (2017). Limits of the Kucera-Gacs coding method. In Post-proceedings volume of SEALS 2016 (South Eastern Logic Symposium) . World Scientific (Firm). picture_as_pdf