6 Search Results for "Hansen, Kristoffer Arnsfelt"

Document
DOI: 10.4230/LIPIcs.ITCS.2022.38
Smaller ACC0 Circuits for Symmetric Functions

Authors: Brynmor Chapman and R. Ryan Williams

Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)

Abstract
What is the power of constant-depth circuits with MOD_m gates, that can count modulo m? Can they efficiently compute MAJORITY and other symmetric functions? When m is a constant prime power, the answer is well understood. In this regime, Razborov and Smolensky proved in the 1980s that MAJORITY and MOD_m require super-polynomial-size MOD_q circuits, where q is any prime power not dividing m. However, relatively little is known about the power of MOD_m gates when m is not a prime power. For example, it is still open whether every problem decidable in exponential time can be computed by depth-3 circuits of polynomial-size and only MOD_6 gates. In this paper, we shed some light on the difficulty of proving lower bounds for MOD_m circuits, by giving new upper bounds. We show how to construct MOD_m circuits computing symmetric functions with non-prime power m, with size-depth tradeoffs that beat the longstanding lower bounds for AC^0[m] circuits when m is a prime power. Furthermore, we observe that our size-depth tradeoff circuits have essentially optimal dependence on m and d in the exponent, under a natural circuit complexity hypothesis. For example, we show that for every ε > 0, every symmetric function can be computed using MOD_m circuits of depth 3 and 2^{n^ε} size, for a constant m depending only on ε > 0. In other words, depth-3 CC^0 circuits can compute any symmetric function in subexponential size. This demonstrates a significant difference in the power of depth-3 CC^0 circuits, compared to other models: for certain symmetric functions, depth-3 AC^0 circuits require 2^{Ω(√n)} size [Håstad 1986], and depth-3 AC^0[p^k] circuits (for fixed prime power p^k) require 2^{Ω(n^{1/6})} size [Smolensky 1987]. Even for depth-2 MOD_p ∘ MOD_m circuits, 2^{Ω(n)} lower bounds were known [Barrington Straubing Thérien 1990].
Cite as

