Fotis Iliopoulos

University of California, Berkeley

Author Statistics

Papers

Citation

H-Index

i-10 index

Research Trends

Author Order

Document Type

Co-Authors

Dimitris Achlioptas

National and Kapodistrian University of Athens

Alistair Sinclair

University of California, Berkeley

Vladimir Kolmogorov

Institute of Science and Technology Austria

Erik Vee

Google (United States)

Themis Gouleakis

National University of Singapore

Gaurav Menghani

Stony Brook University

Cenk Baykal

Massachusetts Institute of Technology

David G. Harris

University of Maryland, College Park

Khoa Trinh

University of Maryland, College Park

Vasilis Kontonis

The University of Texas at Austin

Cooperative Institutions

Google (United States)

Massachusetts Institute of Technology

Institute of Science and Technology Austria

Microsoft Research (United Kingdom)

University of California, Berkeley

Microsoft (United States)

University College London

Sichuan University

National and Kapodistrian University of Athens

Max Planck Institute for Informatics

Author Statistics

Papers

Citation

H-Index

i-10 index

Research Field

Random Walks that Find Perfect Objects and the Lovász Local Lemma

arXiv (Cornell University) (2014)

Dimitris Achlioptas Fotis Iliopoulos

We give an algorithmic local lemma by establishing a sufficient condition for the uniform random walk on a directed graph to reach a sink quickly. Our work is inspired by Moser's entropic method proof of the Lovász Local Lemma (LLL) for satisfiability and completely bypasses the Probabilistic Method formulation of the LLL. In particular, our method works when the underlying state space is entirely unstructured. Similarly to Moser's argument, the key point is that the inevitability of reaching a sink is established by bounding the entropy of the walk as a function of time.

Lemma (botany)

Bounding overwatch

Satisfiability

10.48550/arxiv.1406.0242

Cite

Citations (0)

Random Walks That Find Perfect Objects and the Lovász Local Lemma

Trends in mathematics (2017)

Dimitris Achlioptas Fotis Iliopoulos

Lemma (botany)

Bounding overwatch

Satisfiability

10.1007/978-3-319-51753-7_2

Cite

Citations (3)

Beyond the Lovász Local Lemma: Point to Set Correlations and Their Algorithmic Applications

Dimitris Achlioptas Fotis Iliopoulos Alistair Sinclair

Following the groundbreaking algorithm of Moser and Tardos for the Lovasz Local Lemma (LLL), there has been a plethora of results analyzing local search algorithms for various constraint satisfaction problems. The algorithms considered fall into two broad categories: resampling algorithms, analyzed via different algorithmic LLL conditions; and backtracking algorithms, analyzed via entropy compression arguments. This paper introduces a new convergence condition that seamlessly handles resampling, backtracking, and hybrid algorithms, i.e., algorithms that perform both resampling and backtracking steps. Unlike previous work on the LLL, our condition replaces the notion of a dependency or causality graph by quantifying point-to-set correlations between bad events. As a result, our condition simultaneously: (i) captures the most general algorithmic LLL condition known as a special case; (ii) significantly simplifies the analysis of entropy compression applications; (iii) relates backtracking algorithms, which are conceptually very different from resampling algorithms, to the LLL; and most importantly (iv) allows for the analysis of hybrid algorithms, which were outside the scope of previous techniques. We give several applications of our condition, including a new hybrid vertex coloring algorithm that extends the recent breakthrough result of Molloy for coloring triangle-free graphs to arbitrary graphs.

Backtracking

Resampling

10.1109/focs.2019.00049

Cite

Citations (20)

Commutative Algorithms Approximate the LLL-distribution

arXiv (Cornell University) (2017)

Fotis Iliopoulos

Following the groundbreaking Moser-Tardos algorithm for the Lovasz Local Lemma (LLL), a series of works have exploited a key ingredient of the original analysis, the witness tree lemma, in order to: derive deterministic, parallel and distributed algorithms for the LLL, to estimate the entropy of the output distribution, to partially avoid bad events, to deal with super-polynomially many bad events, and even to devise new algorithmic frameworks. Meanwhile, a parallel line of work, has established tools for analyzing stochastic local search algorithms motivated by the LLL that do not fall within the Moser-Tardos framework. Unfortunately, the aforementioned results do not transfer to these more general settings. Mainly, this is because the witness tree lemma, provably, no longer holds. Here we prove that for commutative algorithms, a class recently introduced by Kolmogorov and which captures the vast majority of LLL applications, the witness tree lemma does hold. Armed with this fact, we extend the main result of Haeupler, Saha, and Srinivasan to commutative algorithms, establishing that the output of such algorithms well-approximates the LLL-distribution, i.e., the distribution obtained by conditioning on all bad events being avoided, and give several new applications. For example, we show that the recent algorithm of Molloy for list coloring number of sparse, triangle-free graphs can output exponential many list colorings of the input graph.

Lemma (botany)

Tree (set theory)

10.48550/arxiv.1704.02796

Cite

Citations (1)

Random Walks That Find Perfect Objects and the Lovász Local Lemma

Journal of the ACM (2016)

Dimitris Achlioptas Fotis Iliopoulos

