Pedro Paredes

I'm a 5^th year PhD student of Computer Science at Carnegie Mellon University, in Pittsburgh, USA.

I am advised by Professor Ryan O'Donnell.

My research interests: Spectral Graph theory, Pseudorandomness, Complexity theory, Combinatorics.

My thesis proposal (On the Expansion of Graphs) is available here.

Publications

• 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

Selected Older Publications (from when I was an undergrad)

• 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
• P. Ribeiro, P. Paredes. Fast streaming small graph canonization.
  CompleNet '18 | PDF

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

Talks

• 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 and Mentoring

• Undergraduate Mentor | Jeremy Brennan | CMU 07-400 : Research Practicum in Computer Science
• Teaching Assistant | CMU 15-751 : TCS Toolkit
• Teaching Assistant | CMU 15-451 : Algorithms
• Teaching Assistant | FCUP CC1007 : Data Structures

About me

Math outreach

I am 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:

• European Trip | ICPC SWERC 2022 | link
• Springboards | USACO 2020 January Contest, Gold | link
• Topografia dos Onimalaias | ONI'2019 Final Round | link (in Portuguese)
• Jantar para dois mil | ONI'2018 Selection Round | link (in Portuguese)
• Chegar ao outro lado | ONI'2017 Final Round | link (in Portuguese)

Miscellaneous

• Map of countries I've visited.
• I helped run CMU Theory Club and CMU Theory Lunch.
• I'm a Pittsburgh Steelers fan and an Anaheim Ducks fan.