Search

Your search keyword '"Papadimitriou, Christos"' showing total 2,198 results
Start Over Author "Papadimitriou, Christos"
2,198 results on '"Papadimitriou, Christos"'

101. Multiplicative Updates in Coordination Games and the Theory of Evolution

Author

Chastain, Erick, Livnat, Adi, Papadimitriou, Christos, and Vazirani, Umesh

Subjects
Computer Science - Computer Science and Game Theory, Quantitative Biology - Populations and Evolution, 91A99, F.2.0
Abstract

We study the population genetics of Evolution in the important special case of weak selection, in which all fitness values are assumed to be close to one another. We show that in this regime natural selection is tantamount to the multiplicative updates game dynamics in a coordination game between genes. Importantly, the utility maximized in this game, as well as the amount by which each allele is boosted, is precisely the allele's mixability, or average fitness, a quantity recently proposed in [1] as a novel concept that is crucial in understanding natural selection under sex, thus providing a rigorous demonstration of that insight. We also prove that the equilibria in two-person coordination games can have large supports, and thus genetic diversity does not suffer much at equilibrium. Establishing large supports involves answering through a novel technique the following question: what is the probability that for a random square matrix A both systems Ax = 1 and A^T y = 1 have positive solutions? Both the question and the technique may be of broader interest. [1] A. Livnat, C. Papadimitriou, J. Dushoff, and M.W. Feldman. A mixability theory for the role of sex in evolution. Proceedings of the National Academy of Sciences, 105(50):19803-19808, 2008.

Published
2012

102. Efficiency-Revenue Trade-offs in Auctions

Author

Diakonikolas, Ilias, Papadimitriou, Christos, Pierrakos, George, and Singer, Yaron

Subjects
Computer Science - Computer Science and Game Theory
Abstract

When agents with independent priors bid for a single item, Myerson's optimal auction maximizes expected revenue, whereas Vickrey's second-price auction optimizes social welfare. We address the natural question of trade-offs between the two criteria, that is, auctions that optimize, say, revenue under the constraint that the welfare is above a given level. If one allows for randomized mechanisms, it is easy to see that there are polynomial-time mechanisms that achieve any point in the trade-off (the Pareto curve) between revenue and welfare. We investigate whether one can achieve the same guarantees using deterministic mechanisms. We provide a negative answer to this question by showing that this is a (weakly) NP-hard problem. On the positive side, we provide polynomial-time deterministic mechanisms that approximate with arbitrary precision any point of the trade-off between these two fundamental objectives for the case of two bidders, even when the valuations are correlated arbitrarily. The major problem left open by our work is whether there is such an algorithm for three or more bidders with independent valuation distributions.

Published
2012

103. On Oblivious PTAS's for Nash Equilibrium

Author

Daskalakis, Constantinos and Papadimitriou, Christos H.

Subjects
Computer Science - Computer Science and Game Theory, Statistics - Computation, F.2.0
Abstract