We give an algorithmic local lemma by establishing a sufficient condition for the uniform random walk on a directed graph to reach a sink quickly. Our work is inspired by Moser’s entropic method proof of the Lovász Local Lemma (LLL) for satisfiability and completely bypasses the Probabilistic Method formulation of the LLL. In particular, our method works when the underlying state space is entirely unstructured. Similarly to Moser’s argument, the key point is that the inevitability of reaching a sink is established by bounding the entropy of the walk as a function of time.

Lemma (botany)

Satisfiability

Bounding overwatch

10.1145/2818352

Cite

Citations (36)

Focused Stochastic Local Search and the Lovász Local Lemma

Dimitris Achlioptas Fotis Iliopoulos

We develop tools for analyzing focused stochastic local search algorithms. These are algorithms that search a state space probabilistically by repeatedly selecting a constraint that is violated in the current state and moving to a random nearby state which, hopefully, addresses the violation without introducing many new ones. A large class of such algorithms arise from algorithmizations of the Lovász Local Lemma, a non-constructive tool for proving the existence of satisfying states. Here we give tools that provide a unified analysis of such algorithms and of many more, expressing them as instances of a general framework.

Lemma (botany)

Constructive

Guided Local Search

10.1137/1.9781611974331.ch141

Cite

Citations (2)

Focused stochastic local search and the lovász local lemma

Dimitris Achlioptas Fotis Iliopoulos

We develop tools for analyzing focused stochastic local search algorithms. These are algorithms that search a state space probabilistically by repeatedly selecting a constraint that is violated in the current state and moving to a random nearby state which, hopefully, addresses the violation without introducing many new ones. A large class of such algorithms arise from algorithmizations of the Lovasz Local Lemma, a non-constructive tool for proving the existence of satisfying states. Here we give tools that provide a unified analysis of such algorithms and of many more, expressing them as instances of a general framework.

Lemma (botany)

Constructive

Guided Local Search

10.5555/2884435.2884576

Cite

Citations (9)

Local Computation Algorithms for the Lovász Local Lemma

arXiv (Cornell University) (2018)

Dimitris Achlioptas Themis Gouleakis Fotis Iliopoulos

Lemma (botany)

Source

Cite

Citations (1)

Robust Active Distillation

arXiv (Cornell University) (2022)

Cenk Baykal Khoa Trinh Fotis Iliopoulos Gaurav Menghani Erik Vee

Distilling knowledge from a large teacher model to a lightweight one is a widely successful approach for generating compact, powerful models in the semi-supervised learning setting where a limited amount of labeled data is available. In large-scale applications, however, the teacher tends to provide a large number of incorrect soft-labels that impairs student performance. The sheer size of the teacher additionally constrains the number of soft-labels that can be queried due to prohibitive computational and/or financial costs. The difficulty in achieving simultaneous \emph{efficiency} (i.e., minimizing soft-label queries) and \emph{robustness} (i.e., avoiding student inaccuracies due to incorrect labels) hurts the widespread application of knowledge distillation to many modern tasks. In this paper, we present a parameter-free approach with provable guarantees to query the soft-labels of points that are simultaneously informative and correctly labeled by the teacher. At the core of our work lies a game-theoretic formulation that explicitly considers the inherent trade-off between the informativeness and correctness of input instances. We establish bounds on the expected performance of our approach that hold even in worst-case distillation instances. We present empirical evaluations on popular benchmarks that demonstrate the improved distillation performance enabled by our work relative to that of state-of-the-art active learning and active distillation methods.

Robustness

10.48550/arxiv.2210.01213

Cite

Citations (3)

Group testing and local search: is there a computational-statistical gap?

Conference on Learning Theory (2021)

Fotis Iliopoulos Ilias Zadik

Group testing is a fundamental problem in statistical inference with many real-world applications, including the need for massive group testing during the ongoing COVID-19 pandemic. In this paper we study the task of approximate recovery, in which we tolerate having a small number of incorrectly classified items. One of the most well-known, optimal, and easy to implement testing procedures is the non-adaptive Bernoulli group testing, where all tests are conducted in parallel, and each item is chosen to be part of any certain test independently with some fixed probability. In this setting, there is an observed gap between the number of tests above which recovery is information theoretically possible, and the number of tests required by the currently best known efficient algorithms to succeed. In this paper we seek to understand whether this computational-statistical gap can be closed. Our main contributions are the following: 1.Often times such gaps are explained by a phase transition in the landscape of the solution space of the problem (an Overlap Gap Property (OGP) phase transition). We provide first moment evidence that, perhaps surprisingly, such a phase transition does not take place throughout the regime for which recovery is information theoretically possible. This fact suggests that the model is in fact amenable to local search algorithms. 2. We prove the complete absence of “bad” local minima for a part of the “hard” regime, a fact which implies an improvement over known theoretical results on the performance of efficient algorithms for approximate recovery without false-negatives. 3. Finally, motivated by the evidence for the abscence for the OGP, we present extensive simulations that strongly suggest that a very simple local algorithm known as Glauber Dynamics does indeed succeed, and can be used to efficiently implement the well-known (theoretically optimal) Smallest Satisfying Set (SSS) estimator. Given that practical algorithms for this task utilize Branch and Bound and Linear Programming relaxation techniques, our finding could potentially be of practical interest.

Maxima and minima

Statistical Inference

Source

Cite

Citations (0)