77 Search Results for "Papadimitriou, Christos"

Volume

LIPIcs, Volume 67

8th Innovations in Theoretical Computer Science Conference (ITCS 2017)

ITCS 2017, January 9-11, 2017, Berkeley, CA, USA

Editors: Christos H. Papadimitriou

Document
DOI: 10.4230/LIPIcs.ITCS.2023.88
Extremal Combinatorics, Iterated Pigeonhole Arguments and Generalizations of PPP

Authors: Amol Pasarkar, Christos Papadimitriou, and Mihalis Yannakakis

Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)

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.
Cite as

Amol Pasarkar, Christos Papadimitriou, and Mihalis Yannakakis. Extremal Combinatorics, Iterated Pigeonhole Arguments and Generalizations of PPP. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 88:1-88:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{pasarkar_et_al:LIPIcs.ITCS.2023.88,
  author =	{Pasarkar, Amol and Papadimitriou, Christos and Yannakakis, Mihalis},
  title =	{{Extremal Combinatorics, Iterated Pigeonhole Arguments and Generalizations of PPP}},
  booktitle =	{14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
  pages =	{88:1--88:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-263-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{251},
  editor =	{Tauman Kalai, Yael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.88},
  URN =		{urn:nbn:de:0030-drops-175913},
  doi =		{10.4230/LIPIcs.ITCS.2023.88},
  annote =	{Keywords: Total Complexity, Extremal Combinatorics, Pigeonhole Principle}
}
Document
DOI: 10.4230/LIPIcs.CCC.2022.37
Derandomization from Time-Space Tradeoffs

Authors: Oliver Korten

Published in: LIPIcs, Volume 234, 37th Computational Complexity Conference (CCC 2022)

Abstract
A recurring challenge in the theory of pseudorandomness and circuit complexity is the explicit construction of "incompressible strings," i.e. finite objects which lack a specific type of structure or simplicity. In most cases, there is an associated NP search problem which we call the "compression problem," where we are given a candidate object and must either find a compressed/structured representation of it or determine that none exist. For a particular notion of compressibility, a natural question is whether an efficient algorithm for the compression problem would aide us in the construction of incompressible objects. Consider the following two instances of this question: 1) Does an efficient algorithm for circuit minimization imply efficient constructions of hard truth tables? 2) Does an efficient algorithm for factoring integers imply efficient constructions of large prime numbers? In this work, we connect these kinds of questions to the long-standing challenge of proving time-space tradeoffs for Turing machines, and proving stronger separations between the RAM and 1-tape computation models. In particular, one of our main theorems shows that modest time-space tradeoffs for deterministic exponential time, or separations between basic Turing machine memory models, would imply a positive answer to both (1) and (2). These results apply to the derandomization of a wider class of explicit construction problems, where we have some efficient compression scheme that encodes n-bit strings using < n bits, and we aim to construct an n-bit string which cannot be recovered from its encoding.
Cite as

Oliver Korten. Derandomization from Time-Space Tradeoffs. In 37th Computational Complexity Conference (CCC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 234, pp. 37:1-37:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{korten:LIPIcs.CCC.2022.37,
  author =	{Korten, Oliver},
  title =	{{Derandomization from Time-Space Tradeoffs}},
  booktitle =	{37th Computational Complexity Conference (CCC 2022)},
  pages =	{37:1--37:26},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-241-9},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{234},
  editor =	{Lovett, Shachar},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2022.37},
  URN =		{urn:nbn:de:0030-drops-165993},
  doi =		{10.4230/LIPIcs.CCC.2022.37},
  annote =	{Keywords: Pseudorandomness, circuit complexity, total functions}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2021.44
Total Functions in the Polynomial Hierarchy

Authors: Robert Kleinberg, Oliver Korten, Daniel Mitropolsky, and Christos Papadimitriou

Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)

