Lefteris M. Kirousis

CoRR, 2022

2021

On the Computational Complexity of Non-Dictatorial Aggregation.

[BibT_eX]

[DOI]

J. Artif. Intell. Res., 2021

Correction to: Directed Lovász Local Lemma and Shearer's Lemma.

[BibT_eX]

[DOI]

Ann. Math. Artif. Intell., 2021

2020

Directed Lovász local lemma and Shearer's lemma.

[BibT_eX]

[DOI]

Ann. Math. Artif. Intell., 2020

2019

Aggregation of Votes with Multiple Positions on Each Issue.

[BibT_eX]

[DOI]

ACM Trans. Economics and Comput., 2019

Algorithmically Efficient Syntactic Characterization of Possibility Domains.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

Proceedings of the Learning and Intelligent Optimization - 12th International Conference, 2018

Alternative proofs of the asymmetric Lovász local lemma and Shearer's lemma.

[BibT_eX]

[DOI]

Proceedings of the 11th International Conference on Random and Exhaustive Generation of Combinatorial Structures, 2018

2017

Acyclic edge coloring through the Lovász Local Lemma.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2017

The social cost of congestion games by imposing variable delays.

[BibT_eX]

[DOI]

ICT Express, 2017

2016

Thresholds of Random <i>k</i>-Sat.

[BibT_eX]

[DOI]

Encyclopedia of Algorithms, 2016

On the Stability of Generalized Second Price Auctions with Budgets.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2016

2015

Aggregation of Votes with Multiple Positions on Each Issue.

[BibT_eX]

[DOI]

CoRR, 2015

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

[BibT_eX]

Proceedings of the 13th Cologne Twente Workshop on Graphs and Combinatorial Optimization, 2015

On the Algorithmic Lovász Local Lemma and Acyclic Edge Coloring.

[BibT_eX]

[DOI]

Proceedings of the Twelfth Workshop on Analytic Algorithmics and Combinatorics, 2015

2014

On the Algorithmic Lovász Local Lemma.

[BibT_eX]

[DOI]

CoRR, 2014

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

[BibT_eX]

[DOI]

CoRR, 2014

2009

On the satisfiability threshold of formulas with three literals per clause.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2009

On the chromatic number of a random 5-regular graph.

[BibT_eX]

[DOI]

J. Graph Theory, 2009

Coloring Random Graphs: A Short Survey.

[BibT_eX]

[DOI]

Proceedings of the 11th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, 2009

2008

Thresholds of Random k-Sat.

[BibT_eX]

[DOI]

Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008

A new upper bound for 3-SAT.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

Ioannis Chatzigiannakis

Thodoris Stratiotis

Proceedings of the Algorithmic Aspects of Wireless Sensor Networks, 2008

2006

The probabilistic analysis of a greedy satisfiability algorithm.

[BibT_eX]

[DOI]

Efthimios G. Lalas

Random Struct. Algorithms, 2006

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

[BibT_eX]

[DOI]

Elias C. Stavropoulos

Proceedings of the Algorithms, 2006

The Satisfiability Threshold Conjecture: Techniques Behind Upper Bound Improvements.

[BibT_eX]

Michele Zito

Proceedings of the Computational Complexity and Statistical Physics., 2006

Proving Conditional Randomness using The Principle of Deferred Decisions.

[BibT_eX]

Proceedings of the Computational Complexity and Statistical Physics., 2006

2005

Special Issue on Typical Case Complexity and Phase Transitions.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2005

Experimental Results for Stackelberg Scheduling Strategies.

[BibT_eX]

[DOI]

Efpraxia I. Politopoulou

Dionisios G. Sotiropoulos

Proceedings of the Experimental and Efficient Algorithms, 4th InternationalWorkshop, 2005

5-Regular Graphs are 3-Colorable with Positive Probability.

[BibT_eX]

[DOI]

Proceedings of the Algorithms, 2005

2004

A Dichotomy in the Complexity of Propositional Circumscription.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2004

2003

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

[BibT_eX]

[DOI]

Networks, 2003

Preface: Volume 16.

[BibT_eX]

[DOI]

Electron. Notes Discret. Math., 2003

Selecting Complementary Pairs of Literals.

[BibT_eX]

[DOI]

Efthimios G. Lalas

Electron. Notes Discret. Math., 2003

2002

Station Layouts in the Presence of Location Constraints.

[BibT_eX]

[DOI]

J. Interconnect. Networks, 2002

2001

Rigorous results for random (2+p)-SAT.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2001

The unsatisfiability threshold revisited.

[BibT_eX]

[DOI]

Electron. Notes Discret. Math., 2001

Random Constraint Satisfaction: A More Accurate Picture.

[BibT_eX]

[DOI]

Constraints An Int. J., 2001

Locating Information with Uncertainty in Fully Interconnected Networks with Applications to World Wide Web Information Retrieval.

[BibT_eX]

[DOI]

Elias C. Stavropoulos

Comput. J., 2001

