Periklis A. Papakonstantinou

associate professor at Rutgers

contact information

periklis.research@gmail.com
periklis.papakonstantinou@rutgers.edu
+1-848-445-9225 		Rutgers University, Rutgers Business School
Management Science and Information Systems
Lucy Stone Building, Rm# A249
54 Joyce Kilmer Ave
Piscataway, NJ 08854   [ map ]

affiliations

» Management Science and Information Systems, Rutgers (faculty)
» Computer Science, Rutgers, New Brunswick (full faculty - courtesy appointment)
» DIMACS: Center for Discrete Mathematics and Theoretical Computer Science

students

» PhD students

current PhD Students (alphabetic order):

  • Songhua He
            foundations of machine learning, information-theoreric lower bounds, computational complexity

I am listing the last thing I heard (or remember or remember to update) where these folks went to

completed PhDs (reverse chronological order):

  • Nathaniel Hobbs (9/2017 - 8/2024) co-supervised with Jaideep Vaidya
            assistant professor of professional practice (lecturer) at Rutgers University
  • Hafiz Asif (1/2016 - 1/2021) co-supervised with Jaideep Vaidya
            assistant professor at Hofstra University
  • Shiteng Chen (3/2010 - 6/2016)
            associate professor at the Chinese Academy of Sciences (ISCAS)
  • Guang Yang (9/2011 - 12/2015)
            CTO at Conflux (previously assistant professor at the Chinese Academy of Sciences)
  • Hao Song (3/2010 - 6/2014)
            software engineer at Facebook
  • Bangsheng Tang (3/2010 - 6/2013)
            research scientist at META

» undergraduate student mentorship and supervision

» completed MSc and Undergraduate Thesis supervision

ordered in reverse chronological order:
  • Yuping Luo (undergraduate thesis, Tsinghua, 2017): PhD student at Princeton
  • Lei Zhixian (undergraduate thesis, Tsinghua, 2016): PhD student at Harvard
  • Sixue Liu (MSc thesis, Tsinghua, 2016): PhD student at Princeton (initially Cambridge U.)
  • Yuanzhi Li (undergraduate thesis, Tsinghua, 2014):   PhD student at Princeton
  • Xin Yang (undergraduate thesis, Tsinghua, 2014):   PhD student at the U. Washington
  • Mao Jieming (undergraduate thesis, Tsinghua, 2013):   PhD student at Princeton
  • Silvio Frischknecht (MSc thesis, ETH, 2012, co-supervised with Roger Wattenhofer)

teaching

At Rutgers I am teaching graduate and undergraduate courses in: cryptography and information security, distributed ledgers and cryptocurrencies, machine learning, and databases. All courses are taught through Canvas.

» past courses at Tsinghua
» before Tsinghua


talks & notes

» talks

Email me for a copy of my slides of a talk

» notes

Below is a selection of course material I developed
  • A crash course in probability [ pdf ]
    -- a mild introduction to measure concentration for Business students
  • Advanced algorithms notes [ pdf ]
    -- from an undergraduate class I taught regularly in the Elite CS class @ Tsinghua
  • Elementary counting [ pdf ]
    -- an introduction to combinatorial enumeration (assuming no prerequisites)

about me

» my research

I work in the foundations of computing, with a focus on computational complexity, and the mathematical foundations of cryptography and machine learning. I am a computer scientist and mathematician by training. In the distant past I started as an engineer. Occasionally, I revisit my engineering roots and enjoy solving practical problems. As a result, my research spans both theoretical and applied domains. I strive to keep these two research lives separate from each other —pure theory for its own sake and applications for their own utility. Yet, both originate from the same source. If I had to choose one, I would say my deepest passion lies in theory. These are the kinds of questions that keep me awake at night.

» at Rutgers and before

Since 2015 I am with Rutgers, The State University of New Jersey, where I'm an associate professor. My main affiliation is with the Management Science department (although in the beginning I was trying to figure out what a theorist of computing is doing in a business school, now I believe that every successful business school should have theoretical computer scientists). Before Rutgers I spent six wonderful years as an assistant professor at Tsinghua University, at Andy Yao's Institute, where I had the priviledge to lead the Laboratory for the Study of Randomness, teach bright undergraduates at the "Tsinghua Elite CS class", and supervise several PhD students who today follow successful careers in academia and industry. I did my PhD in Theoretical Computer Science at the University of Toronto, advised by Charles Rackoff. Also, I hold advanced degrees (MSc & MEng) in Mathematics, Computer Science, and Computer Engineering, and have received various academic awards, distinctions, and all that.

PhD Thesis in Computer Science

Constructions, Lower Bounds, and New Directions in Cryptography and Computational Complexity

Department of Computer Science, University of Toronto, 2010
Advisor: Charles Rackoff

[pdf]

Abstract

In the first part of the thesis we show black-box separations in public and private-key cryptography. Our main result answers in the negative the question of whether we can base Identity Based Encryption (IBE) on Trapdoor Permutations. Furthermore, we make progress towards the black-box separation of IBE from the Decisional Diffie-Hellman assumption. We also show the necessity of adaptivity when querying one-way permutations to construct pseudorandom generators la Goldreich-Levin; an issue related to streaming models for cryptography.

In the second part we introduce streaming techniques in understanding randomness in efficient computation, proving lower bounds for efficiently computable problems, and in computing cryptographic primitives.

We observe [Cook'71] that logarithmic space-bounded Turing Machines, equipped with an unbounded stack, henceforth called Stack Machines, together with an external random tape of polynomial length characterize RP; BPP an so on. By parametrizing on the number of passes over the random tape we provide a technical perspective bringing together Streaming, Derandomization, and older works in Stack Machines. Our technical developments relate this new model with previous works in derandomization. For example, we show that to derandomize parts of BPP it is in some sense sufficient to derandomize BPNC (a class believed to be much lower than P subset of BPP). We also obtain a number of results for variants of the main model, regarding e.g. the fooling power of Nisan's pseudorandom generator (PRG) [Nisan'92] for the derandomization of BPNC^1, and the relation of parametrized access to NP-witnesses with width- parametrizations of SAT.

A substantial contribution regards a streaming approach to lower bounds for problems in the NC-hierarchy (and above). We apply Communication Complexity to show a streaming lower bound for a model with an unbounded (free-to-access) pushdown storage. In particular, we obtain a n^O(1) lower bound simultaneously in the space and in the number of passes over the input, for a variant of inner product. This is the first lower bound for machines that correspond to poly-size circuits, can do Parity, Barrington's language, and decide problems in P-NC, assuming EXP not equal PSPACE. Finally, we initiate the study of log-space streaming computation of cryptographic primitives. We observe that the work on Cryptography in NC^0 [Applebaum, Ishai, Kushilevitch '06] yields a non-black-box construction of a one-way function computable in an O(log n)-space bounded streaming model. Also, we show that relying on this work is in some sense necessary.

publications

Remark: author order in all papers is alphabetical (typical in mathematical sciences)