If a game has a Nash equilibrium with probability values that are either zero or Omega(1) then this equilibrium can be found exhaustively in polynomial time. Somewhat surprisingly, we show that there is a PTAS for the games whose equilibria are guaranteed to have small-O(1/n)-values, and therefore large-Omega(n)-supports. We also point out that there is a PTAS for games with sparse payoff matrices, which are known to be PPAD-complete to solve exactly. Both algorithms are of a special kind that we call oblivious: The algorithm just samples a fixed distribution on pairs of mixed strategies, and the game is only used to determine whether the sampled strategies comprise an eps-Nash equilibrium; the answer is yes with inverse polynomial probability. These results bring about the question: Is there an oblivious PTAS for Nash equilibrium in general games? We answer this question in the negative; our lower bound comes close to the quasi-polynomial upper bound of [Lipton, Markakis, Mehta 2003]. Another recent PTAS for anonymous games is also oblivious in a weaker sense appropriate for this class of games (it samples from a fixed distribution on unordered collections of mixed strategies), but its runtime is exponential in 1/eps. We prove that any oblivious PTAS for anonymous games with two strategies and three player types must have 1/eps^c in the exponent of the running time for some c>1/3, rendering the algorithm in [Daskalakis 2008] essentially optimal within oblivious algorithms. In contrast, we devise a poly(n) (1/eps)^O(log^2(1/eps)) non-oblivious PTAS for anonymous games with 2 strategies and any bounded number of player types. Our algorithm is based on the construction of a sparse (and efficiently computable) eps-cover of the set of all possible sums of n independent indicators, under the total variation distance. The size of the cover is poly(n) (1/ eps^{O(log^2 (1/eps))}., Comment: extended version of paper of the same title that appeared in STOC 2009

Published
2011

104. Optimal Deterministic Auctions with Correlated Priors

Author

Papadimitriou, Christos and Pierrakos, George

Subjects
Computer Science - Computer Science and Game Theory
Abstract

We revisit the problem of designing the profit-maximizing single-item auction, solved by Myerson in his seminal paper for the case in which bidder valuations are independently distributed. We focus on general joint distributions, seeking the optimal deterministic incentive compatible auction. We give a geometric characterization of the optimal auction, resulting in a duality theorem and an efficient algorithm for finding the optimal deterministic auction in the two-bidder case and an NP-completeness result for three or more bidders.

Published
2010

105. The Complexity of the Homotopy Method, Equilibrium Selection, and Lemke-Howson Solutions

Author

Goldberg, Paul W., Papadimitriou, Christos H., and Savani, Rahul

Subjects
Computer Science - Computer Science and Game Theory, Computer Science - Computational Complexity
Abstract

We show that the widely used homotopy method for solving fixpoint problems, as well as the Harsanyi-Selten equilibrium selection process for games, are PSPACE-complete to implement. Extending our result for the Harsanyi-Selten process, we show that several other homotopy-based algorithms for finding equilibria of games are also PSPACE-complete to implement. A further application of our techniques yields the result that it is PSPACE-complete to compute any of the equilibria that could be found via the classical Lemke-Howson algorithm, a complexity-theoretic strengthening of the result in [Savani and von Stengel]. These results show that our techniques can be widely applied and suggest that the PSPACE-completeness of implementing homotopy methods is a general principle., Comment: 23 pages, 1 figure; to appear in FOCS 2011 conference

Published
2010

106. VC v. VCG: Inapproximability of Combinatorial Auctions via Generalizations of the VC Dimension

Author

Mossel, Elchanan, Papadimitriou, Christos, Schapira, Michael, and Singer, Yaron

Subjects
Computer Science - Computer Science and Game Theory, Computer Science - Discrete Mathematics
Abstract

The existence of incentive-compatible computationally-efficient protocols for combinatorial auctions with decent approximation ratios is the paradigmatic problem in computational mechanism design. It is believed that in many cases good approximations for combinatorial auctions may be unattainable due to an inherent clash between truthfulness and computational efficiency. However, to date, researchers lack the machinery to prove such results. In this paper, we present a new approach that we believe holds great promise for making progress on this important problem. We take the first steps towards the development of new technologies for lower bounding the VC dimension of k-tuples of disjoint sets. We apply this machinery to prove the first computational-complexity inapproximability results for incentive-compatible mechanisms for combinatorial auctions. These results hold for the important class of VCG-based mechanisms, and are based on the complexity assumption that NP has no polynomial-size circuits.

Published
2009

107. TP008/#1500 Trial in progress: phase 2/3 study of navtemadlin as maintenance therapy in patients with advanced or recurrent endometrial cancer who responded to chemotherapy (ENGOT-EN21; GOG-3089)

Author

Concin, Nicole, primary, Giorgi, Ugo De, additional, Gorp, Toon Van, additional, Alexandre, Jérôme, additional, Lindemann, Kristina, additional, Marth, Christian, additional, Berger, Regina, additional, Cibula, David, additional, Quindos, Maria, additional, Bologna, Alessandra, additional, Korach, Jacob, additional, Papadimitriou, Christos, additional, Nicum, Shibani, additional, Collins, Dearbhaile, additional, Myers, Reg, additional, Rothbaum, Wayne, additional, Herzog, Thomas, additional, Monk, Bradley, additional, and Cloven, Noelle Gillette, additional

Published
2023
Full Text
View/download PDF

109. RediScore: Prospective validation of a pipeline for homologous recombination deficiency analysis

Author

Tsantikidi, Aikaterini, primary, Papazisis, Konstantinos, additional, Floros, Theofanis, additional, Gazouli, Maria, additional, Papadopoulou, Eirini, additional, Tsaousis, Georgios, additional, Nasioulas, Georgios, additional, Mester, Andra, additional, Milan, Kubelac, additional, Gozman, Bogdan, additional, Afrasanie, Vlad, additional, Stanculeanu, Dana, additional, Trifanescu, Oana, additional, Pescaru, Florentina, additional, Militaru, Claudia, additional, and Papadimitriou, Christos, additional

Published
2023
Full Text
View/download PDF

110. The Utility of NGS Analysis in Homologous Recombination Deficiency Tracking

Author

Tsantikidi, Aikaterini, primary, Papadopoulou, Eirini, additional, Metaxa-Mariatou, Vasiliki, additional, Kapetsis, George, additional, Tsaousis, Georgios, additional, Meintani, Angeliki, additional, Florou-Chatzigiannidou, Chrysiida, additional, Gazouli, Maria, additional, Papadimitriou, Christos, additional, Timotheadou, Eleni, additional, Kotsakis, Athanasios, additional, Boutis, Anastasios, additional, Boukovinas, Ioannis, additional, Kampletsas, Eleftherios, additional, Kontovinis, Loukas, additional, Fountzilas, Elena, additional, Andreadis, Charalampos, additional, Karanikiotis, Charisios, additional, Filippou, Dimitrios, additional, Theodoropoulos, Georgios, additional, Özdoğan, Mustafa, additional, and Nasioulas, George, additional

Published
2023
Full Text
View/download PDF

111. #84 Trial in progress: a phase 2/3 study of navtemadlin as maintenance therapy in patients with advanced or recurrent endometrial cancer (EC) who responded to chemotherapy (ENGOT-En21 and GOG-3089)

Author

Concin, Nicole, primary, Giorgi, Ugo De, additional, Gorp, Toon Van, additional, Alexandre, Jérôme, additional, Lindemann, Kristina, additional, Marth, Christian, additional, Berger, Regina, additional, Cibula, David, additional, Quindós, María, additional, Bologna, Alessandra, additional, Korach, Jacob, additional, Papadimitriou, Christos, additional, Nicum, Shibani, additional, Collins, Dearbhaile, additional, Myers, Reg, additional, Rothbaum, Wayne, additional, Herzog, Thomas J, additional, Monk, Bradley J, additional, and Cloven, Noelle Gillette, additional

Published
2023
Full Text
View/download PDF

112. Discretized Multinomial Distributions and Nash Equilibria in Anonymous Games

Author

Daskalakis, Constantinos and Papadimitriou, Christos H.

Subjects
Computer Science - Computer Science and Game Theory, F.2.0
Abstract

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), extending the two-strategy result of Daskalakis and Papadimitriou 2007. The approximation guarantee follows from a probabilistic result of more general interest: The distribution of the sum of n independent unit vectors with values ranging over {e1, e2, ...,ek}, where ei is the unit vector along dimension i of the k-dimensional Euclidean space, can be approximated by the distribution of the sum of another set of independent unit vectors whose probabilities of obtaining each value are multiples of 1/z for some integer z, and so that the variational distance of the two distributions is at most eps, where eps is bounded by an inverse polynomial in z and a function of k, but with no dependence on n. Our probabilistic result specifies the construction of a surprisingly sparse eps-cover -- under the total variation distance -- of the set of distributions of sums of independent unit vectors, which is of interest on its own right., Comment: In the 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008

