Lefteris M. Kirousis

According to our database1, Lefteris M. Kirousis
  • authored at least 85 papers between 1983 and 2017.
  • has a "Dijkstra number"2 of four.

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

On csauthors.net:

Bibliography

2017
Acyclic edge coloring through the Lovász Local Lemma.
Theor. Comput. Sci., 2017

An interactive version of Lovász local lemma: Arthur and Merlin implement Moser's algorithm.
CoRR, 2017

Aggregation of Votes with Multiple Positions on Each Issue.
Proceedings of the Relational and Algebraic Methods in Computer Science, 2017

2016
Thresholds of Random k-Sat.
Encyclopedia of Algorithms, 2016

On the Stability of Generalized Second Price Auctions with Budgets.
Theory Comput. Syst., 2016

A Simple Algorithmic Proof of the Symmetric Lopsided Lovász Local Lemma.
CoRR, 2016

2015
Aggregation of Votes with Multiple Positions on Each Issue.
CoRR, 2015

An alternative proof for the constructive Asymmetric Lovász Local Lemma.
CoRR, 2015

An alternative proof for the constructive Asymmetric Lovász Local Lemma.
Proceedings of the 13th Cologne Twente Workshop on Graphs and Combinatorial Optimization, 2015

On the Algorithmic Lovász Local Lemma and Acyclic Edge Coloring.
Proceedings of the Twelfth Workshop on Analytic Algorithmics and Combinatorics, 2015

2014
On the Algorithmic Lovász Local Lemma.
CoRR, 2014

Optimizing the Social Cost of Congestion Games by Imposing Variable Delays.
CoRR, 2014

On the Stability of Generalized Second Price Auctions with Budgets.
Proceedings of the LATIN 2014: Theoretical Informatics - 11th Latin American Symposium, Montevideo, Uruguay, March 31, 2014

2013
On the Stability of Generalized Second Price Auctions with Budgets.
CoRR, 2013

2009
On the satisfiability threshold of formulas with three literals per clause.
Theor. Comput. Sci., 2009

On the chromatic number of a random 5-regular graph.
Journal of Graph Theory, 2009

Coloring Random Graphs: A Short Survey.
Proceedings of the 11th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, 2009

2008
Thresholds of Random k-Sat.
Proceedings of the Encyclopedia of Algorithms, 2008

A new upper bound for 3-SAT
CoRR, 2008

A new upper bound for 3-SAT.
Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2008

Probabilistic Protocols for Fair Communication in Wireless Sensor Networks.
Proceedings of the Algorithmic Aspects of Wireless Sensor Networks, 2008

2007
The unsatisfiability threshold revisited.
Discrete Applied Mathematics, 2007

2006
The probabilistic analysis of a greedy satisfiability algorithm.
Random Struct. Algorithms, 2006

Approximating Almost All Instances of Max-Cut Within a Ratio Above the Håstad Threshold.
Proceedings of the Algorithms, 2006

2005
Special Issue on Typical Case Complexity and Phase Transitions.
Discrete Applied Mathematics, 2005

Experimental Results for Stackelberg Scheduling Strategies.
Proceedings of the Experimental and Efficient Algorithms, 4th InternationalWorkshop, 2005

5-Regular Graphs are 3-Colorable with Positive Probability.
Proceedings of the Algorithms, 2005

2004
A Dichotomy in the Complexity of Propositional Circumscription.
Theory Comput. Syst., 2004

2003
Locating information with uncertainty in fully interconnected networks: The case of nondistributed memory.
Networks, 2003

The complexity of minimal satisfiability problems.
Inf. Comput., 2003

Preface: Volume 16.
Electronic Notes in Discrete Mathematics, 2003

Selecting Complementary Pairs of Literals.
Electronic Notes in Discrete Mathematics, 2003

2002
Station Layouts in the Presence of Location Constraints.
Journal of Interconnection Networks, 2002

The Probabilistic Analysis of a Greedy Satisfiability Algorithm.
Proceedings of the Algorithms, 2002

2001
Rigorous results for random (2+p)-SAT.
Theor. Comput. Sci., 2001

The unsatisfiability threshold revisited.
Electronic Notes in Discrete Mathematics, 2001

Random Constraint Satisfaction: A More Accurate Picture.
Constraints, 2001

Locating Information with Uncertainty in Fully Interconnected Networks with Applications to World Wide Web Information Retrieval.
Comput. J., 2001

The Complexity of Minimal Satisfiability Problems.
Proceedings of the STACS 2001, 2001

On the Complexity of Model Checking and Inference in Minimal Models.
Proceedings of the Logic Programming and Nonmonotonic Reasoning, 2001

A Dichotomy in the Complexity of Propositional Circumscription.
Proceedings of the 16th Annual IEEE Symposium on Logic in Computer Science, 2001

Coupon Collectors, q-Binomial Coefficients and the Unsatisfiability Threshold.
Proceedings of the Theoretical Computer Science, 7th Italian Conference, 2001

2000
Power consumption in packet radio networks.
Theor. Comput. Sci., 2000

