| 2019 | ICALP | Algorithmically Efficient Syntactic Characterization of Possibility Domains. | Josep Daz, Lefteris M. Kirousis, Sofia Kokonezi, John Livieratos |
| 2014 | LATIN | On the Stability of Generalized Second Price Auctions with Budgets. | Josep Daz, Ioannis Giotis, Lefteris M. Kirousis, Evangelos Markakis, Maria J. Serna |
| 2009 | SYNASC | Coloring Random Graphs: A Short Survey. | Lefteris M. Kirousis |
| 2008 | Algosensors | Probabilistic Protocols for Fair Communication in Wireless Sensor Networks. | Ioannis Chatzigiannakis, Lefteris M. Kirousis, Thodoris Stratiotis |
| 2006 | ESA | Approximating Almost All Instances of Max-Cut Within a Ratio Above the Hstad Threshold. | Alexis C. Kaporis, Lefteris M. Kirousis, Elias C. Stavropoulos |
| 2005 | ESA | 5-Regular Graphs are 3-Colorable with Positive Probability. | Josep Daz, G. Grammatikopoulos, Alexis C. Kaporis, Lefteris M. Kirousis, Xavier Prez-Gimnez, Dionisios G. Sotiropoulos |
| 2002 | ESA | The Probabilistic Analysis of a Greedy Satisfiability Algorithm. | Alexis C. Kaporis, Lefteris M. Kirousis, Efthimios G. Lalas |
| 2001 | LICS | A Dichotomy in the Complexity of Propositional Circumscription. | Lefteris M. Kirousis, Phokion G. Kolaitis |
| 2001 | LPNMR | On the Complexity of Model Checking and Inference in Minimal Models. | Lefteris M. Kirousis, Phokion G. Kolaitis |
| 2001 | STACS | The Complexity of Minimal Satisfiability Problems. | Lefteris M. Kirousis, Phokion G. Kolaitis |
| 1999 | ISAAC | Station Layouts in the Presence of Location Constraints. | Prosenjit Bose, Christos Kaklamanis, Lefteris M. Kirousis, Evangelos Kranakis, Danny Krizanc, David Peleg |
| 1997 | CP | Random Constraint Satisfaction: A More Accurate Picture. | Dimitris Achlioptas, Lefteris M. Kirousis, Evangelos Kranakis, Danny Krizanc, Michael S. O. Molloy, Yannis C. Stamatiou |
| 1997 | STACS | Power Consumption in Packet Radio Networks (Extended Abstract). | Lefteris M. Kirousis, Evangelos Kranakis, Danny Krizanc, Andrzej Pelc |
| 1996 | ESA | Approximating the Unsatisfiability Threshold of Random Formulas (Extended Abstract). | Lefteris M. Kirousis, Evangelos Kranakis, Danny Krizanc |
| 1995 | CP | Partial Arc Consistency. | Nick Lendris, Lefteris M. Kirousis, Yannis C. Stamatiou, Dimitrios M. Thilikos |
| 1995 | SIROCCO | Linear-time Parallel Arc Consistency with Reduced Communication Requirements. | Nick D. Dendris, Lefteris M. Kirousis |
| 1994 | WG | Fugitive-Search Games on Graphs and Related Parameters. | Nick D. Dendris, Lefteris M. Kirousis, Dimitrios M. Thilikos |
| 1993 | ICALP | Fast Parallel Constraint Satisfaction. | Lefteris M. Kirousis |
| 1992 | ISAAC | An Efficient Parallel Algorithm for Geometrically Characterising Drawings of a Class of 3-D Objects. | Nick D. Dendris, Iannis A. Kalafatis, Lefteris M. Kirousis |
| 1991 | ICCI | Simple Atomic Snapshots: A Linear Complexity Solution with Unbounded Time-Stamps. | Lefteris M. Kirousis, Paul G. Spirakis, Philippas Tsigas |
| 1991 | MFCS | The Complexity of The Reliable Connectivity Problem. | Dimitris Kavadias, Lefteris M. Kirousis, Paul G. Spirakis |
| 1989 | FOCS | The Parallel Complexity of the Subgraph Connectivity Problem | Lefteris M. Kirousis, Maria J. Serna, Paul G. Spirakis |
| 1989 | SPAA | Lower Bounds and Efficient Algorithms for Multiprocessor Scheduling of Dags with Communication Delays. | Hermann Jung, Lefteris M. Kirousis, Paul G. Spirakis |
| 1985 | FOCS | The Complexity of Recognizing Polyhedral Scenes (Extended Abstract) | Lefteris M. Kirousis, Christos H. Papadimitriou |