Published
2008
Full Text
View/download PDF

113. Computing Equilibria in Anonymous Games

Author

Daskalakis, Constantinos and Papadimitriou, Christos

Subjects
Computer Science - Computer Science and Game Theory, Computer Science - Computational Complexity, Computer Science - Discrete Mathematics
Abstract

We present efficient approximation algorithms for finding Nash equilibria in anonymous games, that is, games in which the players utilities, though different, do not differentiate between other players. Our results pertain to such games with many players but few strategies. We show that any such game has an approximate pure Nash equilibrium, computable in polynomial time, with approximation O(s^2 L), where s is the number of strategies and L is the Lipschitz constant of the utilities. Finally, we show that there is a PTAS for finding an epsilon

Published
2007

114. The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies

Author

Gopalan, Parikshit, Kolaitis, Phokion G., Maneva, Elitza, and Papadimitriou, Christos H.

Subjects
Computer Science - Computational Complexity
Abstract

Boolean satisfiability problems are an important benchmark for questions about complexity, algorithms, heuristics and threshold phenomena. Recent work on heuristics, and the satisfiability threshold has centered around the structure and connectivity of the solution space. Motivated by this work, we study structural and connectivity-related properties of the space of solutions of Boolean satisfiability problems and establish various dichotomies in Schaefer's framework. On the structural side, we obtain dichotomies for the kinds of subgraphs of the hypercube that can be induced by the solutions of Boolean formulas, as well as for the diameter of the connected components of the solution space. On the computational side, we establish dichotomy theorems for the complexity of the connectivity and st-connectivity questions for the graph of solutions of Boolean formulas. Our results assert that the intractable side of the computational dichotomies is PSPACE-complete, while the tractable side - which includes but is not limited to all problems with polynomial time algorithms for satisfiability - is in P for the st-connectivity question, and in coNP for the connectivity question. The diameter of components can be exponential for the PSPACE-complete cases, whereas in all other cases it is linear; thus, small diameter and tractability of the connectivity problems are remarkably aligned. The crux of our results is an expressibility theorem showing that in the tractable cases, the subgraphs induced by the solution space possess certain good structural properties, whereas in the intractable cases, the subgraphs can be arbitrary.

Published
2006

115. Stathis Zachos at 70!

Author

Bakali, Eleni, Cheilaris, Panagiotis, Fotakis, Dimitris, Fürer, Martin, Koutras, Costas D., Markou, Euripides, Nomikos, Christos, Pagourtzis, Aris, Papadimitriou, Christos H., Papaspyrou, Nikolaos S., Potika, Katerina, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Fotakis, Dimitris, editor, Pagourtzis, Aris, editor, and Paschos, Vangelis Th., editor

Published
2017
Full Text
View/download PDF

116. TFNP: An Update

Author

Goldberg, Paul W., Papadimitriou, Christos H., Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Fotakis, Dimitris, editor, Pagourtzis, Aris, editor, and Paschos, Vangelis Th., editor

Published
2017
Full Text
View/download PDF

117. Correlation of MYC Gene and Protein Status With Breast Cancer Subtypes and Outcome of Patients Treated With Anthracycline-Based Adjuvant Chemotherapy. Pooled Analysis of 2 Hellenic Cooperative Group Phase III Trials

Author

Batistatou, Anna, Kotoula, Vassiliki, Bobos, Mattheos, Kouvatseas, George, Zagouri, Flora, Tsolaki, Eleftheria, Gogas, Helen, Koutras, Angelos, Pentheroudakis, George, Timotheadou, Eleni, Pervana, Stavroula, Goussia, Anna, Petraki, Kalliopi, Sotiropoulou, Maria, Koletsa, Triantafyllia, Razis, Evangelia, Kosmidis, Paris, Aravantinos, Gerasimos, Papadimitriou, Christos, Pectasides, Dimitrios, and Fountzilas, George

