Pedro Paredes

I'm a Lecturer at Princeton University in the Department of Computer Science.

Before joining Princeton, I completed my PhD in 2022 at Carnegie Mellon University, where I was very lucky to be advised by Ryan O'Donnell. Prior to that, I graduated from University of Porto in 2017 with a Bachelor's and a Master's degree, where I was also lucky to be advised by Pedro Ribeiro.

My primary research interest is in Theoretical Computer Science. In particular I am interested in:
Spectral Graph Theory, Pseudorandomness, Coding Theory, Combinatorics, Quantum Information Theory.

Publications

® Author order randomized

• R. O'Donnell, R. Servedio, P. Paredes ®. Explicit orthogonal and unitary designs.
  Manuscript
• J. Hsieh, T. McKenzie, S. Mohanty, P. Paredes. Explicit two-sided unique-neighbor expanders.
  Manuscript | PDF
• F. G. Jeronimo, T. Mittal, R. O'Donnell, P. Paredes, M. Tulsiani. Explicit Abelian Lifts and Quantum LDPC Codes.
  ITCS '22 | PDF
• P. Paredes. Spectrum preserving short cycle removal on regular graphs.
  STACS '21 | PDF
• S. Mohanty, R. O'Donnell, P. Paredes. Explicit near-Ramanujan graphs of every degree.
  STOC '20 | SIAM Journal on Computing '21, special section on STOC 2020 | PDF
• S. Mohanty, R. O'Donnell, P. Paredes. The SDP value for random two-eigenvalue CSPs.
  STACS '20 | PDF

For a full list of publications check out my Google Scholar or DBLP.

Surveys and Theses

• P. Paredes. On the Expansion of Graphs.
  PhD Thesis | PDF
• P. Ribeiro, P. Paredes, M. E.P. Silva, D. Aparicio, F. Silva.
  A Survey on Subgraph Counting: Concepts, Algorithms and Applications to Network Motifs and Graphlets.
  ACM Computing Surveys '21 | PDF

Talks

• Pseudorandom rotations: explicit approximate designs for some Lie groups | Princeton Theory Lunch, Dec 22 | Video
• Spectrum preserving short cycle removal on regular graphs | STACS'21, Mar 21 | Video
• Spectrum preserving operations in regular graphs | UW Theory Seminar, Jan 21 | Video
• Expander Graphs: Theory and Applications | Talks@DCC, Jul 20
• Explicit near-Ramanujan graphs of every degree (Joint with S. Mohanty) | STOC'20, Jun 20 | Video
• Explicit near-Ramanujan graphs of every degree | CMU Theory lunch, Nov 19 | Video

Teaching

• Faculty | COS 445: Economics and Computing, Spring 2023
• Faculty | COS 126: Computer Science: An Interdisciplinary Approach, Fall 2022

Before Princeton

• Teaching Assistant | CMU 15-751 : TCS Toolkit
• Teaching Assistant | CMU 15-451 : Algorithms
• Teaching Assistant | FCUP CC1007 : Data Structures

Advising

• Undergraduate Research Advisor | Amir Touil
• Undergraduate Research Advisor | Ijay Narang

Before Princeton

• Undergraduate Mentor | Jeremy Brennan | CMU 07-400 : Research Practicum in Computer Science

Projects

Competitive programming

I run the competitive programming club at Princeton

Modern Coding Theory and Expanders Reading Group

Fernando Granha Jeronimo and I co-organize a coding theory and expanders reading group jointly at Princeton and the IAS.

About me

Math outreach

I was an instructor and co-organizer of the Pan-African Math Circle.

Competitive programming

I'm the head of the scientific committee of the Portuguese National Olympiad or ONI (link in Portuguese).

Here are some problems I authored that I like:

• Italian Data Centers | ICPC SWERC 2023 | link
• European Trip | ICPC SWERC 2022 | link
• Springboards | USACO 2020 January Contest, Gold | link
• Topografia dos Onimalaias | ONI'2019 Final Round | link (in Portuguese)
• Chegar ao outro lado | ONI'2017 Final Round | link (in Portuguese)

Miscellaneous

• Map of countries I've visited.
• I'm a Pittsburgh Steelers fan and an Anaheim Ducks fan.