On the Complexity of Model Checking and Inference in Minimal Models.

[BibT_eX]

[DOI]

Proceedings of the Logic Programming and Nonmonotonic Reasoning, 2001

Coupon Collectors, q-Binomial Coefficients and the Unsatisfiability Threshold.

[BibT_eX]

[DOI]

Proceedings of the Theoretical Computer Science, 7th Italian Conference, 2001

2000

Power consumption in packet radio networks.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2000

The Complexity of Minimal Satisfiability Problems

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2000

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

[BibT_eX]

[DOI]

Constraints An Int. J., 2000

A Note on the Non-Colorability Threshold of a Random Graph.

[BibT_eX]

[DOI]

Electron. J. Comb., 2000

Locating Information with Uncertainty in Fully Interconnected Networks.

[BibT_eX]

[DOI]

Proceedings of the Distributed Computing, 14th International Conference, 2000

1998

Approximating the unsatisfiability threshold of random formulas.

[BibT_eX]

[DOI]

Random Struct. Algorithms, 1998

1997

Fugitive-Search Games on Graphs and Related Parameters.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1997

Power Consumption in Packet Radio Networks (Extended Abstract).

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

SIAM J. Comput., 1996

Simple Atomic Snapshots: A Linear Complexity Solution with Unbounded Time-Stamps.

[BibT_eX]

[DOI]

Philippas Tsigas

Inf. Process. Lett., 1996

Approximating the Unsatisfiability Threshold of Random Formulas (Extended Abstract).

[BibT_eX]

[DOI]

Danny Krizanc

Proceedings of the Algorithms, 1996

A better upper bound for the unsatisfiability threshold.

[BibT_eX]

[DOI]

Danny Krizanc

Proceedings of the Satisfiability Problem: Theory and Applications, 1996

1995

Efficient Algorithms for Checking the Atomicity of a Run of Read and Write Operations.

[BibT_eX]

[DOI]

Andreas G. Veneris

Acta Informatica, 1995

Linear-time Parallel Arc Consistency with Reduced Communication Requirements.

[BibT_eX]

Proceedings of the Structure, Information and Communication Complexity, 1995

Partiality and Approximation Schemes for Local Consistency in Networks of Constraints.

[BibT_eX]

[DOI]

Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 1995

Partial Arc Consistency.

[BibT_eX]

[DOI]

Nick Lendris

Proceedings of the Over-Constrained Systems, 1995

1994

Reading Many Variables in One Atomic Operation: Solutions with Linear or Sublinear Complexity.

[BibT_eX]

[DOI]

Philippas Tsigas

IEEE Trans. Parallel Distributed Syst., 1994

An efficient parallel algorithm for geometrically characterising drawings of a class of 3-D objects.

[BibT_eX]

[DOI]

Iannis A. Kalafatis

J. Math. Imaging Vis., 1994

1993

Lower Bounds and Efficient Algorithms for Multiprocessor Scheduling of Directed Acyclic Graphs with Communication Delays

[BibT_eX]

[DOI]

Hermann Jung

Inf. Comput., July, 1993

Parallel Complexity of the Connected Subgraph Problem.

[BibT_eX]

[DOI]

Maria J. Serna

SIAM J. Comput., 1993

Fast Parallel Constraint Satisfaction .

[BibT_eX]

[DOI]

Artif. Intell., 1993

1991

The Complexity of the Reliable Connectivity Problem.

[BibT_eX]

[DOI]

Dimitris Kavadias

Inf. Process. Lett., 1991

1990

Effectively Labeling Planar Projections of Polyhedra.

[BibT_eX]

[DOI]

IEEE Trans. Pattern Anal. Mach. Intell., 1990

1989

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

[BibT_eX]

[DOI]

Hermann Jung

Proceedings of the ACM Symposium on Parallel Algorithms and Architectures, 1989

The Parallel Complexity of the Subgraph Connectivity Problem

[BibT_eX]

[DOI]

Maria J. Serna

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.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1988

Probabilistic Log-Space Reductions and Problems Probabilistically Hard for P.

[BibT_eX]

[DOI]

Proceedings of the SWAT 88, 1988

A Proof Technique for Register Automicity.

[BibT_eX]

[DOI]

Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 1988

1987

Atomic Multireader Register.

[BibT_eX]

[DOI]

Paul M. B. Vitányi

Proceedings of the Distributed Algorithms, 1987

1986

Searching and Pebbling.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1986

A Polynomial Algorithm for Recognizing Images of Polyhedra.

[BibT_eX]

[DOI]

Proceedings of the VLSI Algorithms and Architectures, 1986

1985

Interval graphs and seatching.

[BibT_eX]

[DOI]

Discret. Math., 1985

The Complexity of Recognizing Polyhedral Scenes (Extended Abstract)

[BibT_eX]

[DOI]

Proceedings of the 26th Annual Symposium on Foundations of Computer Science, 1985

1983

A Selection Theorem.

[BibT_eX]

[DOI]