Published
2018
Full Text
View/download PDF

121. Map Graphs

Author

Chen, Zhi-Zhong, Grigni, Michelangelo, and Papadimitriou, Christos

Subjects
Computer Science - Discrete Mathematics, Computer Science - Data Structures and Algorithms, G.2.2, F.2.2
Abstract

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 adjacencies define a map graph. We give an NP characterization for such graphs, and a cubic time recognition algorithm for a restricted version: given a graph, decide whether it is realized by adjacencies in a map without holes, in which at most four nations meet at any point., Comment: 46 pages, LaTeX with 41 PS figures; see http://www.mathcs.emory.edu/~mic/mapgraphs/ for hi-res figures

Published
1999

122. Neuroscience Needs Network Science

Author

Barabási, Dániel L., primary, Bianconi, Ginestra, additional, Bullmore, Ed, additional, Burgess, Mark, additional, Chung, SueYeon, additional, Eliassi-Rad, Tina, additional, George, Dileep, additional, Kovács, István A., additional, Makse, Hernán, additional, Nichols, Thomas E., additional, Papadimitriou, Christos, additional, Sporns, Olaf, additional, Stachenfeld, Kim, additional, Toroczkai, Zoltán, additional, Towlson, Emma K., additional, Zador, Anthony M., additional, Zeng, Hongkui, additional, Barabási, Albert-László, additional, Bernard, Amy, additional, and Buzsáki, György, additional

Published
2023
Full Text
View/download PDF

124. Safety and tolerability of subcutaneous trastuzumab for the adjuvant treatment of human epidermal growth factor receptor 2-positive early breast cancer: SafeHer phase III study's primary analysis of 2573 patients

Author

