Periklis A. Papakonstantinou

According to our database, Periklis A. Papakonstantinou authored at least 37 papers between 2006 and 2023.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2023

Identifying Anomalies While Preserving Privacy.

Hafiz Salman Asif, Jaideep Vaidya, Periklis A. Papakonstantinou

IEEE Trans. Knowl. Data Eng., December, 2023

2022

Intelligent Pandemic Surveillance via Privacy-Preserving Crowdsensing.

Hafiz Salman Asif, Periklis A. Papakonstantinou, Stephanie Shiau, Vivek K. Singh, Jaideep Vaidya

IEEE Intell. Syst., 2022

Deep Neural Networks: The Missing Complexity Parameter.

Songhua He, Periklis A. Papakonstantinou

Electron. Colloquium Comput. Complex., 2022

Hide and Seek: Scaling Machine Learning for Combinatorial Optimization via the Probabilistic Method.

Dimitris Achlioptas, Amrit Daswaney, Periklis A. Papakonstantinou

CoRR, 2022

2021

Accurately and Privately Reporting Crowdsensed COVID-19 Data.

Hafiz Salman Asif, Periklis A. Papakonstantinou, Stephanie Shiau, Vivek K. Singh, Jaideep Vaidya

Proceedings of the AMIA 2021, American Medical Informatics Association Annual Symposium, San Diego, CA, USA, October 30, 2021, 2021

2019

How to Accurately and Privately Identify Anomalies.

Hafiz Salman Asif, Periklis A. Papakonstantinou, Jaideep Vaidya

Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security, 2019

2016

Correlation lower bounds from correlation upper bounds.

Shiteng Chen, Periklis A. Papakonstantinou

Inf. Process. Lett., 2016

Depth-reduction for composites.

Shiteng Chen, Periklis A. Papakonstantinou

Electron. Colloquium Comput. Complex., 2016

On the Power and Limits of Distance-Based Learning.

Periklis A. Papakonstantinou, Jia Xu, Guang Yang

Proceedings of the 33nd International Conference on Machine Learning, 2016

Local Search for Hard SAT Formulas: The Strength of the Polynomial Law.

Sixue Liu, Periklis A. Papakonstantinou

Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence, 2016

2014

Width-Parametrized SAT: Time--Space Tradeoffs.

Eric Allender, Shiteng Chen, Tiancheng Lou, Periklis A. Papakonstantinou, Bangsheng Tang

Theory Comput., 2014

The Depth Irreducibility Hypothesis.

Periklis A. Papakonstantinou

Electron. Colloquium Comput. Complex., 2014

Tradeoff lower lounds for stack machines.

Matei David, Periklis A. Papakonstantinou

Comput. Complex., 2014

Cryptography with Streaming Algorithms.

Periklis A. Papakonstantinou, Guang Yang

Proceedings of the Advances in Cryptology - CRYPTO 2014, 2014

Overlays and Limited Memory Communication.

Periklis A. Papakonstantinou, Dominik Scheder, Hao Song

Proceedings of the IEEE 29th Conference on Computational Complexity, 2014

Bagging by Design (on the Suboptimality of Bagging).

Periklis A. Papakonstantinou, Jia Xu, Zhu Cao

Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence, 2014

2013

Overlays and Limited Memory Communication Mode(l)s.

Periklis A. Papakonstantinou, Dominik Scheder, Hao Song

Electron. Colloquium Comput. Complex., 2013

Space-bounded communication complexity.

Joshua Brody, Shiteng Chen, Periklis A. Papakonstantinou, Hao Song, Xiaoming Sun

Proceedings of the Innovations in Theoretical Computer Science, 2013

2012

A remark on one-wayness versus pseudorandomness.

Periklis A. Papakonstantinou, Guang Yang

Electron. Colloquium Comput. Complex., 2012

How powerful are the DDH hard groups?

Periklis A. Papakonstantinou, Charles Rackoff, Yevgeniy Vahlis

Electron. Colloquium Comput. Complex., 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

Pseudorandomness for Linear Length Branching Programs and Stack Machines.

Andrej Bogdanov, Periklis A. Papakonstantinou, Andrew Wan

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2012

2011

How strong is Nisanʼs pseudo-random generator?

Matei David, Periklis A. Papakonstantinou, Anastasios Sidiropoulos

Inf. Process. Lett., 2011

Pseudorandomness for read-once formulas.

Andrej Bogdanov, Periklis A. Papakonstantinou, Andrew Wan

Electron. Colloquium Comput. Complex., 2011

Width-parameterized SAT: Time-Space Tradeoffs

Shiteng Chen, Tiancheng Lou, Periklis A. Papakonstantinou, Bangsheng Tang

CoRR, 2011

Limits on the Stretch of Non-adaptive Constructions of Pseudo-Random Generators.

Josh Bronson, Ali Juma, Periklis A. Papakonstantinou

Proceedings of the Theory of Cryptography - 8th Theory of Cryptography Conference, 2011

Computationally Limited Randomness.

Matei David, Phuong Nguyen, Periklis A. Papakonstantinou, Anastasios Sidiropoulos

Proceedings of the Innovations in Computer Science, 2011

2010

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

Periklis A. Papakonstantinou

PhD thesis, 2010

Characterizing sets of jobs that admit optimal greedy-like algorithms.

Periklis A. Papakonstantinou, Charles Rackoff

J. Sched., 2010

Trade-Off Lower Bounds for Stack Machines.

Matei David, Periklis A. Papakonstantinou

Proceedings of the 25th Annual IEEE Conference on Computational Complexity, 2010

2009

A note on width-parameterized SAT: An exact machine-model characterization.

Periklis A. Papakonstantinou

Inf. Process. Lett., 2009

Polynomial Time with Restricted Use of Randomness.

Matei David, Periklis A. Papakonstantinou, Anastasios Sidiropoulos

Electron. Colloquium Comput. Complex., 2009

On the complexity of constructing Golomb Rulers.

Christophe Meyer, Periklis A. Papakonstantinou

Discret. Appl. Math., 2009

On the Structure of Optimal Greedy Computation (for Job Scheduling).

Periklis A. Papakonstantinou

Proceedings of the Mathematical Foundations of Computer Science 2009, 2009

2008

Complexity and Algorithms for Well-Structured k-SAT Instances.

Konstantinos Georgiou, Periklis A. Papakonstantinou

Proceedings of the Theory and Applications of Satisfiability Testing, 2008

On the Impossibility of Basing Identity Based Encryption on Trapdoor Permutations.

Dan Boneh, Periklis A. Papakonstantinou, Charles Rackoff, Yevgeniy Vahlis, Brent Waters

Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008

2006

Hierarchies for classes of priority algorithms for Job Scheduling.

Periklis A. Papakonstantinou

Theor. Comput. Sci., 2006