Lefteris M. Kirousis

Publication Activity (10 Years)

Years Active: 1983-2022
Publications (10 Years): 19

Top Topics

Computational Complexity

Pure Nash Equilibrium

Spatial Aggregation

Top Venues

Ann. Math. Artif. Intell.

Publications

Lefteris M. Kirousis, John Livieratos
Improved bounds for acyclic coloring parameters. CoRR (2022)
Lefteris M. Kirousis, John Livieratos, Kostas I. Psaromiligkos
Correction to: Directed Lovász Local Lemma and Shearer's Lemma. Ann. Math. Artif. Intell. 89 (3-4) (2021)
John Livieratos, Phokion G. Kolaitis, Lefteris M. Kirousis
On the Computational Complexity of Non-Dictatorial Aggregation. J. Artif. Intell. Res. 72 (2021)
Lefteris M. Kirousis, John Livieratos, Kostas I. Psaromiligkos
Directed Lovász local lemma and Shearer's lemma. Ann. Math. Artif. Intell. 88 (1-3) (2020)
Josep Díaz, Lefteris M. Kirousis, Sofia Kokonezi, John Livieratos
Algorithmically Efficient Syntactic Characterization of Possibility Domains. CoRR (2019)
Lefteris M. Kirousis, Phokion G. Kolaitis, John Livieratos
Aggregation of Votes with Multiple Positions on Each Issue. ACM Trans. Economics and Comput. 7 (1) (2019)
Josep Díaz, Lefteris M. Kirousis, Sofia Kokonezi, John Livieratos
Algorithmically Efficient Syntactic Characterization of Possibility Domains. ICALP (2019)
Lefteris M. Kirousis, Phokion G. Kolaitis, John Livieratos
On the Computational Complexity of Non-dictatorial Aggregation. RAMiCS (2018)
Lefteris M. Kirousis, John Livieratos
A Simple Algorithmic Proof of the Symmetric Lopsided Lovász Local Lemma. LION (2018)
Ioannis Giotis, Lefteris M. Kirousis, John Livieratos, Kostas I. Psaromiligkos, Dimitrios M. Thilikos
Alternative proofs of the asymmetric Lovász local lemma and Shearer's lemma. GASCom (2018)
Ioannis Giotis, Lefteris M. Kirousis, Kostas I. Psaromiligkos, Dimitrios M. Thilikos
Acyclic edge coloring through the Lovász Local Lemma. Theor. Comput. Sci. 665 (2017)
Lefteris M. Kirousis, Phokion G. Kolaitis, John Livieratos
Aggregation of Votes with Multiple Positions on Each Issue. RAMiCS (2017)
Josep Díaz, Ioannis Giotis, Lefteris M. Kirousis, Ioannis Mourtos, Maria J. Serna
The social cost of congestion games by imposing variable delays. ICT Express 3 (4) (2017)
Josep Díaz, Ioannis Giotis, Lefteris M. Kirousis, Evangelos Markakis, Maria J. Serna
On the Stability of Generalized Second Price Auctions with Budgets. Theory Comput. Syst. 59 (1) (2016)
Lefteris M. Kirousis, John Livieratos
A Simple Algorithmic Proof of the Symmetric Lopsided Lovász Local Lemma. CoRR (2016)
Ioannis Giotis, Lefteris M. Kirousis, Kostas I. Psaromiligkos, Dimitrios M. Thilikos
On the Algorithmic Lovász Local Lemma and Acyclic Edge Coloring. ANALCO (2015)
Ioannis Giotis, Lefteris M. Kirousis, Kostas I. Psaromiligkos, Dimitrios M. Thilikos
An alternative proof for the constructive Asymmetric Lovász Local Lemma. CTW (2015)
Ioannis Giotis, Lefteris M. Kirousis, Kostas I. Psaromiligkos, Dimitrios M. Thilikos
An alternative proof for the constructive Asymmetric Lovász Local Lemma. CoRR (2015)
Lefteris M. Kirousis, Phokion G. Kolaitis
Aggregation of Votes with Multiple Positions on Each Issue. CoRR (2015)
Josep Díaz, Ioannis Giotis, Lefteris M. Kirousis, Yiannis Mourtos, Maria J. Serna
Optimizing the Social Cost of Congestion Games by Imposing Variable Delays. CoRR (2014)
Ioannis Giotis, Lefteris M. Kirousis, Kostas I. Psaromiligkos, Dimitrios M. Thilikos
On the Algorithmic Lovász Local Lemma. CoRR (2014)
Josep Díaz, Ioannis Giotis, Lefteris M. Kirousis, Evangelos Markakis, Maria J. Serna
On the Stability of Generalized Second Price Auctions with Budgets. LATIN (2014)
Josep Díaz, Ioannis Giotis, Lefteris M. Kirousis, Evangelos Markakis, Maria J. Serna
On the Stability of Generalized Second Price Auctions with Budgets. CoRR (2013)
Josep Díaz, Lefteris M. Kirousis, Dieter Mitsche, Xavier Pérez-Giménez
On the satisfiability threshold of formulas with three literals per clause. Theor. Comput. Sci. 410 (30-32) (2009)
Lefteris M. Kirousis
Coloring Random Graphs: A Short Survey. SYNASC (2009)
Josep Díaz, Alexis C. Kaporis, G. D. Kemkes, Lefteris M. Kirousis, Xavier Pérez, Nicholas C. Wormald
On the chromatic number of a random 5-regular graph. J. Graph Theory 61 (3) (2009)
Ioannis Chatzigiannakis, Lefteris M. Kirousis, Thodoris Stratiotis
Probabilistic Protocols for Fair Communication in Wireless Sensor Networks. ALGOSENSORS (2008)
Josep Díaz, Lefteris M. Kirousis, Dieter Mitsche, Xavier Pérez-Giménez
A new upper bound for 3-SAT. FSTTCS (2008)
Josep Díaz, Lefteris M. Kirousis, Dieter Mitsche, Xavier Pérez-Giménez
A new upper bound for 3-SAT CoRR (2008)
Alexis C. Kaporis, Lefteris M. Kirousis, Yannis C. Stamatiou, Malvina Vamvakari, Michele Zito
The unsatisfiability threshold revisited. Discret. Appl. Math. 155 (12) (2007)
Alexis C. Kaporis, Lefteris M. Kirousis, Elias C. Stavropoulos
Approximating Almost All Instances of Max-Cut Within a Ratio Above the Håstad Threshold. ESA (2006)
Alexis C. Kaporis, Lefteris M. Kirousis, Efthimios G. Lalas
The probabilistic analysis of a greedy satisfiability algorithm. Random Struct. Algorithms 28 (4) (2006)
Alexis C. Kaporis, Lefteris M. Kirousis, Efpraxia I. Politopoulou, Paul G. Spirakis
Experimental Results for Stackelberg Scheduling Strategies. WEA (2005)
Josep Díaz, G. Grammatikopoulos, Alexis C. Kaporis, Lefteris M. Kirousis, Xavier Pérez, Dionisios G. Sotiropoulos
5-Regular Graphs are 3-Colorable with Positive Probability. ESA (2005)
Lefteris M. Kirousis, Evangelos Kranakis
Special Issue on Typical Case Complexity and Phase Transitions. Discret. Appl. Math. 153 (1-3) (2005)
Lefteris M. Kirousis, Phokion G. Kolaitis
A Dichotomy in the Complexity of Propositional Circumscription. Theory Comput. Syst. 37 (6) (2004)
Evangelos Kranakis, Lefteris M. Kirousis
Preface: Volume 16. Electron. Notes Discret. Math. 16 (2003)
Alexis C. Kaporis, Lefteris M. Kirousis, Efthimios G. Lalas
Selecting Complementary Pairs of Literals. Electron. Notes Discret. Math. 16 (2003)
Lefteris M. Kirousis, Phokion G. Kolaitis
The complexity of minimal satisfiability problems. Inf. Comput. 187 (1) (2003)
Lefteris M. Kirousis, Evangelos Kranakis, Danny Krizanc, Yannis C. Stamatiou
Locating information with uncertainty in fully interconnected networks: The case of nondistributed memory. Networks 42 (3) (2003)
Alexis C. Kaporis, Lefteris M. Kirousis, Efthimios G. Lalas
The Probabilistic Analysis of a Greedy Satisfiability Algorithm. ESA (2002)
Prosenjit Bose, Evangelos Kranakis, Christos Kaklamanis, Lefteris M. Kirousis, Danny Krizanc, David Peleg
Station Layouts in the Presence of Location Constraints. J. Interconnect. Networks 3 (1-2) (2002)
Alexis C. Kaporis, Lefteris M. Kirousis, Yannis C. Stamatiou, Malvina Vamvakari, Michele Zito
The unsatisfiability threshold revisited. Electron. Notes Discret. Math. 9 (2001)
Lefteris M. Kirousis, Phokion G. Kolaitis
A Dichotomy in the Complexity of Propositional Circumscription. LICS (2001)
Alexis C. Kaporis, Lefteris M. Kirousis, Evangelos Kranakis, Danny Krizanc, Yannis C. Stamatiou, Elias C. Stavropoulos
Locating Information with Uncertainty in Fully Interconnected Networks with Applications to World Wide Web Information Retrieval. Comput. J. 44 (4) (2001)
Lefteris M. Kirousis, Phokion G. Kolaitis
On the Complexity of Model Checking and Inference in Minimal Models. LPNMR (2001)
Alexis C. Kaporis, Lefteris M. Kirousis, Yannis C. Stamatiou, Malvina Vamvakari, Michele Zito
Coupon Collectors, q-Binomial Coefficients and the Unsatisfiability Threshold. ICTCS (2001)
Dimitris Achlioptas, Lefteris M. Kirousis, Evangelos Kranakis, Danny Krizanc
Rigorous results for random (2+p)-SAT. Theor. Comput. Sci. 265 (1-2) (2001)
Dimitris Achlioptas, Michael S. O. Molloy, Lefteris M. Kirousis, Yannis C. Stamatiou, Evangelos Kranakis, Danny Krizanc
Random Constraint Satisfaction: A More Accurate Picture. Constraints An Int. J. 6 (4) (2001)
Lefteris M. Kirousis, Phokion G. Kolaitis
The Complexity of Minimal Satisfiability Problems. STACS (2001)
Lefteris M. Kirousis, Phokion G. Kolaitis
The Complexity of Minimal Satisfiability Problems Electron. Colloquium Comput. Complex. 7 (82) (2000)
Nick D. Dendris, Lefteris M. Kirousis, Yannis C. Stamatiou, Dimitrios M. Thilikos
On Parallel Partial Solutions and Approximation Schemes for Local Consistency in Networks of Constraints. Constraints An Int. J. 5 (3) (2000)
Lefteris M. Kirousis, Evangelos Kranakis, Danny Krizanc, Andrzej Pelc
Power consumption in packet radio networks. Theor. Comput. Sci. 243 (1-2) (2000)
Lefteris M. Kirousis, Evangelos Kranakis, Danny Krizanc, Yannis C. Stamatiou
Locating Information with Uncertainty in Fully Interconnected Networks. DISC (2000)
Alexis C. Kaporis, Lefteris M. Kirousis, Yannis C. Stamatiou
A Note on the Non-Colorability Threshold of a Random Graph. Electron. J. Comb. 7 (2000)
Prosenjit Bose, Christos Kaklamanis, Lefteris M. Kirousis, Evangelos Kranakis, Danny Krizanc, David Peleg
Station Layouts in the Presence of Location Constraints. ISAAC (1999)
Lefteris M. Kirousis, Evangelos Kranakis, Danny Krizanc, Yannis C. Stamatiou
Approximating the unsatisfiability threshold of random formulas. Random Struct. Algorithms 12 (3) (1998)
Lefteris M. Kirousis, Evangelos Kranakis, Danny Krizanc, Andrzej Pelc
Power Consumption in Packet Radio Networks (Extended Abstract). STACS (1997)
Dimitris Achlioptas, Lefteris M. Kirousis, Evangelos Kranakis, Danny Krizanc, Michael S. O. Molloy, Yannis C. Stamatiou
Random Constraint Satisfaction: A More Accurate Picture. CP (1997)
Nick D. Dendris, Lefteris M. Kirousis, Dimitrios M. Thilikos
Fugitive-Search Games on Graphs and Related Parameters. Theor. Comput. Sci. 172 (1-2) (1997)
Lefteris M. Kirousis, Evangelos Kranakis, Danny Krizanc
Approximating the Unsatisfiability Threshold of Random Formulas (Extended Abstract). ESA (1996)
Lefteris M. Kirousis, Evangelos Kranakis, Danny Krizanc
A better upper bound for the unsatisfiability threshold. Satisfiability Problem: Theory and Applications (1996)
Lefteris M. Kirousis, Paul G. Spirakis, Philippas Tsigas
Simple Atomic Snapshots: A Linear Complexity Solution with Unbounded Time-Stamps. Inf. Process. Lett. 58 (1) (1996)
Lefteris M. Kirousis, Dimitrios M. Thilikos
The Linkage of a Graph. SIAM J. Comput. 25 (3) (1996)
Nick D. Dendris, Lefteris M. Kirousis
Linear-time Parallel Arc Consistency with Reduced Communication Requirements. SIROCCO (1995)
Nick Lendris, Lefteris M. Kirousis, Yannis C. Stamatiou, Dimitrios M. Thilikos
Partial Arc Consistency. Over-Constrained Systems (1995)
Nick D. Dendris, Lefteris M. Kirousis, Yannis C. Stamatiou, Dimitrios M. Thilikos
Partiality and Approximation Schemes for Local Consistency in Networks of Constraints. FSTTCS (1995)
Lefteris M. Kirousis, Andreas G. Veneris
Efficient Algorithms for Checking the Atomicity of a Run of Read and Write Operations. Acta Informatica 32 (2) (1995)
Nick D. Dendris, Iannis A. Kalafatis, Lefteris M. Kirousis
An efficient parallel algorithm for geometrically characterising drawings of a class of 3-D objects. J. Math. Imaging Vis. 4 (4) (1994)
Nick D. Dendris, Lefteris M. Kirousis, Dimitrios M. Thilikos
Fugitive-Search Games on Graphs and Related Parameters. WG (1994)
Lefteris M. Kirousis, Paul G. Spirakis, Philippas Tsigas
Reading Many Variables in One Atomic Operation: Solutions with Linear or Sublinear Complexity. IEEE Trans. Parallel Distributed Syst. 5 (7) (1994)
Lefteris M. Kirousis, Maria J. Serna, Paul G. Spirakis
Parallel Complexity of the Connected Subgraph Problem. SIAM J. Comput. 22 (3) (1993)
Lefteris M. Kirousis, Andreas G. Veneris
Efficient Algorithms for Checking the Atomicity of a Run of Read and Write Operations. WDAG (1993)
Lefteris M. Kirousis
Fast Parallel Constraint Satisfaction . Artif. Intell. 64 (1) (1993)
Hermann Jung, Lefteris M. Kirousis, Paul G. Spirakis
Lower Bounds and Efficient Algorithms for Multiprocessor Scheduling of Directed Acyclic Graphs with Communication Delays Inf. Comput. 105 (1) (1993)
Lefteris M. Kirousis
Fast Parallel Constraint Satisfaction. ICALP (1993)
Nick D. Dendris, Iannis A. Kalafatis, Lefteris M. Kirousis
An Efficient Parallel Algorithm for Geometrically Characterising Drawings of a Class of 3-D Objects. ISAAC (1992)
Lefteris M. Kirousis, Paul G. Spirakis, Philippas Tsigas
Reading Many Variables in One Atomic Operation: Solutions With Linear or Sublinear Complexity. WDAG (1991)
Dimitris Kavadias, Lefteris M. Kirousis, Paul G. Spirakis
The Complexity of The Reliable Connectivity Problem. MFCS (1991)
Lefteris M. Kirousis, Paul G. Spirakis, Philippas Tsigas
Simple Atomic Snapshots: A Linear Complexity Solution with Unbounded Time-Stamps. ICCI (1991)
Dimitris Kavadias, Lefteris M. Kirousis, Paul G. Spirakis
The Complexity of the Reliable Connectivity Problem. Inf. Process. Lett. 39 (5) (1991)
Lefteris M. Kirousis
Effectively Labeling Planar Projections of Polyhedra. IEEE Trans. Pattern Anal. Mach. Intell. 12 (2) (1990)
Hermann Jung, Lefteris M. Kirousis, Paul G. Spirakis
Lower Bounds and Efficient Algorithms for Multiprocessor Scheduling of Dags with Communication Delays. SPAA (1989)
Lefteris M. Kirousis, Maria J. Serna, Paul G. Spirakis
The Parallel Complexity of the Subgraph Connectivity Problem FOCS (1989)
Lefteris M. Kirousis, Christos H. Papadimitriou
The Complexity of Recognizing Polyhedral Scenes. J. Comput. Syst. Sci. 37 (1) (1988)
Baruch Awerbuch, Lefteris M. Kirousis, Evangelos Kranakis, Paul M. B. Vitányi
A Proof Technique for Register Automicity. FSTTCS (1988)
Lefteris M. Kirousis, Paul G. Spirakis
Probabilistic Log-Space Reductions and Problems Probabilistically Hard for P. SWAT (1988)
Lefteris M. Kirousis, Evangelos Kranakis, Paul M. B. Vitányi
Atomic Multireader Register. WDAG (1987)
Lefteris M. Kirousis
A Polynomial Algorithm for Recognizing Images of Polyhedra. Aegean Workshop on Computing (1986)
Lefteris M. Kirousis, Christos H. Papadimitriou
Searching and Pebbling. Theor. Comput. Sci. 47 (3) (1986)
Lefteris M. Kirousis, Christos H. Papadimitriou
Interval graphs and seatching. Discret. Math. 55 (2) (1985)
Lefteris M. Kirousis, Christos H. Papadimitriou
The Complexity of Recognizing Polyhedral Scenes (Extended Abstract) FOCS (1985)
Lefteris M. Kirousis
A Selection Theorem. J. Symb. Log. 48 (3) (1983)