Koroveshi, Dhurata, Bouzid, Kamel, Casalnuovo, Monica, Cascallar, Diana, Korbenfeld, Ernesto Pablo, Bastick, Patricia, Beith, Jane, Colosimo, Maree, Friedlander, Michael, Ganju, Vinod, Green, Michael, Patterson, Kevin, Redfern, Andrew, Richardson, Gary, Ceric, Timur, Gordana, Kecman, Beato, Carlos Augusto, Ferrari, Marcela, Hegg, Roberto, Helena, Vanessa, Ismael, Gustavo Fernando, Lessa, Alvaro Edson, Mano, Max, Morelle, Alessandra, Nogueira, Jose Alberto, Timcheva, Konstanta, Tomova, Antoaneta, Tsakova, Maya, Zlatareva-Petrova, Ani, Asselah, Jamil, Assi, Hazem, Brezden-Masley, Christine, Chia, Stephen, Freedman, Ori, Harb, Mohammed, Joy, Anil Abraham, Kulkarni, Swati, Prady, Catherine, Gaete, Alejandro Andres Acevedo, Matamala, Luis, Torres, Roberto, Yanez, Eduardo, Franco, Sandra, Urrego, Marcela, Gugić, Damir, Vrbanec, Damir, Melichar, Bohuslav, Prausová, Jana, Vyzula, Rostislav, Pilarte, Rafael Gutierrez, León, María Isabel, Muñoz, Rene, Ramos, Glenda, Azeem, Hamdy Abdel, Aziz, Amr Abdel, El Zawahry, Heba, Osegueda, Finlander Rosales, Alexandre, Jerome, Artignan, Xavier, Barletta, Hugues, Beguier, Emmanuel, Berdah, Jean-François, Marty, Chantal Bernard, Bollet, Marc, Bourgeois, Hugues, Bressac, Claude, Burki, Franck, Campone, Mario, Coeffic, David, Cojocarasu, Oana Zveltlana, Dagada, Corinne, Dalenc, Florence, Del Piano, Francesco, Desauw, Christophe, Desmoulins, Isabelle, Dohollou, Nadine, Egreteau, Joelle, Ferrero, Jean-Marc, Foa, Cyril, Garidi, Reda, Gasnault, Laurent, Gligorov, Joseph, Guardiola, Emmanuel, Hamizi, Salima, Jarcau, Rosana, Jacquin, Jean-Philippe, Jaubert, Dominique, Jolimoy, Geneviève, Mineur, Hortense Laharie, Largillier, Remy, Leduc, Bernard, Martin, Philippe, Melis, Adrien, Monge, Jeremy, Moullet, Isabelle, Mousseau, Mireille, Nguyen, Suzanne, Orfeuvre, Hubert, Petit, Thierry, Pivot, Xavier, Priou, Frank, Bach, Isabelle Sillet, Simon, Helene, Stefani, Laetitia, Uwer, Lionel, Youssef, Ali, Aktas, Bahriye, von der Assen, Albert, Augustin, Doris, Balser, Christina, Bauer, Lelia-Eveline, Bechtner, Christina, Beyer, Greta, Brucker, Cosima, Bückner, Ute, Busch, Steffi, Christensen, Bernd, Deryal, Mustafa, Farrokh, Andre, Faust, Elke, Friedrichs, Kay, Graf, Heiko, Griesshammer, Martin, Grischke, Eva-Maria, Hänle, Claudia, Heider, Andrea, Henschen, Stephan, Hesse, Tobias, Jackisch, Christian, Kisro, Jens, Köhler, Andreas, Kuemmel, Sherko, Lampe, Dieter, Lantzsch, Tilmann, Latos, Kunibert, Lex, Benno, Liedtke, Cornelia, Luedders, Doerte, Maintz, Christoph, Müller, Volkmar, Overkamp, Friedrich, Park-Simon, Tjoung-won, Paul, Marion, Prechtl, Anita, Ringsdorf, Uta, Runnebaum, Ingo, Ruth, Sylvia, Salat, Christoph, Scheffen, Iris, Schilling, Jörg, Schmatloch, Sabine, Schmidt, Marcus, Schneeweiss, Andreas, Schrader, Iris, Seipelt, Gernot, Simon, Elke, Stefek, Andrea, Stickeler, Elmar, Thill, Marc, Tio, Joke, Tuczek, Anna, Warm, Mathias, Weigel, Michael, Wischnik, Arthur, Wojcinski, Sebastian, Ziegler-Löhr, Katja, Aravantinos, Gerasimos, Ardavanis, Alexandros, Fountzilas, George, Gogas, Helen, Kakolyris, Stylianos, Mavroudis, Dimitris, Papadimitriou, Christos, Papandreou, Christos, Papazisis, Konstantinos, Castro, Hugo, Hernandez-Monroy, Cesar Estuardo, Ngan, Roger, Yeo, Winnie, Bittner, Nora, Boer, Katalin, Csejtei, Andras, Horvath, Zsolt, Kocsis, Judit, Mangel, László Csaba, Mezei, Klara, Nagy, Zsuzsanna, Szanto, Janos, Atmakusuma, Djumhana, Fadjari, Heri, Kurnianda, Djohan, Prayogo, Nugroho, Tanggo, Eddie Herman, Coate, Linda, Hennessy, Bryan, Kelly, Cathy, Martin, Michael, Nasim, Saira, O'Connor, Miriam, Aieta, Michele, Allegrini, Giacomo, Amadori, Dino, Bidoli, Paolo, Biti, Giampaolo, Bordonaro, Roberto, Bottini, Alberto, Carterni, Giacomo, Cavanna, Luigi, Cazzaniga, Marina, Cognetti, Francesco, Contu, Antonio, Cruciani, Giorgio, Donadio, Michela, Falcone, Alfredo, Farci, Daniele, Forcignanò, R. Chiara, Frassoldati, Antonio, Gaion, Fernando, Gamucci, Teresa, Giotta, Francesco, de Laurentiis, Michele, Livi, Lorenzo, Lorusso, Vito, Maiello, Evaristo, Marchetti, Paolo, Mariani, Gabriella, Mion, Marta, Moscetti, Luca, Musolino, Antonino, Pazzola, Antonio, Pedrazzoli, Paolo, Pigi, Andrea, de Placido, Sabino, Caremoli, Elena Rota, Santoro, Armando, Tienghi, Amelia, Ahn, Jin-Seok, Jung, Kyung Hae, Lee, Keun Seok, Lee, Soo Hyeon, Seo, Jae Hong, Sohn, Joo-Hyuk, Cesas, Alvydas, Juozaityte, Elona, Cheah, Nellie Lay Chin, Chong, Flora Li Tze, Devi, Beena C.R., Phua, Vincent, Teoh, Darren, Ching, Lee Wei, Yusof, Mastura, Corona, Jorge, Dominguez, Adriana, Mendoza, René Lazaro González, Hernandez, Carlos Alberto, Ramiro, Alejandro Juarez, Santos, Juan Matos, Espinosa, Paola Morales, Villarreal Garza, Cynthia Mayte, Errihani, Hassan, Bakker, Sandra, van den Berkmortel, Franchette, Blaisse, R.J.B., Huinink, Daan ten Bokkel, van den Bosch, J., Braun, J.J., Dercksen, M.W., Droogendijk, Helga, Erdkamp, Frans, Haringhuizen, Annebeth, de Jongh, F.E., Kok, T.C., Los, Maartje, Madretsma, Stanley, Terwogt, Jetske M. Meerum, van der Padt, Annemieke, van Rossum-Schornagel, Quirine Clementine, Smilde, T.J., de Valk, Bart, van der Velden, Annette, van Warmerdam, Laurence, van de Wouw, A.J., North, Richard, Kersten, Christian, Mjaaland, Ingvild, Wist, Erik, Aziz, Zeba, Masood, Nehal, Rashid, Kamran, Shah, Mazhar, Alcedo, Juan Carlos, Aleman, Diana, Neciosup, Silvia, Reategui, Rocio, Valdiviezo, Natalia, Vera, Luis, Fernando, Gracieux, Roque, Fernando, Strebel, Heinrik Martin, Krzemieniecki, Krzysztof, Litwiniuk, Maria, Mruk, Andrzej, Pienkowski, Tadeusz, Sawrycki, Piotr, Slomian, Grzegorz, Tomczak, Piotr, Afonso, Noemia, Cardoso, Fátima, Damasceno, Margarida, Nave, Monica, Badulescu, Florinel, Ciule, Larisa, Curescu, Stefan, Eniu, Alexandru, Filip, Dumitru, Grecea, Daniela, Jinga, Dan-Corneliu, Lungulescu, Dan, Oprean, Cristina Marinela, Stanculeanu, Dana Lucia, Turdean, Maria, Dvornichenko, Viktoria, Emelyanov, Sergey, Lichinitser, Mikhail, Manikhas, Alexey, Sakaeva, Dina, Shirinkin, Vadim, Stroyakovskiy, Daniil, Abulkhair, Omalkhair, Zekri, Jamal, Filipovic, Sladjana, Kovcin, Vladimir, Nedovic, Jasmina, Pesic, Jasna, Vasovic, Suzana, Ng, Raymond, Bystricky, Branislav, Leskova, Jaroslava, Mardiak, Jozef, Mišurová, Etela, Wagnerova, Maria, Takač, Iztok, Demetriou, Georgia Savva, Dreosti, Lydia, Govender, Poovandren, Jordaan, Johannes Petrus, Veersamy, Petrosian, Romero, Jose Luis Alonso, Lopez, Norberto Batista, Arias, Carmen Cañabate, Chacon, Jose, Aramburo, Antonio Fernandez, Morales, Luis Antonio Fernandez, Garcia, Mirta, Estevez, Laura Garcia, Garcia-Palomo Perez, Andres, Garcia Saenz, Jose Angel, Garcia Sanchis, Laura, Cubells, Laia Garrigos, Cortijo, Lucia Gonzalez, Santiago, Santiago Gonzalez, De Aranguiz, Blanca Hernando Fernandez, Mañas, José Juan Illarramendi, Gallego, Pedro Jimenez, Cussac, Antonio Llombart, Ferrandiz, Cristina Llorca, Garrido, Maria Lomas, Alvarez, Pilar Lopez, Vega, Jose Manuel Lopez, Del Prado, Purificacion Martinez, Jañez, Noelia Martinez, Murillo, Serafin Morales, Rosales, Adolfo Murias, Jaso, Laura Murillo, Fernandez, Ignacio Pelaez, Martorell, Antonia Perello, Carrion, Ramon Perez, Simon, Sonia Pernas, Alcibar, Arrate Plazaola, Lorenzo, Jose Ponce, Garcia, Vanesa Quiroga, Asensio, Teresa Ramon y Cajal, Maicas, Maria Dolores Torregrosa, Villanueva Silva, Maria Jose, Killander, Fredrika, Svensson, Jan Henry, Fehr, Mathias, Hauser, Nik, Müller, Andreas, Pagani, Olivia, Passmann-Kegel, Heike, Popescu, Razvan, Rabaglio, Manuela, Rauch, Daniel, Schlatter, Christina, Zaman, Khalil, Chang, Tsai-Wang, Huang, Chiun-Sheng, Wang, Hwei-Chung, Yu, Jyh-Cherng, Bandidwattanawong, Chanyoot, Maneechavakajorn, Jedzada, Seetalarom, Kasan, Dejthevaporn, Thitiya (Sirisinha), Somwangprasert, Areewan, Vongsaisuwon, Mawin, Akbulut, Hakan, Altundag, Kadri, Arican, Ali, Bozcuk, Hakan, Eralp, Yesim, Idris, Mohamed, Isikdogan, Abdurrahman, Senol, Coskun Hasan, Sevinc, Alper, Uygun, Kazim, Yucel, Eftal, Yucel, Idris, Yumuk, Fulden, Shparyk, Yaroslav, Voitko, Nataliia, Jaloudi, Mohammed, Adams, Jocelyn, Agrawal, Rajiv, Ahmed, Samreen, Alhasso, Abdulla, Allerton, Rozenn, Anwar, Suhail, Archer, Caroline, Ashford, Richard, Barraclough, Lisa, Bertelli, Gianfilippo, Bishop, Jill, Branson, Tony, Butt, Mohammed, Chakrabarti, Amit, Chakraborti, Prabir, Churn, Mark, Crowley, Clare, Davis, Ruth, Dhadda, Amandeep, Eldeeb, Hany, Fraser, Judith, Hall, Julia, Hickish, Tamas, Hogg, Martin, Howe, Theresa, Joffe, Jonathan, Kelleher, Muireann, Kelly, Stephen, Kendall, Anne, Kristeleit, Hartmut, Lumsden, Graeme, Macmillan, Craig, MacPherson, Iain, Malik, Zafar, Mithal, Natasha, Neal, Anthony, Panwar, Udaiveer, Proctor, Andrew, Proctor, Steven John, Raj, Sanjay, Rehman, Shazza, Sandri, Ines, Scatchard, Kate, Sherwin, Elizabeth, Sims, Eliot, Singer, Julian, Smith, Sarah, Tahir, Saad, Taylor, Wendy, Tsalic, Medy, Verrill, Mark, Wardley, Andrew, Waters, Simon, Wheatley, Duncan, Wright, Kathryn, Yuille, Frances, Alonso, Isabel, Artagaveytia, Nora, Rodriguez, Robinson, Arbona, Esther, Garcia, Yuraima, Lion, Lorena, Marcano, Dalila, Van Thuan, Tran, Gligorov, J., Ataseven, B., Verrill, M., De Laurentiis, M., Jung, K.H., Azim, H.A., Al-Sakaff, N., Lauer, S., Shing, M., and Pivot, X.

