Periklis A. Papakonstantinou

Publication Activity (10 Years)

Years Active: 2006-2023
Publications (10 Years): 12

Top Topics

Combinatorial Optimization

Randomly Chosen

Quasi Newton Method

Top Venues

Electron. Colloquium Comput. Complex.

IEEE Intell. Syst.

Publications

Hafiz Salman Asif, Jaideep Vaidya, Periklis A. Papakonstantinou
Identifying Anomalies While Preserving Privacy. IEEE Trans. Knowl. Data Eng. 35 (12) (2023)
Songhua He, Periklis A. Papakonstantinou
Deep Neural Networks: The Missing Complexity Parameter. Electron. Colloquium Comput. Complex. (2022)
Dimitris Achlioptas, Amrit Daswaney, Periklis A. Papakonstantinou
Hide and Seek: Scaling Machine Learning for Combinatorial Optimization via the Probabilistic Method. CoRR (2022)
Hafiz Salman Asif, Periklis A. Papakonstantinou, Stephanie Shiau, Vivek Singh, Jaideep Vaidya
Intelligent Pandemic Surveillance via Privacy-Preserving Crowdsensing. IEEE Intell. Syst. 37 (4) (2022)
Hafiz Salman Asif, Periklis A. Papakonstantinou, Stephanie Shiau, Vivek K. Singh, Jaideep Vaidya
Accurately and Privately Reporting Crowdsensed COVID-19 Data. AMIA (2021)
Hafiz Salman Asif, Periklis A. Papakonstantinou, Jaideep Vaidya
How to Accurately and Privately Identify Anomalies. CCS (2019)
Shiteng Chen, Periklis A. Papakonstantinou
Depth Reduction for Composites. SIAM J. Comput. 48 (2) (2019)
Periklis A. Papakonstantinou, Jia Xu, Guang Yang
On the Power and Limits of Distance-Based Learning. ICML (2016)
Sixue Liu, Periklis A. Papakonstantinou
Local Search for Hard SAT Formulas: The Strength of the Polynomial Law. AAAI (2016)
Shiteng Chen, Periklis A. Papakonstantinou
Depth-Reduction for Composites. FOCS (2016)
Shiteng Chen, Periklis A. Papakonstantinou
Correlation lower bounds from correlation upper bounds. Inf. Process. Lett. 116 (8) (2016)
Shiteng Chen, Periklis A. Papakonstantinou
Depth-reduction for composites. Electron. Colloquium Comput. Complex. 23 (2016)
Shiteng Chen, Periklis A. Papakonstantinou
Correlation lower bounds from correlation upper bounds. Electron. Colloquium Comput. Complex. 22 (2015)
Periklis A. Papakonstantinou, Jia Xu, Zhu Cao
Bagging by Design (on the Suboptimality of Bagging). AAAI (2014)
Periklis A. Papakonstantinou, Dominik Scheder, Hao Song
Overlays and Limited Memory Communication. Computational Complexity Conference (2014)
Periklis A. Papakonstantinou, Guang Yang
Cryptography with Streaming Algorithms. CRYPTO (2) (2014)
Periklis A. Papakonstantinou
The Depth Irreducibility Hypothesis. Electron. Colloquium Comput. Complex. 21 (2014)
Eric Allender, Shiteng Chen, Tiancheng Lou, Periklis A. Papakonstantinou, Bangsheng Tang
Width-Parametrized SAT: Time--Space Tradeoffs. Theory Comput. 10 (2014)
Matei David, Periklis A. Papakonstantinou
Tradeoff lower lounds for stack machines. Comput. Complex. 23 (1) (2014)
Periklis A. Papakonstantinou, Dominik Scheder, Hao Song
Overlays and Limited Memory Communication Mode(l)s. Electron. Colloquium Comput. Complex. 20 (2013)
Joshua Brody, Shiteng Chen, Periklis A. Papakonstantinou, Hao Song, Xiaoming Sun
Space-bounded communication complexity. ITCS (2013)
Andrej Bogdanov, Periklis A. Papakonstantinou, Andrew Wan
Pseudorandomness for Linear Length Branching Programs and Stack Machines. APPROX-RANDOM (2012)
Periklis A. Papakonstantinou, Guang Yang
A remark on one-wayness versus pseudorandomness. Electron. Colloquium Comput. Complex. 19 (2012)
Periklis A. Papakonstantinou, Charles Rackoff, Yevgeniy Vahlis
How powerful are the DDH hard groups? Electron. Colloquium Comput. Complex. 19 (2012)
Periklis A. Papakonstantinou, Guang Yang
A Remark on One-Wayness versus Pseudorandomness. COCOON (2012)
Eric Allender, Shiteng Chen, Tiancheng Lou, Periklis A. Papakonstantinou, Bangsheng Tang
Time-space tradeoffs for width-parameterized SAT: Algorithms and lower bounds. Electron. Colloquium Comput. Complex. 19 (2012)
Periklis A. Papakonstantinou, Charles Rackoff, Yevgeniy Vahlis
How powerful are the DDH hard groups? IACR Cryptol. ePrint Arch. 2012 (2012)
Matei David, Periklis A. Papakonstantinou, Anastasios Sidiropoulos
How strong is Nisanʼs pseudo-random generator? Inf. Process. Lett. 111 (16) (2011)
Andrej Bogdanov, Periklis A. Papakonstantinou, Andrew Wan
Pseudorandomness for read-once formulas. Electron. Colloquium Comput. Complex. 18 (2011)
Josh Bronson, Ali Juma, Periklis A. Papakonstantinou
Limits on the Stretch of Non-adaptive Constructions of Pseudo-Random Generators. TCC (2011)
Andrej Bogdanov, Periklis A. Papakonstantinou, Andrew Wan
Pseudorandomness for Read-Once Formulas. FOCS (2011)
Shiteng Chen, Tiancheng Lou, Periklis A. Papakonstantinou, Bangsheng Tang
Width-parameterized SAT: Time-Space Tradeoffs CoRR (2011)
Matei David, Phuong Nguyen, Periklis A. Papakonstantinou, Anastasios Sidiropoulos
Computationally Limited Randomness. ICS (2011)
Periklis A. Papakonstantinou, Charles Rackoff
Characterizing sets of jobs that admit optimal greedy-like algorithms. J. Sched. 13 (2) (2010)
Matei David, Periklis A. Papakonstantinou
Trade-Off Lower Bounds for Stack Machines. Computational Complexity Conference (2010)
Matei David, Periklis A. Papakonstantinou, Anastasios Sidiropoulos
Polynomial Time with Restricted Use of Randomness. Electron. Colloquium Comput. Complex. 16 (2009)
Periklis A. Papakonstantinou
A note on width-parameterized SAT: An exact machine-model characterization. Inf. Process. Lett. 110 (1) (2009)
Periklis A. Papakonstantinou
On the Structure of Optimal Greedy Computation (for Job Scheduling). MFCS (2009)
Christophe Meyer, Periklis A. Papakonstantinou
On the complexity of constructing Golomb Rulers. Discret. Appl. Math. 157 (4) (2009)
Konstantinos Georgiou, Periklis A. Papakonstantinou
Complexity and Algorithms for Well-Structured k-SAT Instances. SAT (2008)
Dan Boneh, Periklis A. Papakonstantinou, Charles Rackoff, Yevgeniy Vahlis, Brent Waters
On the Impossibility of Basing Identity Based Encryption on Trapdoor Permutations. FOCS (2008)
Periklis A. Papakonstantinou
Hierarchies for classes of priority algorithms for Job Scheduling. Theor. Comput. Sci. 352 (1-3) (2006)