Brynmor Chapman and R. Ryan Williams. Smaller ACC0 Circuits for Symmetric Functions. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 38:1-38:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{chapman_et_al:LIPIcs.ITCS.2022.38,
  author =	{Chapman, Brynmor and Williams, R. Ryan},
  title =	{{Smaller ACC0 Circuits for Symmetric Functions}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{38:1--38:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.38},
  URN =		{urn:nbn:de:0030-drops-156342},
  doi =		{10.4230/LIPIcs.ITCS.2022.38},
  annote =	{Keywords: ACC, CC, circuit complexity, symmetric functions, Chinese Remainder Theorem}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2021.24
Strong Approximate Consensus Halving and the Borsuk-Ulam Theorem

Authors: Eleni Batziou, Kristoffer Arnsfelt Hansen, and Kasper Høgh

Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)

Abstract
In the consensus halving problem we are given n agents with valuations over the interval [0,1]. The goal is to divide the interval into at most n+1 pieces (by placing at most n cuts), which may be combined to give a partition of [0,1] into two sets valued equally by all agents. The existence of a solution may be established by the Borsuk-Ulam theorem. We consider the task of computing an approximation of an exact solution of the consensus halving problem, where the valuations are given by distribution functions computed by algebraic circuits. Here approximation refers to computing a point that is ε-close to an exact solution, also called strong approximation. We show that this task is polynomial time equivalent to computing an approximation to an exact solution of the Borsuk-Ulam search problem defined by a continuous function that is computed by an algebraic circuit. The Borsuk-Ulam search problem is the defining problem of the complexity class BU. We introduce a new complexity class BBU to also capture an alternative formulation of the Borsuk-Ulam theorem from a computational point of view. We investigate their relationship and prove several structural results for these classes as well as for the complexity class FIXP.
Cite as

Eleni Batziou, Kristoffer Arnsfelt Hansen, and Kasper Høgh. Strong Approximate Consensus Halving and the Borsuk-Ulam Theorem. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 24:1-24:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{batziou_et_al:LIPIcs.ICALP.2021.24,
  author =	{Batziou, Eleni and Hansen, Kristoffer Arnsfelt and H{\o}gh, Kasper},
  title =	{{Strong Approximate Consensus Halving and the Borsuk-Ulam Theorem}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{24:1--24:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.24},
  URN =		{urn:nbn:de:0030-drops-140939},
  doi =		{10.4230/LIPIcs.ICALP.2021.24},
  annote =	{Keywords: Consensus halving, Computational Complexity, Borsuk-Ulam}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2020.45
∃ℝ-Completeness of Stationary Nash Equilibria in Perfect Information Stochastic Games

Authors: Kristoffer Arnsfelt Hansen and Steffan Christ Sølvsten

Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)

Abstract
We show that the problem of deciding whether in a multi-player perfect information recursive game (i.e. a stochastic game with terminal rewards) there exists a stationary Nash equilibrium ensuring each player a certain payoff is ∃ℝ-complete. Our result holds for acyclic games, where a Nash equilibrium may be computed efficiently by backward induction, and even for deterministic acyclic games with non-negative terminal rewards. We further extend our results to the existence of Nash equilibria where a single player is surely winning. Combining our result with known gadget games without any stationary Nash equilibrium, we obtain that for cyclic games, just deciding existence of any stationary Nash equilibrium is ∃ℝ-complete. This holds for reach-a-set games, stay-in-a-set games, and for deterministic recursive games.
Cite as

Kristoffer Arnsfelt Hansen and Steffan Christ Sølvsten. ∃ℝ-Completeness of Stationary Nash Equilibria in Perfect Information Stochastic Games. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 45:1-45:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{hansen_et_al:LIPIcs.MFCS.2020.45,
  author =	{Hansen, Kristoffer Arnsfelt and S{\o}lvsten, Steffan Christ},
  title =	{{\exists\mathbb{R}-Completeness of Stationary Nash Equilibria in Perfect Information Stochastic Games}},
  booktitle =	{45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
  pages =	{45:1--45:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-159-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{170},
  editor =	{Esparza, Javier and Kr\'{a}l', Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.45},
  URN =		{urn:nbn:de:0030-drops-127113},
  doi =		{10.4230/LIPIcs.MFCS.2020.45},
  annote =	{Keywords: Existential Theory of the Reals, Stationary Nash Equilibrium, Perfect Information Stochastic Games}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2018.41
Low Rank Approximation of Binary Matrices: Column Subset Selection and Generalizations

Authors: Chen Dan, Kristoffer Arnsfelt Hansen, He Jiang, Liwei Wang, and Yuchen Zhou

Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)

Abstract
Low rank approximation of matrices is an important tool in machine learning. Given a data matrix, low rank approximation helps to find factors, patterns, and provides concise representations for the data. Research on low rank approximation usually focuses on real matrices. However, in many applications data are binary (categorical) rather than continuous. This leads to the problem of low rank approximation of binary matrices. Here we are given a d x n binary matrix A and a small integer k < d. The goal is to find two binary matrices U and V of sizes d x k and k x n respectively, so that the Frobenius norm of A - U V is minimized. There are two models of this problem, depending on the definition of the dot product of binary vectors: The GF(2) model and the Boolean semiring model. Unlike low rank approximation of a real matrix which can be efficiently solved by Singular Value Decomposition, we show that approximation of a binary matrix is NP-hard, even for k=1. In this paper, our main concern is the problem of Column Subset Selection (CSS), in which the low rank matrix U must be formed by k columns of the data matrix, and we are interested in the approximation ratio achievable by CSS for binary matrices. For the GF(2) model, we show that CSS has approximation ratio bounded by k/2+1+k/(2(2^k-1)) and this is asymptotically tight. For the Boolean model, it turns out that CSS is no longer sufficient to obtain a bound. We then develop a Generalized CSS (GCSS) procedure in which the columns of U are generated from Boolean formulas operating bitwise on selected columns of the data matrix. We show that the approximation ratio achieved by GCSS is bounded by 2^(k-1)+1, and argue that an exponential dependency on k is seems inherent.
Cite as

Chen Dan, Kristoffer Arnsfelt Hansen, He Jiang, Liwei Wang, and Yuchen Zhou. Low Rank Approximation of Binary Matrices: Column Subset Selection and Generalizations. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 41:1-41:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{dan_et_al:LIPIcs.MFCS.2018.41,
  author =	{Dan, Chen and Hansen, Kristoffer Arnsfelt and Jiang, He and Wang, Liwei and Zhou, Yuchen},
  title =	{{Low Rank Approximation of Binary Matrices: Column Subset Selection and Generalizations}},
  booktitle =	{43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)},
  pages =	{41:1--41:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-086-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{117},
  editor =	{Potapov, Igor and Spirakis, Paul and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.41},
  URN =		{urn:nbn:de:0030-drops-96239},
  doi =		{10.4230/LIPIcs.MFCS.2018.41},
  annote =	{Keywords: Approximation Algorithms, Low Rank Approximation, Binary Matrices}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2017.55
Strategy Complexity of Concurrent Safety Games

Authors: Krishnendu Chatterjee, Kristoffer Arnsfelt Hansen, and Rasmus Ibsen-Jensen

Published in: LIPIcs, Volume 83, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)

Abstract
We consider two player, zero-sum, finite-state concurrent reachability games, played for an infinite number of rounds, where in every round, each player simultaneously and independently of the other players chooses an action, whereafter the successor state is determined by a probability distribution given by the current state and the chosen actions. Player 1 wins iff a designated goal state is eventually visited. We are interested in the complexity of stationary strategies measured by their patience, which is defined as the inverse of the smallest non-zero probability employed. Our main results are as follows: We show that: (i) the optimal bound on the patience of optimal and epsilon-optimal strategies, for both players is doubly exponential; and (ii) even in games with a single non-absorbing state exponential (in the number of actions) patience is necessary.
Cite as

Krishnendu Chatterjee, Kristoffer Arnsfelt Hansen, and Rasmus Ibsen-Jensen. Strategy Complexity of Concurrent Safety Games. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 55:1-55:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{chatterjee_et_al:LIPIcs.MFCS.2017.55,
  author =	{Chatterjee, Krishnendu and Hansen, Kristoffer Arnsfelt and Ibsen-Jensen, Rasmus},
  title =	{{Strategy Complexity of Concurrent Safety Games}},
  booktitle =	{42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)},
  pages =	{55:1--55:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-046-0},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{83},
  editor =	{Larsen, Kim G. and Bodlaender, Hans L. and Raskin, Jean-Francois},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2017.55},
  URN =		{urn:nbn:de:0030-drops-81203},
  doi =		{10.4230/LIPIcs.MFCS.2017.55},
  annote =	{Keywords: Concurrent games, Reachability and safety, Patience of strategies}
}
Document
DOI: 10.4230/DagSemProc.08381.4
Depth Reduction for Circuits with a Single Layer of Modular Counting Gates

Authors: Kristoffer Arnsfelt Hansen

Published in: Dagstuhl Seminar Proceedings, Volume 8381, Computational Complexity of Discrete Problems (2008)

Abstract
We consider the class of constant depth AND/OR circuits augmented with a layer of modular counting gates at the bottom layer, i.e ${AC}^0 circ {MOD}_m$ circuits. We show that the following holds for several types of gates $G$: by adding a gate of type $G$ at the output, it is possible to obtain an equivalent randomized depth 2 circuit of quasipolynomial size consisting of a gate of type $G$ at the output and a layer of modular counting gates, i.e $G circ {MOD}_m$ circuits. The types of gates $G$ we consider are modular counting gates and threshold-style gates. For all of these, strong lower bounds are known for (deterministic) $G circ {MOD}_m$ circuits.
Cite as

Kristoffer Arnsfelt Hansen. Depth Reduction for Circuits with a Single Layer of Modular Counting Gates. In Computational Complexity of Discrete Problems. Dagstuhl Seminar Proceedings, Volume 8381, pp. 1-11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{hansen:DagSemProc.08381.4,
  author =	{Hansen, Kristoffer Arnsfelt},
  title =	{{Depth Reduction for Circuits with a Single Layer of Modular Counting Gates}},
  booktitle =	{Computational Complexity of Discrete Problems},
  pages =	{1--11},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8381},
  editor =	{Peter Bro Miltersen and R\"{u}diger Reischuk and Georg Schnitger and Dieter van Melkebeek},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.08381.4},
  URN =		{urn:nbn:de:0030-drops-17824},
  doi =		{10.4230/DagSemProc.08381.4},
  annote =	{Keywords: Boolean Circuits, Randomized Polynomials, Fourier sums}
}
  • Refine by Author
  • 5 Hansen, Kristoffer Arnsfelt
  • 1 Batziou, Eleni
  • 1 Chapman, Brynmor
  • 1 Chatterjee, Krishnendu
  • 1 Dan, Chen
  • Show More...

  • Refine by Classification
  • 2 Theory of computation → Problems, reductions and completeness
  • 1 Computing methodologies → Factorization methods
  • 1 Theory of computation → Approximation algorithms analysis
  • 1 Theory of computation → Circuit complexity
  • 1 Theory of computation → Complexity classes
  • Show More...

  • Refine by Keyword
  • 1 ACC
  • 1 Approximation Algorithms
  • 1 Binary Matrices
  • 1 Boolean Circuits
  • 1 Borsuk-Ulam
  • Show More...

  • Refine by Type
  • 6 document

  • Refine by Publication Year
  • 1 2008
  • 1 2017
  • 1 2018
  • 1 2020
  • 1 2021
  • 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