Published
2017
Full Text
View/download PDF

126. Computation with Sequences in the Brain

Author

Dabagia, Max, Papadimitriou, Christos H., and Vempala, Santosh S.

Subjects
FOS: Computer and information sciences, Computer Science - Machine Learning, Artificial Intelligence (cs.AI), Computer Science - Artificial Intelligence, FOS: Biological sciences, Quantitative Biology - Neurons and Cognition, Computer Science - Neural and Evolutionary Computing, Neurons and Cognition (q-bio.NC), Neural and Evolutionary Computing (cs.NE), Machine Learning (cs.LG)
Abstract

Even as machine learning exceeds human-level performance on many applications, the generality, robustness, and rapidity of the brain's learning capabilities remain unmatched. How cognition arises from neural activity is a central open question in neuroscience, inextricable from the study of intelligence itself. A simple formal model of neural activity was proposed in Papadimitriou [2020] and has been subsequently shown, through both mathematical proofs and simulations, to be capable of implementing certain simple cognitive operations via the creation and manipulation of assemblies of neurons. However, many intelligent behaviors rely on the ability to recognize, store, and manipulate temporal sequences of stimuli (planning, language, navigation, to list a few). Here we show that, in the same model, time can be captured naturally as precedence through synaptic weights and plasticity, and, as a result, a range of computations on sequences of assemblies can be carried out. In particular, repeated presentation of a sequence of stimuli leads to the memorization of the sequence through corresponding neural assemblies: upon future presentation of any stimulus in the sequence, the corresponding assembly and its subsequent ones will be activated, one after the other, until the end of the sequence. Finally, we show that any finite state machine can be learned in a similar way, through the presentation of appropriate patterns of sequences. Through an extension of this mechanism, the model can be shown to be capable of universal computation. We support our analysis with a number of experiments to probe the limits of learning in this model in key ways. Taken together, these results provide a concrete hypothesis for the basis of the brain's remarkable abilities to compute and learn, with sequences playing a vital role., 24 pages, 12 figures

