Lefteris M. Kirousis

According to our database1, Lefteris M. Kirousis authored at least 72 papers between 1983 and 2020.

Collaborative distances:
  • Dijkstra number2 of four.
  • Erdős number3 of two.

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepage:

On csauthors.net:

Bibliography

2020
Directed Lovász local lemma and Shearer's lemma.
Ann. Math. Artif. Intell., 2020

2019
Aggregation of Votes with Multiple Positions on Each Issue.
ACM Trans. Economics and Comput., 2019

Algorithmically Efficient Syntactic Characterization of Possibility Domains.
Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

2018
A Simple Algorithmic Proof of the Symmetric Lopsided Lovász Local Lemma.
Proceedings of the Learning and Intelligent Optimization - 12th International Conference, 2018

Alternative proofs of the asymmetric Lovász local lemma and Shearer's lemma.
Proceedings of the 11th International Conference on Random and Exhaustive Generation of Combinatorial Structures, 2018

On the Computational Complexity of Non-dictatorial Aggregation.
Proceedings of the Relational and Algebraic Methods in Computer Science, 2018

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

2016
Thresholds of Random <i>k</i>-Sat.
Encyclopedia of Algorithms, 2016

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

2015
Aggregation of Votes with Multiple Positions on Each Issue.
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

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 Edition, 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

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

The Satisfiability Threshold Conjecture: Techniques Behind Upper Bound Improvements.
Proceedings of the Computational Complexity and Statistical Physics., 2006

Proving Conditional Randomness using The Principle of Deferred Decisions.
Proceedings of the Computational Complexity and Statistical Physics., 2006

2005
Special Issue on Typical Case Complexity and Phase Transitions.
Discret. Appl. Math., 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

Preface: Volume 16.
Electron. Notes Discret. Math., 2003

Selecting Complementary Pairs of Literals.
Electron. Notes Discret. Math., 2003

2002
Station Layouts in the Presence of Location Constraints.
J. Interconnect. Networks, 2002

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

The unsatisfiability threshold revisited.
Electron. Notes Discret. Math., 2001

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

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

On the Complexity of Model Checking and Inference in Minimal Models.
Proceedings of the Logic Programming and Nonmonotonic Reasoning, 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 An Int. J., 2000

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

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

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

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 Informatica, 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.
J. Math. Imaging Vis., 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

1991
The Complexity of the Reliable Connectivity Problem.
Inf. Process. Lett., 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.
Proceedings of the ACM Symposium on Parallel Algorithms and Architectures, 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.
Discret. Math., 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...