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...
Advisor Christos, H. Papadimitriou, Alex Fabrikant, Ankur Luthra, Elitza Maneva, Christos H. Papadimitriou
Graduate minor in systems, security, and networking Graduate minor in statistics
What is the fitness measure that decides the surviva! of ideas (and areas) in mathematics, in applted science, and in computer science? Which ideas from database theory during the past twenty-five...
Sharing the Cost of Multicast Transmissions 1 (2008)
Joan Feigenbaum, Christos H. Papadimitriou, Scott Shenker
We investigate cost-sharing algorithms for multicast transmission. Economic considerations point to two distinct mechanisms, marginal cost and Shapley value, as the two solutions most appropriate in...
Nikhil R. Devanur Market Equilibrium via a Primal-Dual Algorithm for a Convex Program (2008)
Christos H. Papadimitriou, Amin Saberi, Vijay V. Vazirani
We give the first polynomial time algorithm for exactly computing an equilibrium for the linear utilities case of the market model defined by Fisher. Our algorithm uses the primal-dual paradigm in...
Sharing the Cost of Multicast Transmissions 1 (2008)
Joan Feigenbaum, Christos H. Papadimitriou, Scott Shenker
We investigate cost-sharing algorithms for multicast transmission. Economic considerations point to two distinct mechanisms, marginal cost and Shapley value, as the two solutions most appropriate in...
Discretized Multinomial Distributions and Nash Equilibria in Anonymous Games (2008)
Daskalakis, Constantinos, Papadimitriou, Christos H.
We show that there is a polynomial-time approximation scheme for computing Nash equilibria in anonymous games with any fixed number of strategies (a very broad and important class of games),...
Richard M. Karp, Scott Shenker, Christos H. Papadimitriou
We present a simple, exact algorithm for identifying in a multiset the items with frequency more than a threshold θ. The algorithm requires two passes, linear time, and space 1/θ. The first pass is...
Abstract Multiobjective Query Optimization (2008)
The optimization of queries in distributed database systems is known to be subject to delicate trade-o s. For example, the Mariposa database system allows users to specify a desired delay-cost tradeo...
Recognizing hole-free 4-map graphs in cubic time (2008)
Zhi-zhong Chen, Michelangelo Grigni, Christos H. Papadimitriou
We present a cubic-time algorithm for the following problem: Given a simple graph, decide whether it is realized by adjacencies of countries in a map without holes, in which at most four countries...
What is the fitness measure that decides the surviva! of ideas (and areas) in mathematics, in applted science, and in computer science? Which ideas from database theory during the past twenty-five...
February 1986 LIDS-P-1478 ON STOCHASTIC SCHEDULING WITH IN-TREE PRECEDENCE CONSTRAINTS' (2008)
Christos H. Papadimitriou, John N. Tsitsiklis
We consider the problem of optimal scheduling of a set of jobs obeying in-tree precedence con-straints, when a number M of processors is available. It is assumed that the service times of different...
Nikhil R. Devanur, Christos H. Papadimitriou, Amin Saberi, Vijay V. Vazirani
We provide the first polynomial time algorithm for the linear version of a market equilibrium model defined by Irving Fisher in 1891, thereby partially answering an open question of [3]. Our...
Planar Map Graphs (Extended Abstract for 1998 STOC) (2008)
Zhi-zhong Chen, Michelangelo Grigni, Christos H. Papadimitriou
On the Approximability of Trade-offs (2008)
And Optimal Access, Christos H. Papadimitriou
CHRISTOS H. PAPADIMITRIOU Computer Science Dept.
The complexity of game dynamics: Bgp oscillations, sink equilibria, and beyond (2008)
Alex Fabrikant, Christos H. Papadimitriou
We settle the complexity of a well-known problem in networking by establishing that it is PSPACE-complete to tell whether a system of path preferences in the BGP protocol [25] can lead to oscillatory...
The complexity of game dynamics: Bgp oscillations, sink equilibria, and beyond (2008)
Alex Fabrikant, Christos H. Papadimitriou
and beyond
Zhi-zhong Chen, Christos H. Papadimitriou
We consider a modified notion of planarity, in which two nations of a map are considered adjacent when they share any point of their boundaries (not necessarily an edge, as planarity requires). Such...
Zhi-zhong Chen, Christos H. Papadimitriou
We introduce and study a modified notion of planarity, in which two regions of a map are considered adjacent when they share any point of their boundaries (not an edge, as standard planarity...
Towards a Theory of Indexability (Extended Abstract) (2007)
Joseph Hellerstein, Elias Koutsoupias, Christos H. Papadimitriou
for 1997 PODS) Joseph M. Hellerstein Division of Computer Science, U. C. Berkeley, Berkeley, CA 94720 Elias Koutsoupias Department of Computer Science, UCLA Christos H. Papadimitriou Division of...
University of California, (2007)
Christos H. Papadimitriou, Edouard Servan-schreiber
In this paper, we introduce a model of communication in hierarchies in which we emphasize the cost due to the disruption inherent in sending and receiving a message, independently of its size;...
On Approximating a Scheduling Problem (Extended Abstract for Approx98) (2007)
Pierluigi Crescenzi, Deng Xiaotie, Christos H. Papadimitriou
Given a set of communication tasks (best described in terms of a weighted bipartite graph where one set of nodes denotes the senders, the other set the receivers, edges are communication tasks, and...
On Extroverted Complexity Theory (2007)
ymous to "NP-completeness." 2 Complexity as mathematical poverty. One of the fundamental theses that seems to be almost universally accepted and practiced in computer science is that...
Richard Desper, Feng Jiang, Cancer Genetics Branch, Holger Moch, Christos H. Papadimitriou, Alejandro A. Schaffer
Comparative genome hybridization (CGH) is a laboratory method to measure gains and losses of chromosomal regions in tumor cells. It is believed that DNA gains and losses in tumor cells do not occur...
The Power of Reflective Relational Machines (Extended Abstract) (2007)
Serge Abiteboul, Christos H. Papadimitriou, Victor Vianu
) Serge Abiteboul , Christos H. Papadimitriou y and Victor Vianu z March 2, 1995 Abstract A model of database programming with reflection, called reflective relational machine is introduced and...
Victor Vianu, Christos H. Papadimitriou
This paper is my one-time attempt to organize and register these thoughts. 2 Theory and its Function
TRANSLATING UPDATES OF RELATIONAIr DATABASE VIEWS by (2007)
Stavros Stylianos Cosmadakis, Christos H. Papadimitriou
Certified by. Accepted by Department of Electrical Engineering.and Computer Science
Milena Mihail, Christos H. Papadimitriou
We show that the largest eigenvalues of graphs whose highest degrees are Zipf-like distributed with slope are distributed according to a power law with slope =2. This follows as a direct and almost...
The Serializabilit of Concurrent Database udates* (2007)
Christos H. Papadimitriou, Christos H. Papadimitriou, P. A. Bernstein, J. B. Rothnie, Christos H. Papamtriou
It will appear in the Journal of the ACM. A preliminary version of Sections 2 and 3 was presented a t the Conference for Theoret-
Christos H. Papadimitriou, Prabhakar Raghavan, Hisao Tamaki, Santosh Vempala
Latent semantic indexing (LSI) is an information retrieval technique based on the spectral analysis of the term-document matrix, whose empirical success had heretofore been without rigorous...
Christos H. Papadimitriou, Prabhakar Raghavan, Hisao Tamaki
We are given a connected, undirected graph G on n vertices. There is a mobile robot on one of the vertices; this vertex is labeled s. Each of several other vertices contains a single movable...
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...
University of California, (2007)
Christos H. Papadimitriou, Edouard Servan-schreiber
We introduce a model of communication in hierarchies in which we emphasize the cost due to the disruption inherent in sending and receiving messages, independently of their size; bandwidth...
Multiobjective Query Optimization (Extended Abstract) (2007)
Christos H. Papadimitriou, Mihalis Yannakakis
The optimization of queries in distributed database systems is known to be subject to delicate trade-offs. For example, the Mariposa database system allows users to specify a desired delay-cost...
Jon Kleinberg, Christos H. Papadimitriou, Prabhakar Raghavan
As individuals increasingly take advantage of on-line services, the value of the private information they possess emerges as a problem of fundamental concern. We believe that the principle underlying...
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...
The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies (2006)
Gopalan, Parikshit, Kolaitis, Phokion G., Maneva, Elitza, Papadimitriou, Christos H.
Boolean satisfiability problems are an important benchmark for questions about complexity, algorithms, heuristics and threshold phenomena. Recent work on heuristics, and the satisfiability threshold...
The complexity of computing a Nash equilibrium (2006)
Constantinos Daskalakis, Paul W. Goldberg, Christos H. Papadimitriou
We resolve the question of the complexity of Nash equilibrium by showing that the problem of computing a Nash equilibrium in a game with 4 or more players is complete for the complexity class PPAD....
The game world is flat: The complexity of Nash equilibria in succinct games (2006)
Constantinos Daskalakis, Alex Fabrikant, Christos H. Papadimitriou
Abstract. A recent sequence of results established that computing Nash equilibria in normal form games is a PPAD-complete problem even in the case of two players [11,6,4]. By extending these...
The game world is flat: The complexity of Nash equilibria in succinct games (2006)
Constantinos Daskalakis, Alex Fabrikant, Christos H. Papadimitriou
Abstract. A recent sequence of results established that computing Nash equilibria in normal form games is a PPAD-complete problem even in the case of two players [11, 6, 4]. By extending these...
The Complexity of Computing a Nash Equilibrium (2006)
Constantinos Daskalakis Paul, Paul W. Goldberg, Christos H. Papadimitriou
We resolve the question of the complexity of Nash equilibrium by showing that the problem of computing a Nash equilibrium in a game with 4 or more players is complete for the complexity class PPAD....
The complexity of computing a Nash equilibrium (2006)
Constantinos Daskalakis, Paul W. Goldberg, Christos H. Papadimitriou
We resolve the question of the complexity of Nash equilibrium by showing that the problem of computing a Nash equilibrium in a game with 4 or more players is complete for the complexity class PPAD....
Dipl Inf. -ing, Eth Zürich, Malters Lu, Prof Dr, Roger Wattenhofer, Prof Dr, ...
born 11.09.1979 citizen of
Parikshit Gopalan, Phokion G. Kolaitis, Christos H. Papadimitriou, Elitza Maneva
Boolean satisfiability problems are an important benchmark for questions about complexity, algorithms, heuristics and threshold phenomena. Recent work on heuristics, and the satisfiability threshold...
Data gathering tours in sensor networks (2006)
Christos H. Papadimitriou, Alexandra Meliou, Alexandra Meliou, Alexandra Meliou, Joseph M. Hellerstein, Joseph M. Hellerstein, ...
Copyright c ○ 2005 by
The Complexity of Computing a Nash Equilibrium (2006)
Constantinos Daskalakis, Paul W. Goldberg, Christos H. Papadimitriou
In 1951, John F. Nash proved that every game has a Nash equilibrium [43]. His proof is non-constructive, relying on Brouwer’s fixed point theorem, thus leaving open the questions: Is there a...
The Complexity of Computing a Nash Equilibrium (2006)
Constantinos Daskalakis, Paul W. Goldberg, Christos H. Papadimitriou
In 1951, John F. Nash proved that every game has a Nash equilibrium [43]. His proof is non-constructive, relying on Brouwer’s fixed point theorem, thus leaving open the questions: Is there a...
Three-player games are hard (2005)
Constantinos Daskalakis, Christos H. Papadimitriou
We prove that computing a Nash equilibrium in a 3-player game is PPAD-complete, solving a problem left open in (2).
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...
Three-Player Games Are Hard (2005)
Constantinos Daskalakis Christos, Christos H. Papadimitriou
We prove that computing a Nash equilibrium in a 3-player game is PPAD-complete, solving a problem left open in (2).
Approximately Dominating Representatives (2005)
Vladlen Koltun, Christos H. Papadimitriou
Abstract. We propose and investigate from the algorithmic standpoint a novel form of fuzzy query called approximately dominating representatives or ADRs. The ADRs of a multidimensional point set...
The Complexity of Games on Highly Regular Graphs (Extended Abstract) (2005)
Constantinos Daskalakis, Christos H. Papadimitriou
We present algorithms and complexity results for the problem of finding equilibria (mixed Nash equilibria, pure Nash equilibria and correlated equilibria) in games with extremely succinct description...
Computing Correlated Equilibria (2005)
Christos H. Papadimitriou, Tim Roughgarden, Nash Equilibria, Nash Equilibria
���� � ����� � correlated equilibria, �� � �� � ������� � ���� � ����������
Computing Equilibria in Multi-Player Games (2004)
Christos H. Papadimitriou, Tim Roughgarden
We initiate the systematic study of algorithmic issues involved in finding equilibria (Nash and correlated) in games with a large number of players; such games, in order to be computationally...
Selfish Caching in Distributed Systems: A Game-Theoretic Analysis (2004)
Byung-gon Chun, Kamalika Chaudhuri, Hoeteck Wee, Marco Barreno, Christos H, ...
We analyze replication of resources by server nodes that act selfishly, using a game-theoretic approach. We refer to this as the selfish caching problem. In our model, nodes incur either cost for...
Global Synchronization in Sensornets (2004)
Richard Karp Jeremy, Richard M. Karp, Jeremy Elson, Christos H. Papadimitriou, Scott Shenker
Time synchronization is necessary in many distributed systems, but achieving synchronization in sensornets, which combine stringent precision requirements with severe resource constraints, is...
The Complexity of Games on Highly Regular Graphs (2004)
Exte Nd Ed, Konstantinos Daskalakis, Christos H. Papadimitriou
Konstantinos Daskalakis # Christos H. Papadimitriou + November 18, 2004 Abstract We study from the complexity point of view the problem of finding equilibria in games defined by highly regular graphs...
Global synchronization in sensornets (2004)
Richard M. Karp, Jeremy Elson, Christos H. Papadimitriou, Scott Shenker
Time synchronization is necessary in many distributed systems, but achieving synchronization in sensornets, which combine stringent precision requirements with severe resource constraints, is...
A simple algorithm for finding frequent elements in streams and bags (2003)
Richard M. Karp, Christos H. Papadimitriou, Scott Shenker
Abstract. We present a simple, exact algorithm for iceberg queries (identifying in a multidet the items with frequency more than a threshold ) that requires two passes, linear time, and space 1=. 1.
On a network creation game (2003)
Alex Fabrikant, Ankur Luthra, Christos H. Papadimitriou
We introduce a novel game that models the creation of Internet-like networks by selfish node-agents without central design or coordination. Nodes pay for the links that they establish, and benefit...
An Optimality Theory of Concurrency Control for Databases. (2002)
Kung,Hsing-Tsung, Papadimitriou,Christos H.
A concurrency control mechanism (or a scheduler) is the component of a database system that safeguards the consistency of the database in the presence of interleaved accesses and update requests. We...
On the Complexity of Designing Distributed Protocols, (2002)
Papadimitriou,Christos H., Tsitsiklis,John
We study the complexity of two problems of distributed computation and decision-making. We show that deciding whether two distant agents can arrive at compatible decisions without any communication...
Heuristically optimized trade-offs: a new paradigm for power laws in the internet (2002)
Alex Fabrikant, Christos H. Papadimitriou
Abstract We give a plausible explanation of the power law distributions of degrees observed in the graphs arising in the Internet topology [5] based on a toy model of Internet growth in which two...
Heuristically optimized trade-offs: a new paradigm for power laws in the internet (2002)
Alex Fabrikant, Elias Koutsoupias, Christos H. Papadimitriou
Market equilibrium via a primal-dual-type algorithm (2002)
Nikhil R. Devanur, Christos H. Papadimitriou, Amin Saberi, Vijay V. Vazirani
Although the study of market equilibria has occupied center stage within Mathematical Economics for over a century, polynomial time algorithms for such questions have so far evaded researchers. We...
Heuristically optimized trade-offs: a new paradigm for power laws in the internet (2002)
Alex Fabrikant, Elias Koutsoupias, Christos H. Papadimitriou
Abstract. We propose a plausible explanation of the power law distributions of degrees observed in the graphs arising in the Internet topology [Faloutsos, Faloutsos, and Faloutsos, SIGCOMM 1999]...
Market equilibrium via a primal-dual-type algorithm (2002)
Nikhil R. Devanur, Christos H. Papadimitriou, Amin Saberi, Vijay V. Vazirani
We provide the first polynomial time algorithm for the linear version of a market equilibrium model defined by Irving Fisher in 1891, thereby partially answering an open question of [3]. Our...
Market equilibrium via a primal-dual-type algorithm (2002)
Nikhil R. Devanur, Christos H. Papadimitriou, Amin Saberi, Vijay V. Vazirani
Although the study of market equilibria has occupied center stage within Mathematical Economics for over a century, polynomial time algorithms for such questions have so far evaded researchers. We...
Market equilibrium via a primal-dual-type algorithm (2002)
Nikhil R. Devanur, Christos H. Papadimitriou, Amin Saberi, Vijay V. Vazirani
Although the study of market equilibria has occupied center stage within Mathematical Economics for over a century, polynomial time algorithms for such questions have so far evaded researchers. We...
Alex Fabrikant, Elias Koutsoupias, Christos H. Papadimitriou
We give a plausible explanation of the power law distributions of degrees observed in the graphs arising in the Internet topology [5] based on a toy model of Internet growth in which two objectives...
Inferring Tree Models for Oncogenesis from Comparative Genome Hybridization Data (2002)
Richard Desper, Feng Jiang, Olli-P. Kallioniemi, Cancer Genetics Branch, Holger Moch, Christos H. Papadimitriou, ...
Comparative genome hybridization (CGH) is a laboratory method to measure gains and losses of chromosomal regions in tumor cells. It is believed that DNA gains and losses in tumor cells do not occur...
Market equilibrium via a primal-dual-type algorithm (2002)
Nikhil R. Devanur, Christos H. Papadimitriou, Amin Saberi, Vijay V. Vazirani
We give the first polynomial time algorithm for exactly computing an equilibrium for the linear utilities case of the market model defined by Fisher. Our algorithm uses the primal-dual paradigm in...
On a Model of Indexability and its Bounds for Range Queries (2002)
Joseph M. Hellerstein, Elias Koutsoupias, Daniel P. Miranker, Christos H. Papadimitriou, VASILIS SAMOLADAS
Heuristically optimized trade-offs: a new paradigm for power laws in the internet (2002)
Alex Fabrikant, Elias Koutsoupias, Christos H. Papadimitriou
Abstract. We propose a plausible explanation of the power law distributions of degrees observed in the graphs arising in the Internet topology [Faloutsos, Faloutsos, and Faloutsos, SIGCOMM 1999]...
On a model of indexability and its bounds for range queries (2002)
Joseph M. Hellerstein, Elias Koutsoupias, Daniel P. Miranker, Christos H. Papadimitriou, Vasilis Samoladas
Abstract. We develop a theoretical framework to characterize the hardness of indexing data sets on block-access memory devices like hard disks. We define an indexing workload by a data set and a set...
Sharing the Cost of Multicast Transmissions (2001)
Joan Feigenbaum, Christos H. Papadimitriou, Scott Shenker
We investigate cost-sharing algorithms for multicast transmission. Economic considerations point to two distinct mechanisms, marginal cost and Shapley value, as the two solutions most appropriate in...
Algorithms, Games and the Internet (2001)
If the Internet is the next great subject for Theoretical Computer Science to model and illuminate mathematically, then Game Theory, and Mathematical Economics more generally, are likely to prove...
On the value of private information (2001)
Christos H. Papadimitriou, Prabhakar Raghavan
Abstract As individuals increasingly take advantage of on-line services, the value of the private information they possess emerges as a problem of fundamental concern. We believe that the principle...
Sharing the Cost of Multicast Transmissions (2001)
Joan Feigenbaum, Christos H. Papadimitriou
Abstract We investigate cost-sharing algorithms for multicast transmission. Economic considerations point to two distinct mechanisms, marginal cost and Shapley value, as the two solutions most...
Feng Jiang, Richard Desper, Christos H. Papadimitriou, Ro A. Schäffer, Olli-p. Kallioniemi, Jan Richter, ...
Renal cell carcinoma is characterized by an accumulation of complex chromosomal alterations during tumor progression. Chromosome 3p deletions are known to occur early in the carcinogenesis, but the...
On the Approximability of the Traveling Salesman Problem (2000)
Christos H. Papadimitriou, Santosh Vempala
Abstract. We show that the traveling salesman problem with triangle inequality cannot be approximated with a ratio better than 117 116 when the edge lengths are allowed to be asymmetric and 220 219...
Sharing the Cost of Multicast Transmissions (2000)
Joan Feigenbaum, Christos H. Papadimitriou, Scott Shenker
this paper, we focus on the communication burden of algorithms for implementing the MC and SH cost-sharing mechanisms. We prove a lower bound suggesting that any cost-sharing algorithm implementing...
On the approximability of trade-offs and optimal access of web sources (Extended Abstract) (2000)
Christos H. Papadimitriou, Mihalis Yannakakis
We study problems in multiobjective optimization, in which solutions to a combinatorial optimization problem are evaluated with respect to several cost criteria, and we are interested in the...
Sharing the Cost of Multicast Transmissions (2000)
Joan Feigenbaum, Christos H. Papadimitriou, Scott Shenker
this paper, we focus on the communication burden of algorithms for implementing the MC and SH cost-sharing mechanisms. We prove a lower bound suggesting that any cost-sharing algorithm implementing...
Deciding stability and mortality of piecewise affine dynamical systems. (1999)
Blondel, Vincent, Bournez, Olivier, Koiran, Pascal, Papadimitriou, Christos H., Tsitsiklis, John N.
(eng) We show that several global properties (attractivity, global asymptotic stability and mortality) of discrete time dynamical systems defined by iteration of piecewise-affine maps are...
: www.idealibrary.com on Sharing the Cost of Multicast Transmissions 1 (1999)
Joan Feigenbaum, Christos H. Papadimitriou, Scott Shenker
We investigate cost-sharing algorithms for multicast transmission. Economic considerations point to two distinct mechanisms, marginal cost and Shapley value, as the two solutions most appropriate in...
he origins of the deadline: Optimizing communication in organizations (1999)
Christos H. Papadimitriou, Edouard Servan-schreiber
In this paper, we introduce a model of communication in hierarchies which is driven by the cost of being interrupted when receiving a message, rather than the usual bandwidth constraints. We show...
The Complexity Of Optimal Queuing Network Control (1999)
Christos H. Papadimitriou, John N. Tsitsiklis
: We show that several well-known optimization problems related to the optimal control of queues are provably intractable ---independently of any unproven conjecture such as P6=NP. In particular, we...
Zhi-zhong Chen, Michelangelo Grigni, Christos H. Papadimitriou
We consider a modified notion of planarity, in which two nations of a map are considered adjacent when they share any point of their boundaries (not necessarily an edge, as planarity requires). Such...
The Complexity Of Optimal Queuing Network Control (1999)
Christos Papadimitriou And, Christos H. Papadimitriou, John N. Tsitsiklis
We show that several well-known optimization problems relatedtothe optimal control of queues are provably intractable ---independently of any unproven conjecture such as P6=NP. In particular, we show...
Tsitsiklis, “The complexity of optimal queueing network control (1999)
Christos H. Papadimitriou, John N. Tsitsiklis
Abstract [6,11] by reducing them to extensions of the multi-We consider the classical problem of optimal control (routing and sequencing) of a network of queues. We prove that this problem is...
Planar Topological Inference (Algorithms and Theory of Computing) (1998)
Chen, Zhi-Zhong, Grigni, Michelangelo, Papadimitriou, Christos H.
Latent semantic indexing: A probabilistic analysis (1998)
Christos H. Papadimitriou, Prabhakar Raghavan, Santosh Vempala X
Hisao Tamaki z Latent semantic indexing (LSI) is an information retrieval technique based on the spectral analysis of the term-document matrix, whose empirical success had heretofore been without...
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, "...
Deciding Stability and Mortality of Piecewise Affine Dynamical Systems (1998)
Vincent D. Blondel, Olivier Bournez, Pascal Koiran, Christos H. Papadimitriou, John N. Tsitsiklis
This paper studies problems such as: given a discrete time dynamical system of the form x(t + 1) = f(x(t)) where f : R
NP-completeness: A Retrospective (1998)
. For a quarter of a century now, NP-completeness has been computer science's favorite paradigm, fad, punching bag, buzzword, alibi, and intellectual export. This paper is a fragmentary...
Latent Semantic Indexing: A Probabilistic Analysis (1998)
Christos H. Papadimitriou, Prabhakar Raghavan, Hisao Tamaki, S. Vempala, Santosh Vempala
Latent semantic indexing (LSI) is an information retrieval technique based on the spectral analysis of the term-document matrix, whose empirical success had heretofore been without rigorous...
Latent Semantic Indexing: A Probabilistic Analysis (1998)
Christos Papadimitriou Computer, Christos H. Papadimitriou, Prabhakar Raghavan, Hisao Tamaki, Santosh Vempala
Latent semantic indexing (LSI) is an information retrieval technique based on the spectral analysis of the term-document matrix, whose empirical success had heretofore been without rigorous...
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...
Latent Semantic Indexing: A Probabilistic Analysis (1997)
Christos H. Papadimitriou, Prabhakar Raghavan, Hisao Tamaki, Santosh Vempala
Latent semantic indexing (LSI) is an information retrieval technique based on the spectral analysis of the term-document matrix, whose empirical success had heretofore been without rigorous...
On the Complexity of Database Queries (Extended Abstract) (1997)
Christos H. Papadimitriou, Mihalis Yannakakis
) Christos H. Papadimitriou Division of Computer Science, U. C. Berkeley, Berkeley, CA 94720 Mihalis Yannakakis Bell Laboratories, Lucent Technologies, Murray Hill NJ 07974 Abstract We revisit the...
On the Analysis of Indexing Schemes (1997)
Joseph M. Hellerstein, Elias Koutsoupias, Christos H. Papadimitriou
We consider the problem of indexing general database workloads (combinations of data sets and sets of potential queries). We define a framework for measuring the efficiency of an indexing scheme for...
NP-Completeness: A retrospective (1997)
Abstract. For a quarter of a century now, NP-completeness has been computer science's favorite paradigm, fad, punching bag, buzzword, alibi, and intellectual export. This paper is a fragmentary...
On the Difficulty of Designing Good Classifiers (1996)
Michelangelo Grigni, Vincent Mirelli, Christos H. Papadimitriou
It is a very interesting and well-studied problem, given two point sets W;B ` ! n , to design a decision tree that classifies them ---that is, no leaf subdivision contains points from both B and W...
Emerging Opportunities for Theoretical Computer Science (1996)
Alfred Aho, David S. Johnson, S. Rao Kosaraju, Catherine C. Mcgeoch, Christos H. Papadimitriou, ...
The principles underlying this report can be summarized as follows: 1. A strong theoretical foundation is vital to computer science. 2. Theory can be enriched by practice. 3. Practice can be enriched...
Database Metatheory: Asking the Big Queries (1995)
Victor Vianu, Christos H. Papadimitriou
Is ``database theory'' an oxymoron? Or is it a platitude? What is the fitness measure that decides the survival of ideas (and areas) in mathematics, in applied science, and in computer...
On bounded rationality and computational complexity (1994)
Christos H. Papadimitriou, Mihalis Yannakakis
ABSTRACT: It has been hoped that computational approaches can help resolve some wellknown paradoxes in game theory. We prove that if the repeated prisoner's dilemma is played by finite automata...
The Complexity Of Optimal Queueing Network Control (1994)
Christos H. Papadimitriou, John N. Tsitsiklis
: We show that several well-known optimization problems related to the optimal control of queues are provably intractable ---independently of any unproven conjecture such as P6=NP. In particular, we...
On the Random Walk Method for Protocol Testing (1994)
Milena Mihail, Christos H. Papadimitriou
An important method for testing large and complex protocols repeatedly generates and tests a part of the reachable state space by following a random walk; the main advantage of this method is that it...
Motion Planning on a Graph (1994)
Christos H. Papadimitriou, Prabhakar Raghavan, Madhu Sudan, Hisao Tamaki
We are given a connected, undirected graph G on n vertices. There is a mobile robot on one of the vertices; this vertex is labeled s. Each of several other vertices contains a single movable...
On the greedy algorithm for satisfiability (1992)
Elias Koutsoupias, Christos H. Papadimitriou, One Variable, Set T T
ABSTRACT: We show that for the vast majority of satisfiable 3CNF formulae, the local search heuristic that starts at a random truth assignment, and repeatedly flips the variable that improves the...
On the Predictability of Coupled Automata: An Allegory About Chaos (1991)
Sam Buss, Christos H. Papadimitriou, John Tsitsiklis
Abstract We show a sharp dichotomy between systems of identical automata with a symmetric global control whose behavior is easy to predict, and those whose behavior is hard to predict. The division...
On the Predictability of Coupled Automata: An Allegory About Chaos (1991)
Sam Buss, Christos H. Papadimitriou, John Tsitsiklis
Abstract We show a sharp dichotomy between systems of identical automata with a symmetric global control whose behavior is easy to predict, and those whose behavior is hard to predict. The division...
On the Predictability of Coupled Automata: An Allegory About Chaos (1991)
Sam Buss, Christos H. Papadimitriou, John Tsitsiklis
We show a sharp dichotomy between systems of identical automata with a symmetric global control whose behavior is easy to predict, and those whose behavior is hard to predict. The division pertains...
On The Predictability Of Coupled Automata: (1991)
An Allegory About, Sam Buss, Christos H. Papadimitriou, John Tsitsiklis
We show a sharp dichotomy between systems of identical automata with a symmetric global control whose behavior is easy to predict, and those whose behavior is hard to predict. The division pertains...
On the Predictability of Coupled Automata: An Allegory About Chaos (1991)
Sam Buss, Christos H. Papadimitriou, John Tsitsiklis
We show a sharp dichotomy between systems of identical automata with a symmetric global control whose behavior is easy to predict, and those whose behavior is hard to predict. The division pertains...
On the Predictability of Coupled Automata: An Allegory About Chaos (1991)
Samuel R. Buss, Christos H. Papadimitriou, John N. Tsitsiklis
Abstract. We show a sharp dichotomy between systems of identical automata with a symmetric global control whose behavior is easy to predict, and those whose behavior is hard to predict. The division...
On the Predictability of Coupled Automata: An Allegory About Chaos (1991)
Sam Buss, Christos H. Papadimitriou, John Tsitsiklis
We show a sharp dichotomy between systems of identical automata with a symmetric global control whose behavior is easy to predict, and those whose behavior is hard to predict. The division pertains...
On the Predictability of Coupled Automata: An Allegory About Chaos (1991)
Sam Buss, Christos H. Papadimitriou, John Tsitsiklis
We show a sharp dichotomy between systems of identical automata with a symmetric global control whose behavior is easy to predict, and those whose behavior is hard to predict. The division pertains...
North-Holland THE OPTIMUM EXECUTION ORDER OF QUERIES IN LINEAR STORAGE (1990)
John G. Kollias, Yannis Manolopoulos, Christos H. Papadimitriou
Consider a file that resides in a linear storage device with one read head. Suppose that several queries on the file must be answered simultaneously with no prespecified order. To satisfy the ith...
A Note on Total Functions, Existence Theorems, and Computational Complexity (1989)
Nimrod Megiddo, Christos H. Papadimitriou
. Nondeterministic multivalued functions with values that are polynomially verifiable and guaranteed to exist form an interesting complexity class between P and NP. We show that this class, which we...
Nimrod Megiddo, Christos H. Papadimitriou, Communicated M. Nivat
On total functions, existence theorems and computational complexity
A Note on Total Functions, Existence Theorems, and Computational Complexity (1989)
Nimrod Megiddo, Christos H. Papadimitriou
Nondeterministic multivalued functions with values that are polynomially verifiable and guaranteed to exist form an interesting complexity class between P and NP.Weshow that this class,...
The complexity of recognizing polyhedral scenes (1988)
Lefteris M. Kirousis, Christos H Papadimitriou
Given a drawing of straight lines on the plane, we wish to decide whether it is the projec-tion of the visible part of a set of opaque polyhedra. This is the fundamental algorithmic problem that...
A note on strategy elimination in bimatrix games (1988)
Donald E. Knuth, Christos H. Papadimitriou, John N. Tsitsiklis
In bunatrx games we study the process of successively eliminating strategies which are donunated by other-pure strategies. We show how to perform this simplification mn O(n 3) time, where n is the...
Christos H Papadimitriou, Mihalis Yannakakis
We define a natural variant of NP, MAX NP, and also a subclass called MAX SNP. These are classes of optimization problems, and in fact contain several natural, well-studied ones. We show that...
North-Holland ON GENERATING ALL MAXIMAL INDEPENDENT SETS (1987)
David S. Johnson, Mihalis Yannakakis, Christos H. Papadimitriou
We present an algorithm that generates all maximal independent sets of a graph in lexicographic order, with only polynomial delay between the output of two successive independent sets. We also show...
The Complexity of Facets Resolved (1985)
Papadimitriou, Christos H., Wolfe, David
ABSTRACT NOT SUPPLIED
The Complexity of Facets Resolved (1985)
Papadimitriou, Christos H., Wolfe, David
ABSTRACT NOT SUPPLIED
A simple criterion for structurally fixed modes (1984)
Christos H. Papadimitriou, John Tsitsiklis
We present a simple characterization of the maximum possible rank of the product of several real matrices, when certain entries of the matrices are constrained to be zero. Our result relates this...
North-Holland SEARCHING AND PEBBLING (1983)
Lefteris M. Kirousis, Christos H. Papadimitriou
Abstract. We relate the search number of an undirected graph G with the minimum and maximum of the progressive pebble demands of the directed acyclic graphs obtained by orienting (7. Towards this...
On the complexity of designing distributed protocols (1982)
Christos H. Papadimitriou, John Tsitsiklis
The complexity of two problems of distributed computation and decision-making is studied. It is shown that deciding whether two distant agents can arrive at compatible decisions without any...
Marco A. Casanova, Ronald Fagins, Christos H. Papadimitriou
Inclusion dependencies, or INDs (which can say, for example, that every manager is an employee) are studied, including their interaction with functional dependencies, or FDs. A simple complete...
*Paper submitted to Information and Control (1982)
Christos H. Papadimitriou, John Tsitsiklis, Onon T Nplexi, Christos H. Ipapadimitriou, John Tsitsiklis
We study the complexity of two problems of distributed computation and decision-making. We show that deciding ihether two distant agents can arrive at compatible decisions without any communication...
Flowshop scheduling with limited temporary storage (1980)
Christos H. Papadimitriou, Paris C. Kanellakis
We examine the problem of scheduling 2-machine flowshops in order to minimize makespan, using a limited amount of intermediate storage buffers. Although there are efficient algorithms for the extreme...
The Serializability of Concurrent Database Updates (1979)
ABSTRACT A sequence of interleaved user transactions in a database system may not be ser:ahzable, t e, equivalent to some sequential execution of the individual transactions Using a simple...
The complexity of combinatorial optimization problems. (1976)
Thesis (Ph. D.)--Princeton.
Zhi-zhong Chen, Michelangelo Grigni, Christos H. Papadimitriou
We introduce and study a modified notion of planarity, in which two regions of a map are considered adjacent when they share any point of their boundaries (not an edge, as standard planarity...
Congestion games with malicious players
Babaioff, Moshe, Kleinberg, Robert, Papadimitriou, Christos H.
We study the equilibria of non-atomic congestion games in which there are two types of players: rational players, who seek to minimize their own delay, and malicious players, who seek to maximize the...