Published
2023

128. The Web Graph as an Equilibrium

Author

Kouroupas, Georgios, Markakis, Evangelos, Papadimitriou, Christos, Rigas, Vasileios, Sideri, Martha, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, and Hoefer, Martin, editor

Published
2015
Full Text
View/download PDF

131. Serializability of Concurrent Data Base Updates

Author

Papadimitriou, Christos H. and Papadimitriou, Christos H.

Abstract

A sequence of interleaved user transactions in a data base system may not be serializable, i.e., equivalent to some sequential execution of the individual transactions. Using a simple transaction model we show that recognizing the transaction histories which are serializable is an NP-complete problem.

Published
2023

132. On the Complexity of Integer Programming

Author

Papadimitriou, Christos H. and Papadimitriou, Christos H.

Abstract

We give a simple proof that integer programming is in NP. Our proof also establishes that there is a pseudopolynomial time algorithm for integer programming with any (fixed) number of constraints.

Published
2023

133. Two Remarks on the Power of Counting

Author

Papadimitriou, Christos H., Zachos, Stathis K., Papadimitriou, Christos H., and Zachos, Stathis K.

Abstract

The relationship between the polynomial hierarchy and Valiant's class #P is at present unknown. We show that some low portions of the polynomial hierarchy, namely deterministic polynomial algorithms using an NP oracle at most a logarithmic number of times, can be simulated by one #P computation. We also show that the class of problems solvable by polynomial-time nondeterministic Turing machines which accept whenever there is an odd number of accepting computations is idempotent, that is closed under usage of oracles from the same class.

Published
2023

135. The Complexity of Concurrency Control for Distributed Databases

Author

Papadimitriou, Christos H., Kanellakis, Paris C., Papadimitriou, Christos H., and Kanellakis, Paris C.

Abstract

This study is an analysis of the distributed version of data base concurrency control. It provides concrete mathematical evidence that the distributed problem is an inherently more complex task than the centralized one. The notions of transaction, concurrency, history, serializability, scheduler, etc, for centralized databases are now well-understood both from a theoretical and a practical point of view.

Published
2023

136. Covering Graphs by Simple Circuits

Author

Atai, Alon, Lipton, Richard J., Papadimitriou, Christos H., Rodeh, M., Atai, Alon, Lipton, Richard J., Papadimitriou, Christos H., and Rodeh, M.

Published
2023

137. On Linear Characterizations of Combinatorial Optimization Problems

Author

Karp, Richard M. Papadimitriou, Christos H. and Karp, Richard M. Papadimitriou, Christos H.

Abstract

