On the Complexity of Reconfiguration Problems (2009)
Takehiro Ito, Erik D. Demaine, Christos H. Papadimitriou, Martha Sideri, Ryuhei Uehara, ...
Abstract. Reconfiguration problems arise when we wish to find a stepby-step transformation between two feasible solutions of a problem such that all intermediate results are also feasible. We...
Improved Tradeoff-based Models of the Internet (2008)
Anthony Spatharis, Ilias Foudalis, Minas Gjoka, Panagiota Krouska, Christos Papadimitriou, Martha Sideri
Abstract: This paper introduces and evaluates several new models of the Internet graph, inspired by the model proposed by Fabrikant, Koutsoupias, and Papadimitriou (FKP), in which connections are...
Elias Koutsoupias, Christos H. Papadimitriou, Martha Sideri
ABSTRACT:We show that bisecting a polygon into two equal (possibly disconnected) parts with the smallest possible total perimeter is NP-complete, and it is in fact NP-hard to approximate within any...
Georg Gottlob, Francesco Scarcello, Martha Sideri
Abstract This paper studies the fixed-parameter complexity of various problems in AI and nonmonotonic reasoning. We show that a number of relevant parameterized problems in these areas are...
Linked Decompositions of Networks and the Power of Choice in Polya Urns (2007)
Henry Lin, Christos Amanatidis, Martha Sideri, Richard M. Karp, Christos H. Papadimitriou
A linked decomposition of a graph with n nodes is a set of subgraphs covering the n nodes such that all pairs of subgraphs intersect; we seek linked decompositions such that all subgraphs have about...
An Economic Model of the Worldwide Web (2005)
George Kouroupas, Elias Koutsoupias, Christos H. Papadimitriou, Martha Sideri
We believe that much novel insight into the worldwide web can be obtained from taking into account the important fact that it is created, used, and run by selfish optimizing agents: users, document...
On the Floyd-Warshall Algorithm for Logic Programs (2003)
Christos Papadimitriou, Martha Sideri
We explore the possibility of evaluating single-rule Datalog programs efficiently and with logarithmic work space by a natural extension of the Floyd-Warshall algorithm for transitive closure. We...
On the maximal models of Horn formulas (1998)
Dimitris J. Kavvadias, Dimitris J. Kavvadias, Martha Sideri, Martha Sideri, Elias C. Stavropoulos, Elias C. Stavropoulos
Abstract. We investigate the problem of generating the maximal models of Horn formulas. Based on the Resolution Theorem of Kavvadias and Stavropoulos [Computer Technology Institute, CTI TR 98.2.4,...
The inverse satisfiability problem (1998)
Dimitris Kavvadias, Martha Sideri
Abstract. We study the complexity of telling whether a set of bit-vectors represents the set of all satisfying truth assignments of a Boolean expression of a certain type. We show that the problem is...
Incremental recompilation of knowledge (1998)
Goran Gogic, Christos H. Papadimitriou, Martha Sideri
Approximating a general formula from above and below by Horn formulas (its Horn envelope and Horn core, respectively) was proposed in [22] as a form of "knowledge compilation, "...
The Inverse Satisfiability Problem (1998)
Dimitris Kavvadias, Martha Sideri
.<F3.846e+05> We study the complexity of telling whether a set of bit-vectors represents the set of all satisfying truth assignments of a Boolean expression of a certain type. We show that the...
Incremental Recompilation of Knowledge (1998)
Goran Gogic, Christos H. Papadimitriou, Martha Sideri
Approximating a general formula from above and below by Horn formulas (its Horn envelope and Horn core, respectively) was proposed by Selman and Kautz (1991, 1996) as a form of "knowledge...
On the Evolution of Easy Instances (1998)
Christos H. Papadimitriou, Martha Sideri
We present experimental evidence, based on the traveling salesman problem and the 2-opt neighborhood, that a genetic algorithm that samples the energy landscape of an optimization problem and rewards...
On Horn envelopes and hypergraph transversals (1993)
Dimitris Kavvadias, Martha Sideri
Abstract: We study the problem of bounding from above and below a given set of bit vectors by the set of satisfying truth assignments of a Horn formula. We point out a rather unexpected connection...