Abstract
We identify several genres of search problems beyond NP for which existence of solutions is guaranteed. One class that seems especially rich in such problems is PEPP (for "polynomial empty pigeonhole principle"), which includes problems related to existence theorems proved through the union bound, such as finding a bit string that is far from all codewords, finding an explicit rigid matrix, as well as a problem we call Complexity, capturing Complexity Theory’s quest. When the union bound is generous, in that solutions constitute at least a polynomial fraction of the domain, we have a family of seemingly weaker classes α-PEPP, which are inside FP^NP|poly. Higher in the hierarchy, we identify the constructive version of the Sauer-Shelah lemma and the appropriate generalization of PPP that contains it, as well as the problem of finding a king in a tournament (a vertex k such that all other vertices are defeated by k, or by somebody k defeated).
Cite as

Robert Kleinberg, Oliver Korten, Daniel Mitropolsky, and Christos Papadimitriou. Total Functions in the Polynomial Hierarchy. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 44:1-44:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{kleinberg_et_al:LIPIcs.ITCS.2021.44,
  author =	{Kleinberg, Robert and Korten, Oliver and Mitropolsky, Daniel and Papadimitriou, Christos},
  title =	{{Total Functions in the Polynomial Hierarchy}},
  booktitle =	{12th Innovations in Theoretical Computer Science Conference (ITCS 2021)},
  pages =	{44:1--44:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-177-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{185},
  editor =	{Lee, James R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.44},
  URN =		{urn:nbn:de:0030-drops-135835},
  doi =		{10.4230/LIPIcs.ITCS.2021.44},
  annote =	{Keywords: total complexity, polynomial hierarchy, pigeonhole principle}
}
Document
DOI: 10.4230/LIPIcs.CCC.2020.19
On the Complexity of Modulo-q Arguments and the Chevalley - Warning Theorem

Authors: Mika Göös, Pritish Kamath, Katerina Sotiraki, and Manolis Zampetakis

Published in: LIPIcs, Volume 169, 35th Computational Complexity Conference (CCC 2020)

Abstract
We study the search problem class PPA_q defined as a modulo-q analog of the well-known polynomial parity argument class PPA introduced by Papadimitriou (JCSS 1994). Our first result shows that this class can be characterized in terms of PPA_p for prime p. Our main result is to establish that an explicit version of a search problem associated to the Chevalley - Warning theorem is complete for PPA_p for prime p. This problem is natural in that it does not explicitly involve circuits as part of the input. It is the first such complete problem for PPA_p when p ≥ 3. Finally we discuss connections between Chevalley-Warning theorem and the well-studied short integer solution problem and survey the structural properties of PPA_q.
Cite as

Mika Göös, Pritish Kamath, Katerina Sotiraki, and Manolis Zampetakis. On the Complexity of Modulo-q Arguments and the Chevalley - Warning Theorem. In 35th Computational Complexity Conference (CCC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 169, pp. 19:1-19:42, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{goos_et_al:LIPIcs.CCC.2020.19,
  author =	{G\"{o}\"{o}s, Mika and Kamath, Pritish and Sotiraki, Katerina and Zampetakis, Manolis},
  title =	{{On the Complexity of Modulo-q Arguments and the Chevalley - Warning Theorem}},
  booktitle =	{35th Computational Complexity Conference (CCC 2020)},
  pages =	{19:1--19:42},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-156-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{169},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2020.19},
  URN =		{urn:nbn:de:0030-drops-125712},
  doi =		{10.4230/LIPIcs.CCC.2020.19},
  annote =	{Keywords: Total NP Search Problems, Modulo-q arguments, Chevalley - Warning Theorem}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2020.18
Tarski’s Theorem, Supermodular Games, and the Complexity of Equilibria

Authors: Kousha Etessami, Christos Papadimitriou, Aviad Rubinstein, and Mihalis Yannakakis

Published in: LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)

Abstract
The use of monotonicity and Tarski’s theorem in existence proofs of equilibria is very widespread in economics, while Tarski’s theorem is also often used for similar purposes in the context of verification. However, there has been relatively little in the way of analysis of the complexity of finding the fixed points and equilibria guaranteed by this result. We study a computational formalism based on monotone functions on the d-dimensional grid with sides of length N, and their fixed points, as well as the closely connected subject of supermodular games and their equilibria. It is known that finding some (any) fixed point of a monotone function can be done in time log^d N, and we show it requires at least log^2 N function evaluations already on the 2-dimensional grid, even for randomized algorithms. We show that the general Tarski problem of finding some fixed point, when the monotone function is given succinctly (by a boolean circuit), is in the class PLS of problems solvable by local search and, rather surprisingly, also in the class PPAD. Finding the greatest or least fixed point guaranteed by Tarski’s theorem, however, requires d ⋅ N steps, and is NP-hard in the white box model. For supermodular games, we show that finding an equilibrium in such games is essentially computationally equivalent to the Tarski problem, and finding the maximum or minimum equilibrium is similarly harder. Interestingly, two-player supermodular games where the strategy space of one player is one-dimensional can be solved in O(log N) steps. We also show that computing (approximating) the value of Condon’s (Shapley’s) stochastic games reduces to the Tarski problem. An important open problem highlighted by this work is proving a Ω(log^d N) lower bound for small fixed dimension d ≥ 3.
Cite as

Kousha Etessami, Christos Papadimitriou, Aviad Rubinstein, and Mihalis Yannakakis. Tarski’s Theorem, Supermodular Games, and the Complexity of Equilibria. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 18:1-18:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{etessami_et_al:LIPIcs.ITCS.2020.18,
  author =	{Etessami, Kousha and Papadimitriou, Christos and Rubinstein, Aviad and Yannakakis, Mihalis},
  title =	{{Tarski’s Theorem, Supermodular Games, and the Complexity of Equilibria}},
  booktitle =	{11th Innovations in Theoretical Computer Science Conference (ITCS 2020)},
  pages =	{18:1--18:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-134-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{151},
  editor =	{Vidick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.18},
  URN =		{urn:nbn:de:0030-drops-117037},
  doi =		{10.4230/LIPIcs.ITCS.2020.18},
  annote =	{Keywords: Tarski’s theorem, supermodular games, monotone functions, lattices, fixed points, Nash equilibria, computational complexity, PLS, PPAD, stochastic games, oracle model, lower bounds}
}
Document
DOI: 10.4230/LIPIcs.STACS.2019.31
Wealth Inequality and the Price of Anarchy

Authors: Kurtuluş Gemici, Elias Koutsoupias, Barnabé Monnot, Christos H. Papadimitriou, and Georgios Piliouras

Published in: LIPIcs, Volume 126, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)

Abstract
The price of anarchy quantifies the degradation of social welfare in games due to the lack of a centralized authority that can enforce the optimal outcome. It is known that, in certain games, such effects can be ameliorated via tolls or taxes. This leads to a natural, but largely unexplored, question: what is the effect of such transfers on social inequality? We study this question in nonatomic congestion games, arguably one of the most thoroughly studied settings from the perspective of the price of anarchy. We introduce a new model that incorporates the income distribution of the population and captures the income elasticity of travel time (i.e., how does loss of time translate to lost income). This allows us to argue about the equality of wealth distribution both before and after employing a mechanism. We establish that, under reasonable assumptions, tolls always increase inequality in symmetric congestion games under any reasonable metric of inequality such as the Gini index. We introduce the inequity index, a novel measure for quantifying the magnitude of these forces towards a more unbalanced wealth distribution and show it has good normative properties (robustness to scaling of income, no-regret learning). We analyze inequity both in theoretical settings (Pigou’s network under various wealth distributions) as well as experimental ones (based on a large scale field experiment in Singapore). Finally, we provide an algorithm for computing optimal tolls for any point of the trade-off of relative importance of efficiency and equality. We conclude with a discussion of our findings in the context of theories of justice as developed in contemporary social sciences and present several directions for future research.
Cite as

Kurtuluş Gemici, Elias Koutsoupias, Barnabé Monnot, Christos H. Papadimitriou, and Georgios Piliouras. Wealth Inequality and the Price of Anarchy. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 31:1-31:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{gemici_et_al:LIPIcs.STACS.2019.31,
  author =	{Gemici, Kurtulu\c{s} and Koutsoupias, Elias and Monnot, Barnab\'{e} and Papadimitriou, Christos H. and Piliouras, Georgios},
  title =	{{Wealth Inequality and the Price of Anarchy}},
  booktitle =	{36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)},
  pages =	{31:1--31:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-100-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{126},
  editor =	{Niedermeier, Rolf and Paul, Christophe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2019.31},
  URN =		{urn:nbn:de:0030-drops-102707},
  doi =		{10.4230/LIPIcs.STACS.2019.31},
  annote =	{Keywords: congestion games, inequality}
}
Document
DOI: 10.4230/LIPIcs.STACS.2019.44
Tight Complexity Lower Bounds for Integer Linear Programming with Few Constraints

Authors: Dušan Knop, Michał Pilipczuk, and Marcin Wrochna

Published in: LIPIcs, Volume 126, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)

Abstract
We consider the standard ILP Feasibility problem: given an integer linear program of the form {Ax = b, x >= 0}, where A is an integer matrix with k rows and l columns, x is a vector of l variables, and b is a vector of k integers, we ask whether there exists x in N^l that satisfies Ax = b. Each row of A specifies one linear constraint on x; our goal is to study the complexity of ILP Feasibility when both k, the number of constraints, and |A|_infty, the largest absolute value of an entry in A, are small. Papadimitriou [Christos H. Papadimitriou, 1981] was the first to give a fixed-parameter algorithm for ILP Feasibility under parameterization by the number of constraints that runs in time ((|A |_infty + |b|_infty) * k)^O(k^2). This was very recently improved by Eisenbrand and Weismantel [Friedrich Eisenbrand and Robert Weismantel, 2018], who used the Steinitz lemma to design an algorithm with running time (k |A|_infty)^{O(k)}* |b|_infty^2, which was subsequently improved by Jansen and Rohwedder [Klaus Jansen and Lars Rohwedder, 2019] to O(k |A |_infty)^k* log |b|_infty. We prove that for {0,1}-matrices A, the running time of the algorithm of Eisenbrand and Weismantel is probably optimal: an algorithm with running time 2^{o(k log k)}* (l+|{b}|_infty)^{o(k)} would contradict the Exponential Time Hypothesis (ETH). This improves previous non-tight lower bounds of Fomin et al. [Fedor V. Fomin et al., 2018]. We then consider integer linear programs that may have many constraints, but they need to be structured in a "shallow" way. Precisely, we consider the parameter {dual treedepth} of the matrix A, denoted td_D(A), which is the treedepth of the graph over the rows of A, where two rows are adjacent if in some column they simultaneously contain a non-zero entry. It was recently shown by Koutecký et al. [Martin Koutecký et al., 2018] that {ILP Feasibility} can be solved in time |A |_infty^{2^O(td_D(A))} * (k+l+log |b|_infty)^O(1). We present a streamlined proof of this fact and prove that, again, this running time is probably optimal: even assuming that all entries of A and {b} are in {-1,0,1}, the existence of an algorithm with running time 2^{2^o(td_D(A))} * (k+l)^O(1) would contradict the ETH.
Cite as

Dušan Knop, Michał Pilipczuk, and Marcin Wrochna. Tight Complexity Lower Bounds for Integer Linear Programming with Few Constraints. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 44:1-44:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{knop_et_al:LIPIcs.STACS.2019.44,
  author =	{Knop, Du\v{s}an and Pilipczuk, Micha{\l} and Wrochna, Marcin},
  title =	{{Tight Complexity Lower Bounds for Integer Linear Programming with Few Constraints}},
  booktitle =	{36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)},
  pages =	{44:1--44:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-100-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{126},
  editor =	{Niedermeier, Rolf and Paul, Christophe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2019.44},
  URN =		{urn:nbn:de:0030-drops-102831},
  doi =		{10.4230/LIPIcs.STACS.2019.44},
  annote =	{Keywords: integer linear programming, fixed-parameter tractability, ETH}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2019.57
Random Projection in the Brain and Computation with Assemblies of Neurons

Authors: Christos H. Papadimitriou and Santosh S. Vempala

Published in: LIPIcs, Volume 124, 10th Innovations in Theoretical Computer Science Conference (ITCS 2019)

Abstract
It has been recently shown via simulations [Dasgupta et al., 2017] that random projection followed by a cap operation (setting to one the k largest elements of a vector and everything else to zero), a map believed to be an important part of the insect olfactory system, has strong locality sensitivity properties. We calculate the asymptotic law whereby the overlap in the input vectors is conserved, verifying mathematically this empirical finding. We then focus on the far more complex homologous operation in the mammalian brain, the creation through successive projections and caps of an assembly (roughly, a set of excitatory neurons representing a memory or concept) in the presence of recurrent synapses and plasticity. After providing a careful definition of assemblies, we prove that the operation of assembly projection converges with high probability, over the randomness of synaptic connectivity, even if plasticity is relatively small (previous proofs relied on high plasticity). We also show that assembly projection has itself some locality preservation properties. Finally, we propose a large repertoire of assembly operations, including associate, merge, reciprocal project, and append, each of them both biologically plausible and consistent with what we know from experiments, and show that this computational system is capable of simulating, again with high probability, arbitrary computation in a quite natural way. We hope that this novel way of looking at brain computation, open-ended and based on reasonably mainstream ideas in neuroscience, may prove an attractive entry point for computer scientists to work on understanding the brain.
Cite as

Christos H. Papadimitriou and Santosh S. Vempala. Random Projection in the Brain and Computation with Assemblies of Neurons. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 57:1-57:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{papadimitriou_et_al:LIPIcs.ITCS.2019.57,
  author =	{Papadimitriou, Christos H. and Vempala, Santosh S.},
  title =	{{Random Projection in the Brain and Computation with Assemblies of Neurons}},
  booktitle =	{10th Innovations in Theoretical Computer Science Conference (ITCS 2019)},
  pages =	{57:1--57:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-095-8},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{124},
  editor =	{Blum, Avrim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2019.57},
  URN =		{urn:nbn:de:0030-drops-101506},
  doi =		{10.4230/LIPIcs.ITCS.2019.57},
  annote =	{Keywords: Brain computation, random projection, assemblies, plasticity, memory, association}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2018.37
Towards a Unified Complexity Theory of Total Functions

Authors: Paul W. Goldberg and Christos H. Papadimitriou

Published in: LIPIcs, Volume 94, 9th Innovations in Theoretical Computer Science Conference (ITCS 2018)

Abstract
The class TFNP, of NP search problems where all instances have solutions, appears not to have complete problems. However, TFNP contains various syntactic subclasses and important problems. We introduce a syntactic class of problems that contains these known subclasses, for the purpose of understanding and classifying TFNP problems. This class is defined in terms of the search for an error in a concisely-represented formal proof. Finally, the known complexity subclasses are based on existence theorems that hold for finite structures; from Herbrand's Theorem, we note that such theorems must apply specifically to finite structures, and not infinite ones.
Cite as

Paul W. Goldberg and Christos H. Papadimitriou. Towards a Unified Complexity Theory of Total Functions. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 37:1-37:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{goldberg_et_al:LIPIcs.ITCS.2018.37,
  author =	{Goldberg, Paul W. and Papadimitriou, Christos H.},
  title =	{{Towards a Unified Complexity Theory of Total Functions}},
  booktitle =	{9th Innovations in Theoretical Computer Science Conference (ITCS 2018)},
  pages =	{37:1--37:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-060-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{94},
  editor =	{Karlin, Anna R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2018.37},
  URN =		{urn:nbn:de:0030-drops-83403},
  doi =		{10.4230/LIPIcs.ITCS.2018.37},
  annote =	{Keywords: Computational complexity, first-order logic, proof system, NP search functions, TFNP}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2018.57
Long Term Memory and the Densest K-Subgraph Problem

Authors: Robert Legenstein, Wolfgang Maass, Christos H. Papadimitriou, and Santosh S. Vempala

Published in: LIPIcs, Volume 94, 9th Innovations in Theoretical Computer Science Conference (ITCS 2018)

Abstract
In a recent experiment, a cell in the human medial temporal lobe (MTL) encoding one sensory stimulus starts to also respond to a second stimulus following a combined experience associating the two. We develop a theoretical model predicting that an assembly of cells with exceptionally high synaptic intraconnectivity can emerge, in response to a particular sensory experience, to encode and abstract that experience. We also show that two such assemblies are modified to increase their intersection after a sensory event that associates the two corresponding stimuli. The main technical tools employed are random graph theory, and Bernoulli approximations. Assembly creation must overcome a computational challenge akin to the Densest K-Subgraph problem, namely selecting, from a large population of randomly and sparsely interconnected cells, a subset with exceptionally high density of interconnections. We identify three mechanisms that help achieve this feat in our model: (1) a simple two-stage randomized algorithm, and (2) the "triangle completion bias" in synaptic connectivity and a "birthday paradox", while (3) the strength of these connections is enhanced through Hebbian plasticity.
Cite as

Robert Legenstein, Wolfgang Maass, Christos H. Papadimitriou, and Santosh S. Vempala. Long Term Memory and the Densest K-Subgraph Problem. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 57:1-57:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{legenstein_et_al:LIPIcs.ITCS.2018.57,
  author =	{Legenstein, Robert and Maass, Wolfgang and Papadimitriou, Christos H. and Vempala, Santosh S.},
  title =	{{Long Term Memory and the Densest K-Subgraph Problem}},
  booktitle =	{9th Innovations in Theoretical Computer Science Conference (ITCS 2018)},
  pages =	{57:1--57:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-060-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{94},
  editor =	{Karlin, Anna R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2018.57},
  URN =		{urn:nbn:de:0030-drops-83593},
  doi =		{10.4230/LIPIcs.ITCS.2018.57},
  annote =	{Keywords: Brain computation, long term memory, assemblies, association}
}
Document
Complete Volume
DOI: 10.4230/LIPIcs.ITCS.2017
LIPIcs, Volume 67, ITCS'17, Complete Volume

Authors: Christos H. Papadimitriou

Published in: LIPIcs, Volume 67, 8th Innovations in Theoretical Computer Science Conference (ITCS 2017)

Abstract
LIPIcs, Volume 67, ITCS'17, Complete Volume
Cite as

8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@Proceedings{papadimitriou:LIPIcs.ITCS.2017,
  title =	{{LIPIcs, Volume 67, ITCS'17, Complete Volume}},
  booktitle =	{8th Innovations in Theoretical Computer Science Conference (ITCS 2017)},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-029-3},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{67},
  editor =	{Papadimitriou, Christos H.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017},
  URN =		{urn:nbn:de:0030-drops-82066},
  doi =		{10.4230/LIPIcs.ITCS.2017},
  annote =	{Keywords: Theory of Computation, Mathematics of Computing}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.ITCS.2017.0
Front Matter, Table of Contents, Preface, Conference Organization

Authors: Christos H. Papadimitriou

Published in: LIPIcs, Volume 67, 8th Innovations in Theoretical Computer Science Conference (ITCS 2017)

Abstract
Front Matter, Table of Contents, Preface, Conference Organization
Cite as

8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 0:i-0:x, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{papadimitriou:LIPIcs.ITCS.2017.0,
  author =	{Papadimitriou, Christos H.},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{8th Innovations in Theoretical Computer Science Conference (ITCS 2017)},
  pages =	{0:i--0:x},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-029-3},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{67},
  editor =	{Papadimitriou, Christos H.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.0},
  URN =		{urn:nbn:de:0030-drops-82025},
  doi =		{10.4230/LIPIcs.ITCS.2017.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2017.1
Separators in Region Intersection Graphs

Authors: James R. Lee

Published in: LIPIcs, Volume 67, 8th Innovations in Theoretical Computer Science Conference (ITCS 2017)

Abstract
For undirected graphs G=(V,E) and G_0=(V_0,E_0), say that G is a region intersection graph over G_0 if there is a family of connected subsets {R_u \subseteq V_0 : u \in V} of G_0 such that {u,v} \in E \iff R_u \cap R_v \neq \emptyset. We show if G_0 excludes the complete graph K_h as a minor for some h \geq 1, then every region intersection graph G over G_0 with m edges has a balanced separator with at most c_h \sqrt{m} nodes, where c_h is a constant depending only on h. If G additionally has uniformly bounded vertex degrees, then such a separator is found by spectral partitioning. A string graph is the intersection graph of continuous arcs in the plane. String graphs are precisely region intersection graphs over planar graphs. Thus the preceding result implies that every string graph with m edges has a balanced separator of size O(\sqrt{m}). This bound is optimal, as it generalizes the planar separator theorem. It confirms a conjecture of Fox and Pach (2010), and improves over the O(\sqrt{m} \log m) bound of Matousek (2013).
Cite as

James R. Lee. Separators in Region Intersection Graphs. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 1:1-1:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{lee:LIPIcs.ITCS.2017.1,
  author =	{Lee, James R.},
  title =	{{Separators in Region Intersection Graphs}},
  booktitle =	{8th Innovations in Theoretical Computer Science Conference (ITCS 2017)},
  pages =	{1:1--1:8},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-029-3},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{67},
  editor =	{Papadimitriou, Christos H.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.1},
  URN =		{urn:nbn:de:0030-drops-81970},
  doi =		{10.4230/LIPIcs.ITCS.2017.1},
  annote =	{Keywords: Graph separators, planar graphs, spectral partitioning}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2017.2
Gradient Descent Only Converges to Minimizers: Non-Isolated Critical Points and Invariant Regions

Authors: Ioannis Panageas and Georgios Piliouras

Published in: LIPIcs, Volume 67, 8th Innovations in Theoretical Computer Science Conference (ITCS 2017)

Abstract
Given a twice continuously differentiable cost function f, we prove that the set of initial conditions so that gradient descent converges to saddle points where \nabla^2 f has at least one strictly negative eigenvalue, has (Lebesgue) measure zero, even for cost functions f with non-isolated critical points, answering an open question in [Lee, Simchowitz, Jordan, Recht, COLT 2016]. Moreover, this result extends to forward-invariant convex subspaces, allowing for weak (non-globally Lipschitz) smoothness assumptions. Finally, we produce an upper bound on the allowable step-size.
Cite as

Ioannis Panageas and Georgios Piliouras. Gradient Descent Only Converges to Minimizers: Non-Isolated Critical Points and Invariant Regions. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 2:1-2:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{panageas_et_al:LIPIcs.ITCS.2017.2,
  author =	{Panageas, Ioannis and Piliouras, Georgios},
  title =	{{Gradient Descent Only Converges to Minimizers: Non-Isolated Critical Points and Invariant Regions}},
  booktitle =	{8th Innovations in Theoretical Computer Science Conference (ITCS 2017)},
  pages =	{2:1--2:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-029-3},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{67},
  editor =	{Papadimitriou, Christos H.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.2},
  URN =		{urn:nbn:de:0030-drops-81640},
  doi =		{10.4230/LIPIcs.ITCS.2017.2},
  annote =	{Keywords: Gradient Descent, Center-stable manifold, Saddle points, Hessian}
}
  • Refine by Author
  • 10 Papadimitriou, Christos H.
  • 3 Papadimitriou, Christos
  • 3 Piliouras, Georgios
  • 3 Vazirani, Umesh V.
  • 3 Vidick, Thomas
  • Show More...

  • Refine by Classification
  • 3 Theory of computation → Complexity classes
  • 1 Theory of computation → Algorithmic game theory
  • 1 Theory of computation → Complexity theory and logic
  • 1 Theory of computation → Computational complexity and cryptography
  • 1 Theory of computation → Fixed parameter tractability
  • Show More...

  • Refine by Keyword
  • 3 Communication Complexity
  • 3 circuit complexity
  • 2 Brain computation
  • 2 Cryptography
  • 2 PPAD
  • Show More...

  • Refine by Type
  • 76 document
  • 1 volume

  • Refine by Publication Year
  • 64 2017
  • 3 2019
  • 2 2018
  • 2 2020
  • 1 2003
  • Show More...

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact