47 citations · 139 across the 36 of their papers we have counts for
43 papers
The Computational Complexity of Multi-player Concave Games and Kakutani Fixed Points
Christos H. Papadimitriou, Emmanouil-Vasileios Vlatakis-Gkaragkounis, Manolis Zampetakis
Kakutani's Fixed Point theorem is a fundamental theorem in topology with numerous applications in game theory and economics. Computational formulations of Kakutani exist only in sp…
Assemblies of neurons learn to classify well-separated distributions
Max Dabagia, Christos H. Papadimitriou, Santosh S. Vempala
An assembly is a large population of neurons whose synchronous firing is hypothesized to represent a memory, concept, word, and other cognitive categories. Assemblies are believed…
A Biologically Plausible Parser
Daniel Mitropolsky, Michael J. Collins, Christos H. Papadimitriou
We describe a parser of English effectuated by biologically plausible neurons and synapses, and implemented through the Assembly Calculus, a recently proposed computational framewo…
Public Goods Games in Directed Networks
Christos Papadimitriou, Binghui Peng
Public goods games in undirected networks are generally known to have pure Nash equilibria, which are easy to find. In contrast, we prove that, in directed networks, a broad range…
Self-Attention Networks Can Process Bounded Hierarchical Languages
Shunyu Yao, Binghui Peng, Christos Papadimitriou +1
Despite their impressive performance in NLP, self-attention networks were recently proved to be limited for processing formal languages with hierarchical structure, such as $\maths…
Online Stochastic Max-Weight Bipartite Matching: Beyond Prophet Inequalities
Christos Papadimitriou, Tristan Pollner, Amin Saberi +1
The rich literature on online Bayesian selection problems has long focused on so-called prophet inequalities, which compare the gain of an online algorithm to that of a "prophet" w…