We show that there can be no computationally tractable description by linear inequalities of the polyhedron associated with any NP-complete combinatorial optimization problem unless NP=co-NP -- a very unlikely event. We also use the recent result by Khacian to present even stronger evidence that NP-complete combinatorial optimization problems cannot have efficient generators of violated inequalities.

Published
2023

138. Translating Updates of Relational Database Views

Author

Papadimitriou, Christos H., Cosmadakis, Stavros Stylianos, Papadimitriou, Christos H., and Cosmadakis, Stavros Stylianos

Abstract

We study the problem of translating updates of data base views. We disambiguate a view update by requiring that a specified view compliment (i.e. a second view which contains all the data base information omitted from the given view) remains constant during the translation. We study some of the computational problems related to the application of this general methodology in the context of relational databases.

Published
2023

139. The Traveling Saleman Problem with Many Visits to Few Cities

Author

Cosmadakis, Stavros S., Papadimitriou, Christos H., Cosmadakis, Stavros S., and Papadimitriou, Christos H.

Abstract

We study the version of the traveling salesman problem in which a relatively small number of cities -- say, six -- must be visited a huge number of times -- e.g., several hundred times each. )It costs to go from one city to itself). We develop an algorithm for this problem whose running time is exponential in the number of cities, but logarithmic in the number of visits. Our algorithm is a practical approach to the problem for instances of size in the range indicated above. The implementation and analysis of our algorithm give rise to a number of interesting graph-theoretic and counting problems.

Published
2023

140. Extremal Combinatorics, Iterated Pigeonhole Arguments and Generalizations of PPP

Author

Amol Pasarkar and Christos Papadimitriou and Mihalis Yannakakis, Pasarkar, Amol, Papadimitriou, Christos, Yannakakis, Mihalis, Amol Pasarkar and Christos Papadimitriou and Mihalis Yannakakis, Pasarkar, Amol, Papadimitriou, Christos, and Yannakakis, Mihalis

Abstract

We study the complexity of computational problems arising from existence theorems in extremal combinatorics. For some of these problems, a solution is guaranteed to exist based on an iterated application of the Pigeonhole Principle. This results in the definition of a new complexity class within TFNP, which we call PLC (for "polynomial long choice"). PLC includes all of PPP, as well as numerous previously unclassified total problems, including search problems related to Ramsey’s theorem, the Sunflower theorem, the Erdős-Ko-Rado lemma, and König’s lemma. Whether the first two of these four problems are PLC-complete is an important open question which we pursue; in contrast, we show that the latter two are PPP-complete. Finally, we reframe PPP as an optimization problem, and define a hierarchy of such problems related to Turàn’s theorem.

Published
2023
Full Text
View/download PDF

141. Safety and Tolerability of Anthracycline-Containing Adjuvant Chemotherapy in Elderly High-Risk Breast Cancer Patients

Author

Karavasilis, Vasilios, Papadimitriou, Christos, Gogas, Helen, Kouvatseas, George, Pentheroudakis, George, Koutras, Angelos, Christodoulou, Christos, Bafaloukos, Dimitrios, Samantas, Epaminontas, Pisanidis, Nikolaos, Papakostas, Pavlos, Aravantinos, Gerasimos, Karanikiotis, Charisios, Kosmidis, Paris, Pectasides, Dimitrios, Dimopoulos, Meletios-Athanassios, and Fountzilas, George

Published
2016
Full Text
View/download PDF

149. Copy Number Variations (CNVs) Account for 10.8% of Pathogenic Variants in Patients Referred for Hereditary Cancer Testing

Author

AGIANNITOPOULOS, KONSTANTINOS, primary, PEPE, GEORGIA, additional, TSAOUSIS, GEORGIOS N., additional, POTSKA, KEVISA, additional, BOUZARELOU, DIMITRA, additional, KATSELI, ANASTASIA, additional, NTOGKA, CHRISTINA, additional, MEINTANI, ANGELIKI, additional, TSOULOS, NIKOLAOS, additional, GIASSAS, STYLIANOS, additional, VENIZELOS, VASSILEIOS, additional, MARKOPOULOS, CHRISTOS, additional, IOSIFIDOU, RODONIKI, additional, KARAGEORGOPOULOU, SOFIA, additional, CHRISTODOULOU, CHRISTOS, additional, NATSIOPOULOS, IOANNIS, additional, PAPAZISIS, KONSTANTINOS, additional, VASILAKI-ANTONATOU, MARIA, additional, KABLETSAS, ELEFTHERIOS, additional, PSYRRI, AMANTA, additional, ZIOGAS, DIMITRIOS, additional, LALLA, EFTHALIA, additional, KOUMARIANOU, ANNA, additional, ANASTASAKOU, KORNILIA, additional, PAPADIMITRIOU, CHRISTOS, additional, OZMEN, VAHIT, additional, TANSAN, SUALP, additional, KABAN, KERIM, additional, OZATLI, TAHSIN, additional, ENIU, DAN TUDOR, additional, CHIOREAN, ANGELICA, additional, BLIDARU, ALEXANDRU, additional, RINSMA, MARRIT, additional, PAPADOPOULOU, EIRINI, additional, and NASIOULAS, GEORGE, additional

Published
2023
Full Text
View/download PDF

Catalog

Books, media, physical & digital resources
See catalog results