The Complexity of Minimal Satisfiability Problems
Electronic Colloquium on Computational Complexity (ECCC), 2000

On Parallel Partial Solutions and Approximation Schemes for Local Consistency in Networks of Constraints.
Constraints, 2000

A Note on the Non-Colorability Threshold of a Random Graph.
Electr. J. Comb., 2000

Locating Information with Uncertainty in Fully Interconnected Networks.
Proceedings of the Distributed Computing, 14th International Conference, 2000

1999
Station Layouts in the Presence of Location Constraints.
Proceedings of the Algorithms and Computation, 10th International Symposium, 1999

1998
Approximating the unsatisfiability threshold of random formulas.
Random Struct. Algorithms, 1998

1997
Fugitive-Search Games on Graphs and Related Parameters.
Theor. Comput. Sci., 1997

Power Consumption in Packet Radio Networks (Extended Abstract).
Proceedings of the STACS 97, 14th Annual Symposium on Theoretical Aspects of Computer Science, Lübeck, Germany, February 27, 1997

Random Constraint Satisfaction: A More Accurate Picture.
Proceedings of the Principles and Practice of Constraint Programming - CP97, Third International Conference, Linz, Austria, October 29, 1997

1996
The Linkage of a Graph.
SIAM J. Comput., 1996

Simple Atomic Snapshots: A Linear Complexity Solution with Unbounded Time-Stamps.
Inf. Process. Lett., 1996

Approximating the Unsatisfiability Threshold of Random Formulas (Extended Abstract).
Proceedings of the Algorithms, 1996

A better upper bound for the unsatisfiability threshold.
Proceedings of the Satisfiability Problem: Theory and Applications, 1996

1995
Efficient Algorithms for Checking the Atomicity of a Run of Read and Write Operations.
Acta Inf., 1995

Linear-time Parallel Arc Consistency with Reduced Communication Requirements.
Proceedings of the Structure, Information and Communication Complexity, 1995

Partiality and Approximation Schemes for Local Consistency in Networks of Constraints.
Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 1995

Partial Arc Consistency.
Proceedings of the Over-Constrained Systems, 1995

1994
Reading Many Variables in One Atomic Operation: Solutions with Linear or Sublinear Complexity.
IEEE Trans. Parallel Distrib. Syst., 1994

An efficient parallel algorithm for geometrically characterising drawings of a class of 3-D objects.
Journal of Mathematical Imaging and Vision, 1994

Fugitive-Search Games on Graphs and Related Parameters.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 1994

1993
Lower Bounds and Efficient Algorithms for Multiprocessor Scheduling of Directed Acyclic Graphs with Communication Delays
Inf. Comput., July, 1993

Parallel Complexity of the Connected Subgraph Problem.
SIAM J. Comput., 1993

Fast Parallel Constraint Satisfaction .
Artif. Intell., 1993

Efficient Algorithms for Checking the Atomicity of a Run of Read and Write Operations.
Proceedings of the Distributed Algorithms, 7th International Workshop, 1993

Fast Parallel Constraint Satisfaction.
Proceedings of the Automata, Languages and Programming, 20nd International Colloquium, 1993

1992
An Efficient Parallel Algorithm for Geometrically Characterising Drawings of a Class of 3-D Objects.
Proceedings of the Algorithms and Computation, Third International Symposium, 1992

1991
The Complexity of the Reliable Connectivity Problem.
Inf. Process. Lett., 1991

Reading Many Variables in One Atomic Operation: Solutions With Linear or Sublinear Complexity.
Proceedings of the Distributed Algorithms, 5th International Workshop, 1991

The Complexity of The Reliable Connectivity Problem.
Proceedings of the Mathematical Foundations of Computer Science 1991, 1991

Simple Atomic Snapshots: A Linear Complexity Solution with Unbounded Time-Stamps.
Proceedings of the Advances in Computing and Information, 1991

1990
Effectively Labeling Planar Projections of Polyhedra.
IEEE Trans. Pattern Anal. Mach. Intell., 1990

1989
Lower Bounds and Efficient Algorithms for Multiprocessor Scheduling of Dags with Communication Delays.
SPAA, 1989

The Parallel Complexity of the Subgraph Connectivity Problem
Proceedings of the 30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, USA, 30 October, 1989

1988
The Complexity of Recognizing Polyhedral Scenes.
J. Comput. Syst. Sci., 1988

Probabilistic Log-Space Reductions and Problems Probabilistically Hard for P.
Proceedings of the SWAT 88, 1988

A Proof Technique for Register Automicity.
Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 1988

1987
Atomic Multireader Register.
Proceedings of the Distributed Algorithms, 1987

1986
Searching and Pebbling.
Theor. Comput. Sci., 1986

A Polynomial Algorithm for Recognizing Images of Polyhedra.
Proceedings of the VLSI Algorithms and Architectures, 1986

1985
Interval graphs and seatching.
Discrete Mathematics, 1985

The Complexity of Recognizing Polyhedral Scenes (Extended Abstract)
Proceedings of the 26th Annual Symposium on Foundations of Computer Science, 1985

1983
A Selection Theorem.
J. Symb. Log., 1983


  Loading...