Renato Ferreira Pinto Jr.

I am a postdoc in the Department of Computer Science at Columbia University, hosted by Xi Chen and Rocco Servedio and partially supported by an NSERC Postdoctoral Fellowship.

Previously, I completed my PhD in Computer Science under the supervision of Eric Blais at the University of Waterloo. Before that, I obtained an MSc at the University of Toronto under the supervision of Yang Xu, and completed my Bachelor's at the University of Waterloo.

My research is guided by the following question: what kinds of decisions can algorithms make using little information? I am broadly interested in sublinear algorithms, randomness in computation, Boolean functions, high-dimensional functions and geometry, learning theory, and computational statistics.

In a previous life, I studied computational linguistics with a touch of cognitive science at the University of Toronto.

Theory Papers

In Theoretical Computer Science, authors are typically listed in alphabetical order, and this is the case below.

Citing my works in BibTeX (or, what is my name?)

I do not have a middle name, that is, my first name is "Renato" and my last name is "Ferreira Pinto Jr", with initial "F". I believe the easiest way to have BibTeX behave accordingly is to enter my last name as {Ferreira Pinto Jr}. For slides and such, feel free to use the shorter "Ferreira" if that is more convenient.

• Learning and Testing Convex Functions (To appear, RANDOM 2026)
  RF, Cassandra Marcussen, Elchanan Mossel, Shivam Nadimpalli [arXiv]
• Testing Distributions Against Bounded Distinguishers (STOC 2026)
  Mark Bun, Rathin Desai, RF [arXiv]
• Computational Complexity in Property Testing (SODA 2026)
  RF, Diptaksho Palit, Sofya Raskhodnikova [arXiv]
• On the Spectral Expansion of Monotone Subsets of the Hypercube (RANDOM 2025)
  Yumou Fei, RF [arXiv]
• Testing Support Size More Efficiently Than Learning Histograms (STOC 2025, TheoretiCS)
  RF, Nathaniel Harms [arXiv] [video for STOC]
• Directed Isoperimetry and Monotonicity Testing: A Dynamical Approach (FOCS 2024)
  RF [arXiv] [slides] [animations: heat equation, directed heat equation] [TCS+ talk]
• Distribution Testing with a Confused Collector (ITCS 2024)
  RF, Nathaniel Harms [arXiv]
• Directed Poincaré Inequalities and L¹ Monotonicity Testing of Lipschitz Functions (RANDOM 2023)
  RF [arXiv]
• VC Dimension and Distribution-Free Sample-Based Testing (STOC 2021)
  Eric Blais, RF, Nathaniel Harms [arXiv]

PhD Thesis

Analytic Property Testing: Directed Isoperimetry and Monotonicity

Manuscripts

• Distribution Testing Under the Parity Trace
  RF, Nathaniel Harms [arXiv]

Cognitive Science Papers

Note that the TCS author list convention does not apply to this section. A * symbol denotes equal contribution.

• The emergence of moral foundations in child language development (CogSci 2022)
  Aida Ramezani*, Emmy Liu*, RF, Spike W. S. Lee, Yang Xu [pdf]
• A computational theory of child overextension (2021, Cognition)
  RF, Yang Xu [pdf] [supplementary material] [GitHub]
• Text-based inference of moral sentiment change (EMNLP 2019)
  Jing Yi Xie*, RF*, Graeme Hirst, Yang Xu [pdf] [supplementary material] [GitHub]
• Children's overextension as communication by multimodal chaining (CogSci 2019)
  RF, Yang Xu [pdf]

MSc Research Paper

A Computational Theory of Children's Overextension