Hierarchies for classes of priority algorithms for Job Scheduling. - Periklis A. Papakonstantinou (Theor. Comput. Sci., 2006)

On the Impossibility of Basing Identity Based Encryption on Trapdoor Permutations. - Dan Boneh; Periklis A. Papakonstantinou; Charles Rackoff; Yevgeniy Vahlis; Brent Waters (FOCS, 2008)

Complexity and Algorithms for Well-Structured k-SAT Instances. - Konstantinos Georgiou; Periklis A. Papakonstantinou (SAT, 2008)

On the Structure of Optimal Greedy Computation (for Job Scheduling). - Periklis A. Papakonstantinou (MFCS, 2009)

On the complexity of constructing Golomb Rulers. - Christophe Meyer; Periklis A. Papakonstantinou (Discret. Appl. Math., 2009)

Polynomial Time with Restricted Use of Randomness. - Matei David; Periklis A. Papakonstantinou; Anastasios Sidiropoulos (Electron. Colloquium Comput. Complex., 2009)

A note on width-parameterized SAT: An exact machine-model characterization. - Periklis A. Papakonstantinou (Inf. Process. Lett., 2009)

Trade-Off Lower Bounds for Stack Machines. - Matei David; Periklis A. Papakonstantinou (CCC, 2010)

Characterizing sets of jobs that admit optimal greedy-like algorithms. - Periklis A. Papakonstantinou; Charles Rackoff (J. Sched., 2010)

Constructions, Lower Bounds, and New Directions in Cryptography and Computational Complexity. - Periklis A. Papakonstantinou (2010)

Computationally Limited Randomness. - Matei David; Phuong Nguyen 001; Periklis A. Papakonstantinou; Anastasios Sidiropoulos (ICS, 2011)

Limits on the Stretch of Non-adaptive Constructions of Pseudo-Random Generators. - Josh Bronson; Ali Juma; Periklis A. Papakonstantinou (TCC, 2011)

Width-parameterized SAT: Time-Space Tradeoffs - Shiteng Chen; Tiancheng Lou; Periklis A. Papakonstantinou; Bangsheng Tang (CoRR, 2011)

Pseudorandomness for read-once formulas. - Andrej Bogdanov; Periklis A. Papakonstantinou; Andrew Wan (Electron. Colloquium Comput. Complex., 2011)

How strong is Nisanʼs pseudo-random generator? - Matei David; Periklis A. Papakonstantinou; Anastasios Sidiropoulos (Inf. Process. Lett., 2011)

Pseudorandomness for Linear Length Branching Programs and Stack Machines. - Andrej Bogdanov; Periklis A. Papakonstantinou; Andrew Wan (APPROX-RANDOM, 2012)

Time-space tradeoffs for width-parameterized SAT: Algorithms and lower bounds. - Eric Allender; Shiteng Chen; Tiancheng Lou; Periklis A. Papakonstantinou; Bangsheng Tang (Electron. Colloquium Comput. Complex., 2012)

How powerful are the DDH hard groups? - Periklis A. Papakonstantinou; Charles Rackoff; Yevgeniy Vahlis (Electron. Colloquium Comput. Complex., 2012)

A remark on one-wayness versus pseudorandomness. - Periklis A. Papakonstantinou; Guang Yang 020 (Electron. Colloquium Comput. Complex., 2012)

Space-bounded communication complexity. - Joshua Brody; Shiteng Chen; Periklis A. Papakonstantinou; Hao Song; Xiaoming Sun 001 (ITCS, 2013)

Overlays and Limited Memory Communication Mode(l)s. - Periklis A. Papakonstantinou; Dominik Scheder; Hao Song (Electron. Colloquium Comput. Complex., 2013)

Bagging by Design (on the Suboptimality of Bagging). - Periklis A. Papakonstantinou; Jia Xu 004; Zhu Cao (AAAI, 2014)

Overlays and Limited Memory Communication. - Periklis A. Papakonstantinou; Dominik Scheder; Hao Song (CCC, 2014)

Cryptography with Streaming Algorithms. - Periklis A. Papakonstantinou; Guang Yang 020 (CRYPTO (2), 2014)

Tradeoff lower lounds for stack machines. - Matei David; Periklis A. Papakonstantinou (Comput. Complex., 2014)

The Depth Irreducibility Hypothesis. - Periklis A. Papakonstantinou (Electron. Colloquium Comput. Complex., 2014)

Width-Parametrized SAT: Time–Space Tradeoffs. - Eric Allender; Shiteng Chen; Tiancheng Lou; Periklis A. Papakonstantinou; Bangsheng Tang (Theory Comput., 2014)

Local Search for Hard SAT Formulas: The Strength of the Polynomial Law. - Sixue Liu; Periklis A. Papakonstantinou (AAAI, 2016)

On the Power and Limits of Distance-Based Learning. - Periklis A. Papakonstantinou; Jia Xu 004; Guang Yang 020 (ICML, 2016)

Correlation lower bounds from correlation upper bounds. - Shiteng Chen; Periklis A. Papakonstantinou (Inf. Process. Lett., 2016)

How to Accurately and Privately Identify Anomalies. - Hafiz Salman Asif; Periklis A. Papakonstantinou; Jaideep Vaidya (CCS, 2019)

Depth Reduction for Composites. - Shiteng Chen; Periklis A. Papakonstantinou (SIAM J. Comput., 2019)

Accurately and Privately Reporting Crowdsensed COVID-19 Data. - Hafiz Salman Asif; Periklis A. Papakonstantinou; Stephanie Shiau; Vivek K. Singh 001; Jaideep Vaidya (AMIA, 2021)

Hide and Seek: Scaling Machine Learning for Combinatorial Optimization via the Probabilistic Method. - Dimitris Achlioptas; Amrit Daswaney; Periklis A. Papakonstantinou (CoRR, 2022)

Deep Neural Networks: The Missing Complexity Parameter. - Songhua He; Periklis A. Papakonstantinou (Electron. Colloquium Comput. Complex., 2022)

Intelligent Pandemic Surveillance via Privacy-Preserving Crowdsensing. - Hafiz Salman Asif; Periklis A. Papakonstantinou; Stephanie Shiau; Vivek K. Singh 001; Jaideep Vaidya (IEEE Intell. Syst., 2022)

Identifying Anomalies While Preserving Privacy. - Hafiz Salman Asif; Jaideep Vaidya; Periklis A. Papakonstantinou (IEEE Trans. Knowl. Data Eng., 2023)

The Effect of Weight Precision on the Neuron Count in Deep ReLU Networks. - Songhua He; Periklis A. Papakonstantinou (ICML, 2024)

Lower Bounds in the Query-with-Sketch Model and a Barrier in Derandomizing BPL. - Songhua He; Yuanzhi Li; Periklis A. Papakonstantinou; Xin Yang (Electron. Colloquium Comput. Complex., 2024)

Engravings, Secrets, and Interpretability of Neural Networks. - Nathaniel Hobbs; Periklis A. Papakonstantinou; Jaideep Vaidya (IEEE Trans. Emerg. Top. Comput., 2024)