On the impossibility of basing identity based encryption on trapdoor permutations D Boneh, P Papakonstantinou, C Rackoff, Y Vahlis, B Waters 2008 49th Annual IEEE Symposium on Foundations of Computer Science, 283-292, 2008 | 67 | 2008 |

On the complexity of constructing Golomb rulers C Meyer, PA Papakonstantinou Discrete applied mathematics 157 (4), 738-748, 2009 | 33 | 2009 |

Width-parametrized SAT: Time--space tradeoffs E Allender, S Chen, T Lou, PA Papakonstantinou, B Tang Theory of Computing 10 (1), 297-339, 2014 | 26 | 2014 |

Complexity and Algorithms for Well-Structured *k*-SAT InstancesK Georgiou, PA Papakonstantinou International Conference on Theory and Applications of Satisfiability …, 2008 | 16 | 2008 |

Space-bounded communication complexity JE Brody, S Chen, PA Papakonstantinou, H Song, X Sun Proceedings of the 4th conference on Innovations in Theoretical Computer …, 2013 | 14 | 2013 |

Depth reduction for composites S Chen, PA Papakonstantinou SIAM Journal on Computing 48 (2), 668-686, 2019 | 12 | 2019 |

Overlays and limited memory communication P Papakonstantinou, D Scheder, H Song 2014 IEEE 29th Conference on Computational Complexity (CCC), 298-308, 2014 | 12 | 2014 |

How powerful are the DDH hard groups? PA Papakonstantinou, C Rackoff, Y Vahlis Electron. Colloquium Comput. Complex. 19, 167, 2012 | 12 | 2012 |

Limits on the stretch of non-adaptive constructions of pseudo-random generators J Bronson, A Juma, PA Papakonstantinou Theory of Cryptography Conference, 504-521, 2011 | 9 | 2011 |

How to accurately and privately identify anomalies H Asif, PA Papakonstantinou, J Vaidya Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications …, 2019 | 8 | 2019 |

Local search for hard sat formulas: the strength of the polynomial law S Liu, P Papakonstantinou Proceedings of the AAAI Conference on Artificial Intelligence 30 (1), 2016 | 8 | 2016 |

How strong is Nisanʼs pseudo-random generator? M David, PA Papakonstantinou, A Sidiropoulos Information processing letters 111 (16), 804-808, 2011 | 8 | 2011 |

A Note on Width-Parameterized SAT: an exact machine-model characterization PA Papakonstantinou Information Processing Letters 110 (1), 8-12, 2009 | 8 | 2009 |

Pseudorandomness for linear length branching programs and stack machines A Bogdanov, PA Papakonstantinou, A Wan Approximation, Randomization, and Combinatorial Optimization. Algorithms and …, 2012 | 7 | 2012 |

Computationally Limited Randomness. M David, P Nguyen, PA Papakonstantinou, A Sidiropoulos ICS, 522-536, 2011 | 6 | 2011 |

Hierarchies for classes of priority algorithms for job scheduling PA Papakonstantinou Theoretical Computer Science 352 (1-3), 181-189, 2006 | 6 | 2006 |

True Randomness from big data PA Papakonstantinou, DP Woodruff, G Yang Scientific reports 6 (1), 1-8, 2016 | 5 | 2016 |

Cryptography with streaming algorithms PA Papakonstantinou, G Yang Annual Cryptology Conference, 55-70, 2014 | 5 | 2014 |

Bagging by Design (on the Suboptimality of Bagging) P Papakonstantinou, J Xu, Z Cao Twenty-Eighth AAAI Conference on Artificial Intelligence, 2014 | 5 | 2014 |

The Depth Irreducibility Hypothesis. PA Papakonstantinou Electron. Colloquium Comput. Complex. 21, 124, 2014 | 5 | 2014 |