Periklis A. Papakonstantinou

47 papers A* 8A 6B 2Misc 2Journal 26Unranked 2

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