Person:222484

Available identifiers

zbMath Open papadimitriou.christos-hDBLPp/CHPapadimitriouWikidataQ92639 ScholiaQ92639MaRDI QIDQ222484

List of research outcomes

Publication	Date of Publication	Type
On the difficulty of designing good classifiers	2024-01-29	Paper
Optimal information delivery	2023-03-21	Paper
https://portal.mardi4nfdi.de/entity/Q5875712	2023-02-03	Paper
Extremal combinatorics, iterated pigeonhole arguments, and generalizations of PPP	2022-09-15	Paper
https://portal.mardi4nfdi.de/entity/Q5090436	2022-07-18	Paper
Wealth Inequality and the Price of Anarchy	2022-07-18	Paper
On the complexity of dynamic mechanism design	2022-07-15	Paper
The platform design problem	2022-07-06	Paper
Bridging the Gap Between Neurons and Cognition Through Assemblies of Neurons	2022-02-25	Paper
Towards a Unified Complexity Theory of Total Functions	2021-06-15	Paper
Long Term Memory and the Densest K-Subgraph Problem	2021-06-15	Paper
Sex: the power of randomization	2019-10-17	Paper
An analytical contrast between fitness maximization and selection for mixability	2018-09-06	Paper
Locally Adaptive Optimization: Adaptive Seeding for Monotone Submodular Functions	2018-07-16	Paper
On the complexity of dynamic mechanism design	2018-07-16	Paper
NP-completeness: A retrospective	2018-07-04	Paper
Towards a unified complexity theory of total functions	2018-04-18	Paper
On Satisfiability Problems with a Linear Structure	2018-04-10	Paper
https://portal.mardi4nfdi.de/entity/Q4608043	2018-03-15	Paper
https://portal.mardi4nfdi.de/entity/Q4608067	2018-03-15	Paper
https://portal.mardi4nfdi.de/entity/Q5365081	2017-09-29	Paper
TFNP: An Update	2017-07-21	Paper
Stathis Zachos at 70!	2017-07-21	Paper
Algorithms, games, and evolution	2017-02-16	Paper
Power-Law Distributions in a Two-Sided Market and Net Neutrality	2017-02-10	Paper
On the k-server conjecture	2016-09-01	Paper
On complexity as bounded rationality (extended abstract)	2016-09-01	Paper
Zero-Sum Polymatrix Games: A Generalization of Minmax	2016-05-19	Paper
Can Almost Everybody be Almost Happy?	2016-04-15	Paper
Strategic Classification	2016-04-15	Paper
From Nash Equilibria to Chain Recurrent Sets	2016-04-15	Paper
On the Computational Complexity of Limit Cycles in Dynamical Systems	2016-04-15	Paper
Market equilibrium via a primal--dual algorithm for a convex program	2015-11-11	Paper
The Web Graph as an Equilibrium	2015-11-04	Paper
On a model of indexability and its bounds for range queries	2015-10-30	Paper
Map graphs	2015-10-30	Paper
Sparse covers for sums of indicators	2015-09-14	Paper
On a network creation game	2015-09-04	Paper
Optimal deterministic auctions with correlated priors	2015-08-12	Paper
Selfish caching in distributed systems	2015-08-03	Paper
Segmentation problems	2015-08-01	Paper
On the value of information in distributed decision-making (extended abstract)	2015-06-19	Paper
Optimal coteries	2015-06-19	Paper
Linear programming without the matrix	2015-05-07	Paper
Algorithms, games, and the internet	2015-02-27	Paper
Approximate Nash equilibria in anonymous games	2015-02-13	Paper
On oblivious PTAS's for nash equilibrium	2015-02-04	Paper
Reducibility among equilibrium problems	2014-11-25	Paper
The complexity of computing a Nash equilibrium	2014-11-25	Paper
https://portal.mardi4nfdi.de/entity/Q2921656	2014-10-13	Paper
https://portal.mardi4nfdi.de/entity/Q2921659	2014-10-13	Paper
Worst-case equilibria	2014-10-07	Paper
On the approximability of the traveling salesman problem (extended abstract)	2014-09-26	Paper
Sharing the cost of muliticast transmissions (preliminary version)	2014-09-26	Paper
The Complexity of the Homotopy Method, Equilibrium Selection, and Lemke-Howson Solutions	2014-07-30	Paper
A BGP-based mechanism for lowest-cost routing	2014-07-25	Paper
On optimal single-item auctions	2014-06-05	Paper
On Simplex Pivoting Rules and Complexity Theory	2014-06-02	Paper
https://portal.mardi4nfdi.de/entity/Q5417646	2014-05-22	Paper
https://portal.mardi4nfdi.de/entity/Q2856489	2013-10-29	Paper
A BGP-based mechanism for lowest-cost routing	2013-06-07	Paper
The New Faces of Combinatorial Optimization	2012-11-02	Paper
Efficiency-Revenue Trade-Offs in Auctions	2012-11-01	Paper
https://portal.mardi4nfdi.de/entity/Q2883227	2012-05-11	Paper
https://portal.mardi4nfdi.de/entity/Q2996825	2011-05-03	Paper
On the complexity of reconfiguration problems	2011-03-14	Paper
An impossibility theorem for price-adjustment mechanisms	2011-02-12	Paper
When the Players Are Not Expectation Maximizers	2010-10-19	Paper
On Learning Algorithms for Nash Equilibria	2010-10-19	Paper
The myth of the folk theorem	2010-09-20	Paper
Computing correlated equilibria in multi-player games	2010-08-16	Paper
The complexity of pure Nash equilibria	2010-08-15	Paper
https://portal.mardi4nfdi.de/entity/Q3579412	2010-08-06	Paper
https://portal.mardi4nfdi.de/entity/Q3579456	2010-08-06	Paper
On the complexity of equilibria	2010-08-05	Paper
The Joy of Theory	2010-08-05	Paper
Incentive-Compatible Interdomain Routing with Linear Utilities	2010-07-09	Paper
The Complexity of Computing a Nash Equilibrium	2010-03-17	Paper
The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies	2010-01-06	Paper
A Note on Strictly Competitive Games	2009-12-09	Paper
Congestion games with malicious players	2009-08-27	Paper
On a Network Generalization of the Minmax Theorem	2009-07-14	Paper
Algorithmic Game Theory: A Snapshot	2009-07-14	Paper
LATIN 2004: Theoretical Informatics	2009-05-07	Paper
A note on approximate Nash equilibria	2009-04-29	Paper
The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies	2009-03-12	Paper
The Game World Is Flat: The Complexity of Nash Equilibria in Succinct Games	2009-03-12	Paper
On the Complexity of Reconfiguration Problems	2009-01-29	Paper
https://portal.mardi4nfdi.de/entity/Q3549720	2009-01-05	Paper
Computing correlated equilibria in multi-player games	2008-12-21	Paper
Nash Equilibria: Where We Stand	2008-09-25	Paper
Interval scheduling: A survey	2008-09-12	Paper
https://portal.mardi4nfdi.de/entity/Q3524711	2008-09-12	Paper
The Search for Equilibrium Concepts	2008-05-02	Paper
Approximately dominating representatives	2007-03-12	Paper
On the approximability of the traveling salesman problem	2007-01-02	Paper
https://portal.mardi4nfdi.de/entity/Q3409969	2006-11-21	Paper
Recognizing hole-free 4-map graphs in cubic time	2006-08-11	Paper
Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques	2006-07-07	Paper
Algorithms – ESA 2005	2006-06-27	Paper
On certain connectivity properties of the internet topology	2006-04-28	Paper
On a conjecture related to geometric routing	2005-12-05	Paper
Experimental and Efficient Algorithms	2005-11-30	Paper
Database Theory - ICDT 2005	2005-09-13	Paper
Algorithmic Aspects of Wireless Sensor Networks	2005-08-25	Paper
An Approximate Truthful Mechanism for Combinatorial Auctions with Single Parameter Agents	2005-04-11	Paper
On the complexity of price equilibria	2004-11-18	Paper
https://portal.mardi4nfdi.de/entity/Q4818841	2004-09-24	Paper
https://portal.mardi4nfdi.de/entity/Q3046720	2004-08-12	Paper
https://portal.mardi4nfdi.de/entity/Q4737149	2004-08-11	Paper
https://portal.mardi4nfdi.de/entity/Q4737927	2004-08-11	Paper
https://portal.mardi4nfdi.de/entity/Q3044307	2004-08-11	Paper
https://portal.mardi4nfdi.de/entity/Q4471296	2004-07-28	Paper
https://portal.mardi4nfdi.de/entity/Q4440442	2003-12-17	Paper
https://portal.mardi4nfdi.de/entity/Q4437950	2003-12-04	Paper
On the complexity of single-rule datalog queries.	2003-08-19	Paper
Auditing Boolean attributes	2003-06-25	Paper
A deterministic \((2-2/(k+1))^{n}\) algorithm for \(k\)-SAT based on local search.	2003-01-21	Paper
https://portal.mardi4nfdi.de/entity/Q4542566	2002-09-17	Paper
https://portal.mardi4nfdi.de/entity/Q4542582	2002-09-17	Paper
https://portal.mardi4nfdi.de/entity/Q4542571	2002-08-01	Paper
https://portal.mardi4nfdi.de/entity/Q2766809	2002-07-01	Paper
https://portal.mardi4nfdi.de/entity/Q4535005	2002-06-12	Paper
Sharing the cost of multicast transmissions	2002-02-27	Paper
The Complexity of Optimal Queuing Network Control	2001-11-26	Paper
Deciding stability and mortality of piecewise affine dynamical systems	2001-08-20	Paper
https://portal.mardi4nfdi.de/entity/Q4527188	2001-04-26	Paper
On approximating a scheduling problem	2001-01-01	Paper
Latent semantic indexing: A probabilistic analysis	2000-12-19	Paper
Beyond Competitive Analysis	2000-10-18	Paper
On the Difficulty of Designing Good Classifiers	2000-10-18	Paper
https://portal.mardi4nfdi.de/entity/Q4938426	2000-09-26	Paper
Topological queries in spatial databases	2000-09-05	Paper
Decision-making by hierarchies of discordant agents	2000-07-10	Paper
https://portal.mardi4nfdi.de/entity/Q4252749	2000-04-26	Paper
On the Floyd–Warshall algorithm for logic programs	2000-01-04	Paper
Exploring an unknown graph	2000-01-03	Paper
https://portal.mardi4nfdi.de/entity/Q4703476	1999-12-15	Paper
On the complexity of database queries	1999-11-09	Paper
https://portal.mardi4nfdi.de/entity/Q4268444	1999-10-31	Paper
Reflective relational machines	1999-08-23	Paper
https://portal.mardi4nfdi.de/entity/Q4218400	1999-02-14	Paper
How to learn an unknown environment. I	1999-01-11	Paper
https://portal.mardi4nfdi.de/entity/Q4217266	1998-11-04	Paper
https://portal.mardi4nfdi.de/entity/Q4386975	1998-05-13	Paper
On the k -server conjecture	1998-01-28	Paper
A linear programming approach to reasoning about probabilities	1997-12-14	Paper
On kernels, defaults and even graphs	1997-10-26	Paper
On limited nondeterminism and the complexity of the V-C dimension	1997-03-31	Paper
Tie-breaking semantics and structural totality	1997-03-18	Paper
Reversible simulation of space-bounded computations	1997-02-28	Paper
The 2-evader problem	1997-02-27	Paper
Competitive distributed decision-making	1996-11-17	Paper
The bisection width of grid graphs	1996-03-18	Paper
Default theories that always have extensions	1996-02-26	Paper
On the complexity of the parity argument and other inefficient proofs of existence	1995-02-13	Paper
The weighted region problem	1994-11-13	Paper
Modularity of cycles and paths in graphs	1994-11-13	Paper
The Complexity of Multiterminal Cuts	1994-10-17	Paper
https://portal.mardi4nfdi.de/entity/Q3138918	1994-09-20	Paper
https://portal.mardi4nfdi.de/entity/Q4302464	1994-09-13	Paper
On the Complexity of Cooperative Solution Concepts	1994-08-21	Paper
https://portal.mardi4nfdi.de/entity/Q4298260	1994-07-26	Paper
Designing secure communication protocols from trust specifications	1994-06-16	Paper
The Traveling Salesman Problem with Distances One and Two	1993-06-29	Paper
Computing the throughput of a network with dedicated lines	1993-06-29	Paper
https://portal.mardi4nfdi.de/entity/Q4031421	1993-04-01	Paper
On the Optimal Bisection of a Polygon	1993-02-25	Paper
https://portal.mardi4nfdi.de/entity/Q4027186	1993-02-21	Paper
https://portal.mardi4nfdi.de/entity/Q4027187	1993-02-21	Paper
On the greedy algorithm for satisfiability	1993-01-16	Paper
The Complexity of the Lin–Kernighan Heuristic for the Traveling Salesman Problem	1993-01-16	Paper
The parallel complexity of simple logic programs	1993-01-01	Paper
On players with a bounded number of states	1992-08-03	Paper
Optimization, approximation, and complexity classes	1992-06-28	Paper
Why not negation by fixpoint?	1992-06-25	Paper
On path lengths modulo three	1992-06-25	Paper
On total functions, existence theorems and computational complexity	1991-01-01	Paper
Shortest paths without a map	1991-01-01	Paper
The optimum execution order of queries in linear storage	1990-01-01	Paper
On recognizing integer polyhedra	1990-01-01	Paper
Towards an Architecture-Independent Analysis of Parallel Algorithms	1990-01-01	Paper
Some computational aspects of circumscription	1990-01-01	Paper
Exponential lower bounds for finding Brouwer fixed points	1989-01-01	Paper
On the convergence of query evaluation	1989-01-01	Paper
Corrigendum to ``The complexity of cubical graphs	1989-01-01	Paper
Finding feasible paths for a two-point body	1989-01-01	Paper
The synthesis of communication protocols	1988-01-01	Paper
A note on strategy elimination in bimatrix games	1988-01-01	Paper
Probabilistic satisfiability	1988-01-01	Paper
On generating all maximal independent sets	1988-01-01	Paper
The complexity of facets resolved	1988-01-01	Paper
How easy is local search?	1988-01-01	Paper
The complexity of recognizing polyhedral scenes	1988-01-01	Paper
Complexity characterizations of attribute grammar languages	1988-01-01	Paper
The complexity of searching a graph	1988-01-01	Paper
On Stochastic Scheduling with In-Tree Precedence Constraints	1987-01-01	Paper
Optimal piecewise linear motion of an object among obstacles	1987-01-01	Paper
The Discrete Geodesic Problem	1987-01-01	Paper
The Complexity of Markov Decision Processes	1987-01-01	Paper
The 1-steiner tree problem	1987-01-01	Paper
A Communication-Time Tradeoff	1987-01-01	Paper
The Complexity of Reliable Concurrency Control	1987-01-01	Paper
A note on succinct representations of graphs	1986-01-01	Paper
Algorithmic aspects of multiversion concurrency control	1986-01-01	Paper
Searching and pebbling	1986-01-01	Paper
The complexity of the travelling repairman problem	1986-01-01	Paper
On the complexity of circulations	1986-01-01	Paper
Intractable Problems in Control Theory	1986-01-01	Paper
https://portal.mardi4nfdi.de/entity/Q3750150	1986-01-01	Paper
Interval graphs and searching	1985-01-01	Paper
Games against nature	1985-01-01	Paper
On negative cycles in mixed graphs	1985-01-01	Paper
An algorithm for shortest-path motion in three dimensions	1985-01-01	Paper
https://portal.mardi4nfdi.de/entity/Q3221403	1985-01-01	Paper
The Complexity of Distributed Concurrency Control	1985-01-01	Paper
Topological Bandwidth	1985-01-01	Paper
https://portal.mardi4nfdi.de/entity/Q3693290	1985-01-01	Paper
https://portal.mardi4nfdi.de/entity/Q3701213	1985-01-01	Paper
https://portal.mardi4nfdi.de/entity/Q3734166	1985-01-01	Paper
The complexity of cubical graphs	1985-01-01	Paper
https://portal.mardi4nfdi.de/entity/Q3769998	1985-01-01	Paper
The complexity of facets (and some facets of complexity)	1984-01-01	Paper
Is distributed locking harder?	1984-01-01	Paper
Communication complexity	1984-01-01	Paper
Inclusion dependencies and their interaction with functional dependencies	1984-01-01	Paper
A simple criterion for structurally fixed modes	1984-01-01	Paper
The Traveling Salesman Problem with Many Visits to Few Cities	1984-01-01	Paper
On Concurrency Control by Multiple Versions	1984-01-01	Paper
https://portal.mardi4nfdi.de/entity/Q3342215	1984-01-01	Paper
On two geometric problems related to the travelling salesman problem	1984-01-01	Paper
The even-path problem for graphs and digraphs	1984-01-01	Paper
https://portal.mardi4nfdi.de/entity/Q3707421	1984-01-01	Paper
https://portal.mardi4nfdi.de/entity/Q3720729	1984-01-01	Paper
Updates of Relational Views	1984-01-01	Paper
An optimality theory of concurrency control for databases	1983-01-01	Paper
https://portal.mardi4nfdi.de/entity/Q3326858	1983-01-01	Paper
https://portal.mardi4nfdi.de/entity/Q3341921	1983-01-01	Paper
Concurrency Control by Locking	1983-01-01	Paper
https://portal.mardi4nfdi.de/entity/Q4739657	1982-01-01	Paper
On Linear Characterizations of Combinatorial Optimization Problems	1982-01-01	Paper
Hamilton Paths in Grid Graphs	1982-01-01	Paper
https://portal.mardi4nfdi.de/entity/Q4743737	1982-01-01	Paper
Symmetric space-bounded computation	1982-01-01	Paper
Algebraic dependencies	1982-01-01	Paper
On the complexity of designing distributed protocols	1982-01-01	Paper
The complexity of restricted spanning tree problems	1982-01-01	Paper
A theorem in database concurrency control	1982-01-01	Paper
On minimal Eulerian graphs	1981-01-01	Paper
The complexity of testing whether a graph is a superconcentrator	1981-01-01	Paper
Worst-Case and Probabilistic Analysis of a Geometric Location Problem	1981-01-01	Paper
https://portal.mardi4nfdi.de/entity/Q3915990	1981-01-01	Paper
On the complexity of integer programming	1981-01-01	Paper
Covering Graphs by Simple Circuits	1981-01-01	Paper
A fast algorithm for testing for safety and detecting deadlocks in locked transaction systems	1981-01-01	Paper
https://portal.mardi4nfdi.de/entity/Q3886863	1980-01-01	Paper
https://portal.mardi4nfdi.de/entity/Q3886873	1980-01-01	Paper
Local Search for the Asymmetric Traveling Salesman Problem	1980-01-01	Paper
On the performance of balanced hashing functions when the keys are not equiprobable	1980-01-01	Paper
Flowshop scheduling with limited temporary storage	1980-01-01	Paper
https://portal.mardi4nfdi.de/entity/Q3960120	1980-01-01	Paper
The Complexity of Coloring Circular Arcs and Chords	1980-01-01	Paper
Bounds for sorting by prefix reversal	1979-01-01	Paper
Efficient search for rationals	1979-01-01	Paper
The serializability of concurrent database updates	1979-01-01	Paper
Scheduling Interval-Ordered Tasks	1979-01-01	Paper
Optimality of the Fast Fourier transform	1979-01-01	Paper
https://portal.mardi4nfdi.de/entity/Q4190141	1979-01-01	Paper
The complexity of the capacitated tree problem	1978-01-01	Paper
The adjacency relation on the traveling salesman polytope is NP-Complete	1978-01-01	Paper
Some Examples of Difficult Traveling Salesman Problems	1978-01-01	Paper
The complexity of the capacitated tree problem	1978-01-01	Paper
The Euclidean traveling salesman problem is NP-complete	1977-01-01	Paper
https://portal.mardi4nfdi.de/entity/Q3906402	1977-01-01	Paper
On the Complexity of Local Search for the Traveling Salesman Problem	1977-01-01	Paper
The NP-completeness of the bandwidth minimization problem	1976-01-01	Paper
On the complexity of edge traversing	1976-01-01	Paper
https://portal.mardi4nfdi.de/entity/Q4146536	1976-01-01	Paper
https://portal.mardi4nfdi.de/entity/Q4158481	1976-01-01	Paper

Research outcomes over time

Doctoral students

No records found.

Known relations from the MaRDI Knowledge Graph

Property	Value
MaRDI profile type	MaRDI person profile
instance of	human

This page was built for person: Christos H. Papadimitriou