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 | 83 | 2008 |

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

Width-parameterized SAT: Time-space tradeoffs E Allender, S Chen, T Lou, P Papakonstantinou, B Tang Theory of Computing 10 (12), 297-339, 2014 | 30 | 2014 |

How powerful are the DDH hard groups? PA Papakonstantinou, CW Rackoff, Y Vahlis Cryptology ePrint Archive, 2012 | 28 | 2012 |

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 | 16 | 2019 |

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

Complexity and Algorithms for Well-Structured *k*-SAT InstancesK Georgiou, PA Papakonstantinou International Conference on Theory and Applications of Satisfiability …, 2008 | 15 | 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 | 13 | 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 | 11 | 2016 |

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

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

Limits on the stretch of non-adaptive constructions of pseudo-random generators J Bronson, A Juma, PA Papakonstantinou Theory of Cryptography: 8th Theory of Cryptography Conference, TCC 2011 …, 2011 | 9 | 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 |

True randomness from big data PA Papakonstantinou, DP Woodruff, G Yang Scientific reports 6 (1), 33740, 2016 | 6 | 2016 |

Bagging by Design (on the Suboptimality of Bagging) P Papakonstantinou, J Xu, Z Cao Proceedings of the AAAI Conference on Artificial Intelligence 28 (1), 2014 | 6 | 2014 |

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

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

Overlays and limited memory communication mode (l) s P Papakonstantinou, D Scheder, H Song Proc. of the 29th Conference on Computational Complexity, 2014 | 5 | 2014 |