30 Search Results for "Seidel, Raimund"


Volume

OASIcs, Volume 61

1st Symposium on Simplicity in Algorithms (SOSA 2018)

SOSA 2018, January 7-10, 2018, New Orleans, LA, USA

Editors: Raimund Seidel

Document
RANDOM
Polynomial Identity Testing for Low Degree Polynomials with Optimal Randomness

Authors: Markus Bläser and Anurag Pandey

Published in: LIPIcs, Volume 176, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)


Abstract
We give a randomized polynomial time algorithm for polynomial identity testing for the class of n-variate poynomials of degree bounded by d over a field 𝔽, in the blackbox setting. Our algorithm works for every field 𝔽 with | 𝔽 | ≥ d+1, and uses only d log n + log (1/ ε) + O(d log log n) random bits to achieve a success probability 1 - ε for some ε > 0. In the low degree regime that is d ≪ n, it hits the information theoretic lower bound and differs from it only in the lower order terms. Previous best known algorithms achieve the number of random bits (Guruswami-Xing, CCC'14 and Bshouty, ITCS'14) that are constant factor away from our bound. Like Bshouty, we use Sidon sets for our algorithm. However, we use a new construction of Sidon sets to achieve the improved bound. We also collect two simple constructions of hitting sets with information theoretically optimal size against the class of n-variate, degree d polynomials. Our contribution is that we give new, very simple proofs for both the constructions.

Cite as

Markus Bläser and Anurag Pandey. Polynomial Identity Testing for Low Degree Polynomials with Optimal Randomness. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 8:1-8:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{blaser_et_al:LIPIcs.APPROX/RANDOM.2020.8,
  author =	{Bl\"{a}ser, Markus and Pandey, Anurag},
  title =	{{Polynomial Identity Testing for Low Degree Polynomials with Optimal Randomness}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)},
  pages =	{8:1--8:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-164-1},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{176},
  editor =	{Byrka, Jaros{\l}aw and Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2020.8},
  URN =		{urn:nbn:de:0030-drops-126112},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2020.8},
  annote =	{Keywords: Algebraic Complexity theory, Polynomial Identity Testing, Hitting Set, Pseudorandomness}
}
Document
Algebraic Branching Programs, Border Complexity, and Tangent Spaces

Authors: Markus Bläser, Christian Ikenmeyer, Meena Mahajan, Anurag Pandey, and Nitin Saurabh

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


Abstract
Nisan showed in 1991 that the width of a smallest noncommutative single-(source,sink) algebraic branching program (ABP) to compute a noncommutative polynomial is given by the ranks of specific matrices. This means that the set of noncommutative polynomials with ABP width complexity at most k is Zariski-closed, an important property in geometric complexity theory. It follows that approximations cannot help to reduce the required ABP width. It was mentioned by Forbes that this result would probably break when going from single-(source,sink) ABPs to trace ABPs. We prove that this is correct. Moreover, we study the commutative monotone setting and prove a result similar to Nisan, but concerning the analytic closure. We observe the same behavior here: The set of polynomials with ABP width complexity at most k is closed for single-(source,sink) ABPs and not closed for trace ABPs. The proofs reveal an intriguing connection between tangent spaces and the vector space of flows on the ABP. We close with additional observations on VQP and the closure of VNP which allows us to establish a separation between the two classes.

Cite as

Markus Bläser, Christian Ikenmeyer, Meena Mahajan, Anurag Pandey, and Nitin Saurabh. Algebraic Branching Programs, Border Complexity, and Tangent Spaces. In 35th Computational Complexity Conference (CCC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 169, pp. 21:1-21:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{blaser_et_al:LIPIcs.CCC.2020.21,
  author =	{Bl\"{a}ser, Markus and Ikenmeyer, Christian and Mahajan, Meena and Pandey, Anurag and Saurabh, Nitin},
  title =	{{Algebraic Branching Programs, Border Complexity, and Tangent Spaces}},
  booktitle =	{35th Computational Complexity Conference (CCC 2020)},
  pages =	{21:1--21:24},
  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.21},
  URN =		{urn:nbn:de:0030-drops-125733},
  doi =		{10.4230/LIPIcs.CCC.2020.21},
  annote =	{Keywords: Algebraic Branching Programs, Border Complexity, Tangent Spaces, Lower Bounds, Geometric Complexity Theory, Flows, VQP, VNP}
}
Document
A Unified Approach to Tail Estimates for Randomized Incremental Construction

Authors: Sandeep Sen

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


Abstract
By combining several interesting applications of random sampling in geometric algorithms like point location, linear programming, segment intersections, binary space partitioning, Clarkson and Shor [Kenneth L. Clarkson and Peter W. Shor, 1989] developed a general framework of randomized incremental construction (RIC ). The basic idea is to add objects in a random order and show that this approach yields efficient/optimal bounds on expected running time. Even quicksort can be viewed as a special case of this paradigm. However, unlike quicksort, for most of these problems, sharper tail estimates on their running times are not known. Barring some promising attempts in [Kurt Mehlhorn et al., 1993; Kenneth L. Clarkson et al., 1992; Raimund Seidel, 1991], the general question remains unresolved. In this paper we present a general technique to obtain tail estimates for RIC and and provide applications to some fundamental problems like Delaunay triangulations and construction of Visibility maps of intersecting line segments. The main result of the paper is derived from a new and careful application of Freedman’s [David Freedman, 1975] inequality for Martingale concentration that overcomes the bottleneck of the better known Azuma-Hoeffding inequality. Further, we explore instances, where an RIC based algorithm may not have inverse polynomial tail estimates. In particular, we show that the RIC time bounds for trapezoidal map can encounter a running time of Omega (n log n log log n) with probability exceeding 1/(sqrt{n)}. This rules out inverse polynomial concentration bounds within a constant factor of the O(n log n) expected running time.

Cite as

Sandeep Sen. A Unified Approach to Tail Estimates for Randomized Incremental Construction. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 58:1-58:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{sen:LIPIcs.STACS.2019.58,
  author =	{Sen, Sandeep},
  title =	{{A Unified Approach to Tail Estimates for Randomized Incremental Construction}},
  booktitle =	{36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)},
  pages =	{58:1--58: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.58},
  URN =		{urn:nbn:de:0030-drops-102977},
  doi =		{10.4230/LIPIcs.STACS.2019.58},
  annote =	{Keywords: ric, tail estimates, martingale, lower bound}
}
Document
Complete Volume
OASIcs, Volume 61, SOSA'18, Complete Volume

Authors: Raimund Seidel

Published in: OASIcs, Volume 61, 1st Symposium on Simplicity in Algorithms (SOSA 2018)


Abstract
OASIcs, Volume 61, SOSA'18, Complete Volume

Cite as

1st Symposium on Simplicity in Algorithms (SOSA 2018). Open Access Series in Informatics (OASIcs), Volume 61, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@Proceedings{seidel:OASIcs.SOSA.2018,
  title =	{{OASIcs, Volume 61, SOSA'18, Complete Volume}},
  booktitle =	{1st Symposium on Simplicity in Algorithms (SOSA 2018)},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-064-4},
  ISSN =	{2190-6807},
  year =	{2018},
  volume =	{61},
  editor =	{Seidel, Raimund},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.SOSA.2018},
  URN =		{urn:nbn:de:0030-drops-84405},
  doi =		{10.4230/OASIcs.SOSA.2018},
  annote =	{Keywords: Algorithm design and analysis}
}
Document
Front Matter
Front Matter, Table of Contents, Preface, Conference Organization

Authors: Raimund Seidel

Published in: OASIcs, Volume 61, 1st Symposium on Simplicity in Algorithms (SOSA 2018)


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

Cite as

1st Symposium on Simplicity in Algorithms (SOSA 2018). Open Access Series in Informatics (OASIcs), Volume 61, pp. 0:i-0:xii, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{seidel:OASIcs.SOSA.2018.0,
  author =	{Seidel, Raimund},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{1st Symposium on Simplicity in Algorithms (SOSA 2018)},
  pages =	{0:i--0:xii},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-064-4},
  ISSN =	{2190-6807},
  year =	{2018},
  volume =	{61},
  editor =	{Seidel, Raimund},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.SOSA.2018.0},
  URN =		{urn:nbn:de:0030-drops-82942},
  doi =		{10.4230/OASIcs.SOSA.2018.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
A Naive Algorithm for Feedback Vertex Set

Authors: Yixin Cao

Published in: OASIcs, Volume 61, 1st Symposium on Simplicity in Algorithms (SOSA 2018)


Abstract
Given a graph on n vertices and an integer k, the feedback vertex set problem asks for the deletion of at most k vertices to make the graph acyclic. We show that a greedy branching algorithm, which always branches on an undecided vertex with the largest degree, runs in single-exponential time, i.e., O(c^k n^2) for some constant c.

Cite as

Yixin Cao. A Naive Algorithm for Feedback Vertex Set. In 1st Symposium on Simplicity in Algorithms (SOSA 2018). Open Access Series in Informatics (OASIcs), Volume 61, pp. 1:1-1:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{cao:OASIcs.SOSA.2018.1,
  author =	{Cao, Yixin},
  title =	{{A Naive Algorithm for Feedback Vertex Set}},
  booktitle =	{1st Symposium on Simplicity in Algorithms (SOSA 2018)},
  pages =	{1:1--1:9},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-064-4},
  ISSN =	{2190-6807},
  year =	{2018},
  volume =	{61},
  editor =	{Seidel, Raimund},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.SOSA.2018.1},
  URN =		{urn:nbn:de:0030-drops-82961},
  doi =		{10.4230/OASIcs.SOSA.2018.1},
  annote =	{Keywords: greedy algorithm, analysis of algorithms, branching algorithm, parameterized computation -- graph modification problem}
}
Document
A Note on Iterated Rounding for the Survivable Network Design Problem

Authors: Chandra Chekuri and Thapanapong Rukkanchanunt

Published in: OASIcs, Volume 61, 1st Symposium on Simplicity in Algorithms (SOSA 2018)


Abstract
In this note we consider the survivable network design problem (SNDP) in undirected graphs. We make two contributions. The first is a new counting argument in the iterated rounding based 2-approximation for edge-connectivity SNDP (EC-SNDP) originally due to Jain. The second contribution is to make some connections between hypergraphic version of SNDP (Hypergraph-SNDP) introduced by Zhao, Nagamochi and Ibaraki, and edge and node-weighted versions of EC-SNDP and element-connectivity SNDP (Elem-SNDP). One useful consequence is a 2-approximation for Elem-SNDP that avoids the use of set-pair based relaxation and analysis.

Cite as

Chandra Chekuri and Thapanapong Rukkanchanunt. A Note on Iterated Rounding for the Survivable Network Design Problem. In 1st Symposium on Simplicity in Algorithms (SOSA 2018). Open Access Series in Informatics (OASIcs), Volume 61, pp. 2:1-2:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{chekuri_et_al:OASIcs.SOSA.2018.2,
  author =	{Chekuri, Chandra and Rukkanchanunt, Thapanapong},
  title =	{{A Note on Iterated Rounding for the Survivable Network Design Problem}},
  booktitle =	{1st Symposium on Simplicity in Algorithms (SOSA 2018)},
  pages =	{2:1--2:10},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-064-4},
  ISSN =	{2190-6807},
  year =	{2018},
  volume =	{61},
  editor =	{Seidel, Raimund},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.SOSA.2018.2},
  URN =		{urn:nbn:de:0030-drops-82976},
  doi =		{10.4230/OASIcs.SOSA.2018.2},
  annote =	{Keywords: survivable network design, iterated rounding, approximation, element connectivity}
}
Document
Congestion Minimization for Multipath Routing via Multiroute Flows

Authors: Chandra Chekuri and Mark Idleman

Published in: OASIcs, Volume 61, 1st Symposium on Simplicity in Algorithms (SOSA 2018)


Abstract
Congestion minimization is a well-known routing problem for which there is an O(log n/loglog n)-approximation via randomized rounding due to Raghavan and Thompson. Srinivasan formally introduced the low-congestion multi-path routing problem as a generalization of the (single-path) congestion minimization problem. The goal is to route multiple disjoint paths for each pair, for the sake of fault tolerance. Srinivasan developed a dependent randomized scheme for a special case of the multi-path problem when the input consists of a given set of disjoint paths for each pair and the goal is to select a given subset of them. Subsequently Doerr gave a different dependentrounding scheme and derandomization. Doerr et al. considered the problem where the paths have to be chosen, and applied the dependent rounding technique and evaluated it experimentally. However, their algorithm does not maintain the required disjointness property without which the problem easily reduces to the standard congestion minimization problem. In this note we show a simple algorithm that solves the problem correctly without the need for dependent rounding --- standard independent rounding suffices. This is made possible via the notion of multiroute flows originally suggested by Kishimoto et al. One advantage of the simpler rounding is an improved bound on the congestion when the path lengths are short.

Cite as

Chandra Chekuri and Mark Idleman. Congestion Minimization for Multipath Routing via Multiroute Flows. In 1st Symposium on Simplicity in Algorithms (SOSA 2018). Open Access Series in Informatics (OASIcs), Volume 61, pp. 3:1-3:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{chekuri_et_al:OASIcs.SOSA.2018.3,
  author =	{Chekuri, Chandra and Idleman, Mark},
  title =	{{Congestion Minimization for Multipath Routing via Multiroute Flows}},
  booktitle =	{1st Symposium on Simplicity in Algorithms (SOSA 2018)},
  pages =	{3:1--3:12},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-064-4},
  ISSN =	{2190-6807},
  year =	{2018},
  volume =	{61},
  editor =	{Seidel, Raimund},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.SOSA.2018.3},
  URN =		{urn:nbn:de:0030-drops-82984},
  doi =		{10.4230/OASIcs.SOSA.2018.3},
  annote =	{Keywords: multipath routing, congestion minimization, multiroute flows}
}
Document
Better and Simpler Error Analysis of the Sinkhorn-Knopp Algorithm for Matrix Scaling

Authors: Deeparnab Chakrabarty and Sanjeev Khanna

Published in: OASIcs, Volume 61, 1st Symposium on Simplicity in Algorithms (SOSA 2018)


Abstract
Given a non-negative real matrix A, the matrix scaling problem is to determine if it is possible to scale the rows and columns so that each row and each column sums to a specified target value for it. The matrix scaling problem arises in many algorithmic applications, perhaps most notably as a preconditioning step in solving linear system of equations. One of the most natural and by now classical approach to matrix scaling is the Sinkhorn-Knopp algorithm (also known as the RAS method) where one alternately scales either all rows or all columns to meet the target values. In addition to being extremely simple and natural, another appeal of this procedure is that it easily lends itself to parallelization. A central question is to understand the rate of convergence of the Sinkhorn-Knopp algorithm. Specifically, given a suitable error metric to measure deviations from target values, and an error bound epsilon, how quickly does the Sinkhorn-Knopp algorithm converge to an error below epsilon? While there are several non-trivial convergence results known about the Sinkhorn-Knopp algorithm, perhaps somewhat surprisingly, even for natural error metrics such as ell_1-error or ell_2-error, this is not entirely understood. In this paper, we present an elementary convergence analysis for the Sinkhorn-Knopp algorithm that improves upon the previous best bound. In a nutshell, our approach is to show (i) a simple bound on the number of iterations needed so that the KL-divergence between the current row-sums and the target row-sums drops below a specified threshold delta, and (ii) then show that for a suitable choice of delta, whenever KL-divergence is below delta, then the ell_1-error or the ell_2-error is below epsilon. The well-known Pinsker's inequality immediately allows us to translate a bound on the KL divergence to a bound on ell_1-error. To bound the ell_2-error in terms of the KL-divergence, we establish a new inequality, referred to as (KL vs ell_1/ell_2) inequality in the paper. This new inequality is a strengthening of the Pinsker's inequality that we believe is of independent interest. Our analysis of ell_2-error significantly improves upon the best previous convergence bound for ell_2-error. The idea of studying Sinkhorn-Knopp convergence via KL-divergence is not new and has indeed been previously explored. Our contribution is an elementary, self-contained presentation of this approach and an interesting new inequality that yields a significantly stronger convergence guarantee for the extensively studied ell_2-error.

Cite as

Deeparnab Chakrabarty and Sanjeev Khanna. Better and Simpler Error Analysis of the Sinkhorn-Knopp Algorithm for Matrix Scaling. In 1st Symposium on Simplicity in Algorithms (SOSA 2018). Open Access Series in Informatics (OASIcs), Volume 61, pp. 4:1-4:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{chakrabarty_et_al:OASIcs.SOSA.2018.4,
  author =	{Chakrabarty, Deeparnab and Khanna, Sanjeev},
  title =	{{Better and Simpler Error Analysis of the  Sinkhorn-Knopp Algorithm for Matrix Scaling}},
  booktitle =	{1st Symposium on Simplicity in Algorithms (SOSA 2018)},
  pages =	{4:1--4:11},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-064-4},
  ISSN =	{2190-6807},
  year =	{2018},
  volume =	{61},
  editor =	{Seidel, Raimund},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.SOSA.2018.4},
  URN =		{urn:nbn:de:0030-drops-83045},
  doi =		{10.4230/OASIcs.SOSA.2018.4},
  annote =	{Keywords: Matrix Scaling, Entropy Minimization, KL Divergence Inequalities}
}
Document
Approximation Schemes for 0-1 Knapsack

Authors: Timothy M. Chan

Published in: OASIcs, Volume 61, 1st Symposium on Simplicity in Algorithms (SOSA 2018)


Abstract
We revisit the standard 0-1 knapsack problem. The latest polynomial-time approximation scheme by Rhee (2015) with approximation factor 1+eps has running time near O(n+(1/eps)^{5/2}) (ignoring polylogarithmic factors), and is randomized. We present a simpler algorithm which achieves the same result and is deterministic. With more effort, our ideas can actually lead to an improved time bound near O(n + (1/eps)^{12/5}), and still further improvements for small n.

Cite as

Timothy M. Chan. Approximation Schemes for 0-1 Knapsack. In 1st Symposium on Simplicity in Algorithms (SOSA 2018). Open Access Series in Informatics (OASIcs), Volume 61, pp. 5:1-5:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{chan:OASIcs.SOSA.2018.5,
  author =	{Chan, Timothy M.},
  title =	{{Approximation Schemes for 0-1 Knapsack}},
  booktitle =	{1st Symposium on Simplicity in Algorithms (SOSA 2018)},
  pages =	{5:1--5:12},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-064-4},
  ISSN =	{2190-6807},
  year =	{2018},
  volume =	{61},
  editor =	{Seidel, Raimund},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.SOSA.2018.5},
  URN =		{urn:nbn:de:0030-drops-82994},
  doi =		{10.4230/OASIcs.SOSA.2018.5},
  annote =	{Keywords: knapsack problem, approximation algorithms, optimization, (min,+)-convolution}
}
Document
Counting Solutions to Polynomial Systems via Reductions

Authors: R. Ryan Williams

Published in: OASIcs, Volume 61, 1st Symposium on Simplicity in Algorithms (SOSA 2018)


Abstract
This paper provides both positive and negative results for counting solutions to systems of polynomial equations over a finite field. The general idea is to try to reduce the problem to counting solutions to a single polynomial, where the task is easier. In both cases, simple methods are utilized that we expect will have wider applicability (far beyond algebra). First, we give an efficient deterministic reduction from approximate counting for a system of (arbitrary) polynomial equations to approximate counting for one equation, over any finite field. We apply this reduction to give a deterministic poly(n,s,log p)/eps^2 time algorithm for approximately counting the fraction of solutions to a system of s quadratic n-variate polynomials over F_p (the finite field of prime order p) to within an additive eps factor, for any prime p. Note that uniform random sampling would already require Omega(s/eps^2) time, so our algorithm behaves as a full derandomization of uniform sampling. The approximate-counting algorithm yields efficient approximate counting for other well-known problems, such as 2-SAT, NAE-3SAT, and 3-Coloring. As a corollary, there is a deterministic algorithm (with analogous running time) for producing solutions to such systems which have at least eps p^n solutions. Second, we consider the difficulty of exactly counting solutions to a single polynomial of constant degree, over a finite field. (Note that finding a solution in this case is easy.) It has been known for over 20 years that this counting problem is already NP-hard for degree-three polynomials over F_2; however, all known reductions increased the number of variables by a considerable amount. We give a subexponential-time reduction from counting solutions to k-CNF formulas to counting solutions to a degree-k^{O(k)} polynomial (over any finite field of O(1) order) which exactly preserves the number of variables. As a corollary, the Strong Exponential Time Hypothesis (even its weak counting variant #SETH) implies that counting solutions to constant-degree polynomials (even over F_2) requires essentially 2^n time. Similar results hold for counting orthogonal pairs of vectors over F_p.

Cite as

R. Ryan Williams. Counting Solutions to Polynomial Systems via Reductions. In 1st Symposium on Simplicity in Algorithms (SOSA 2018). Open Access Series in Informatics (OASIcs), Volume 61, pp. 6:1-6:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{williams:OASIcs.SOSA.2018.6,
  author =	{Williams, R. Ryan},
  title =	{{Counting Solutions to Polynomial Systems via Reductions}},
  booktitle =	{1st Symposium on Simplicity in Algorithms (SOSA 2018)},
  pages =	{6:1--6:15},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-064-4},
  ISSN =	{2190-6807},
  year =	{2018},
  volume =	{61},
  editor =	{Seidel, Raimund},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.SOSA.2018.6},
  URN =		{urn:nbn:de:0030-drops-83078},
  doi =		{10.4230/OASIcs.SOSA.2018.6},
  annote =	{Keywords: counting complexity, polynomial equations, finite field, derandomization, strong exponential time hypothesis}
}
Document
On Sampling Edges Almost Uniformly

Authors: Talya Eden and Will Rosenbaum

Published in: OASIcs, Volume 61, 1st Symposium on Simplicity in Algorithms (SOSA 2018)


Abstract
We consider the problem of sampling an edge almost uniformly from an unknown graph, G = (V, E). Access to the graph is provided via queries of the following types: (1) uniform vertex queries, (2) degree queries, and (3) neighbor queries. We describe a new simple algorithm that returns a random edge e in E using \tilde{O}(n/sqrt{eps m}) queries in expectation, such that each edge e is sampled with probability (1 +/- eps)/m. Here, n = |V| is the number of vertices, and m = |E| is the number of edges. Our algorithm is optimal in the sense that any algorithm that samples an edge from an almost-uniform distribution must perform Omega(n/sqrt{m}) queries.

Cite as

Talya Eden and Will Rosenbaum. On Sampling Edges Almost Uniformly. In 1st Symposium on Simplicity in Algorithms (SOSA 2018). Open Access Series in Informatics (OASIcs), Volume 61, pp. 7:1-7:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{eden_et_al:OASIcs.SOSA.2018.7,
  author =	{Eden, Talya and Rosenbaum, Will},
  title =	{{On Sampling Edges Almost Uniformly}},
  booktitle =	{1st Symposium on Simplicity in Algorithms (SOSA 2018)},
  pages =	{7:1--7:9},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-064-4},
  ISSN =	{2190-6807},
  year =	{2018},
  volume =	{61},
  editor =	{Seidel, Raimund},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.SOSA.2018.7},
  URN =		{urn:nbn:de:0030-drops-83001},
  doi =		{10.4230/OASIcs.SOSA.2018.7},
  annote =	{Keywords: Sublinear Algorithms, Graph Algorithms, Sampling Edges, Query Complexity}
}
Document
A Simple PTAS for the Dual Bin Packing Problem and Advice Complexity of Its Online Version

Authors: Allan Borodin, Denis Pankratov, and Amirali Salehi-Abari

Published in: OASIcs, Volume 61, 1st Symposium on Simplicity in Algorithms (SOSA 2018)


Abstract
Recently, Renault (2016) studied the dual bin packing problem in the per-request advice model of online algorithms. He showed that given O(1/eps) advice bits for each input item allows approximating the dual bin packing problem online to within a factor of 1+\eps. Renault asked about the advice complexity of dual bin packing in the tape-advice model of online algorithms. We make progress on this question. Let s be the maximum bit size of an input item weight. We present a conceptually simple online algorithm that with total advice O((s + log n)/eps^2) approximates the dual bin packing to within a 1+eps factor. To this end, we describe and analyze a simple offline PTAS for the dual bin packing problem. Although a PTAS for a more general problem was known prior to our work (Kellerer 1999, Chekuri and Khanna 2006), our PTAS is arguably simpler to state and analyze. As a result, we could easily adapt our PTAS to obtain the advice-complexity result. We also consider whether the dependence on s is necessary in our algorithm. We show that if s is unrestricted then for small enough eps > 0 obtaining a 1+eps approximation to the dual bin packing requires Omega_eps(n) bits of advice. To establish this lower bound we analyze an online reduction that preserves the advice complexity and approximation ratio from the binary separation problem due to Boyar et al. (2016). We define two natural advice complexity classes that capture the distinction similar to the Turing machine world distinction between pseudo polynomial time algorithms and polynomial time algorithms. Our results on the dual bin packing problem imply the separation of the two classes in the advice complexity world.

Cite as

Allan Borodin, Denis Pankratov, and Amirali Salehi-Abari. A Simple PTAS for the Dual Bin Packing Problem and Advice Complexity of Its Online Version. In 1st Symposium on Simplicity in Algorithms (SOSA 2018). Open Access Series in Informatics (OASIcs), Volume 61, pp. 8:1-8:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{borodin_et_al:OASIcs.SOSA.2018.8,
  author =	{Borodin, Allan and Pankratov, Denis and Salehi-Abari, Amirali},
  title =	{{A Simple PTAS for the Dual Bin Packing Problem and Advice Complexity of Its Online Version}},
  booktitle =	{1st Symposium on Simplicity in Algorithms (SOSA 2018)},
  pages =	{8:1--8:12},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-064-4},
  ISSN =	{2190-6807},
  year =	{2018},
  volume =	{61},
  editor =	{Seidel, Raimund},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.SOSA.2018.8},
  URN =		{urn:nbn:de:0030-drops-83033},
  doi =		{10.4230/OASIcs.SOSA.2018.8},
  annote =	{Keywords: dual bin packing, PTAS, tape-advice complexity}
}
Document
Simple and Efficient Leader Election

Authors: Petra Berenbrink, Dominik Kaaser, Peter Kling, and Lena Otterbach

Published in: OASIcs, Volume 61, 1st Symposium on Simplicity in Algorithms (SOSA 2018)


Abstract
We provide a simple and efficient population protocol for leader election that uses O(log n) states and elects exactly one leader in O(n (log n)^2) interactions with high probability and in expectation. Our analysis is simple and based on fundamental stochastic arguments. Our protocol combines the tournament based leader elimination by Alistarh and Gelashvili, ICALP'15, with the synthetic coin introduced by Alistarh et al., SODA'17.

Cite as

Petra Berenbrink, Dominik Kaaser, Peter Kling, and Lena Otterbach. Simple and Efficient Leader Election. In 1st Symposium on Simplicity in Algorithms (SOSA 2018). Open Access Series in Informatics (OASIcs), Volume 61, pp. 9:1-9:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{berenbrink_et_al:OASIcs.SOSA.2018.9,
  author =	{Berenbrink, Petra and Kaaser, Dominik and Kling, Peter and Otterbach, Lena},
  title =	{{Simple and Efficient Leader Election}},
  booktitle =	{1st Symposium on Simplicity in Algorithms (SOSA 2018)},
  pages =	{9:1--9:11},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-064-4},
  ISSN =	{2190-6807},
  year =	{2018},
  volume =	{61},
  editor =	{Seidel, Raimund},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.SOSA.2018.9},
  URN =		{urn:nbn:de:0030-drops-83029},
  doi =		{10.4230/OASIcs.SOSA.2018.9},
  annote =	{Keywords: population protocols, leader election, distributed, randomized}
}
  • Refine by Author
  • 7 Seidel, Raimund
  • 2 Arge, Lars
  • 2 Bläser, Markus
  • 2 Chekuri, Chandra
  • 2 Klein, Rolf
  • Show More...

  • Refine by Classification
  • 2 Theory of computation → Algebraic complexity theory
  • 1 Theory of computation → Complexity classes
  • 1 Theory of computation → Computational geometry

  • Refine by Keyword
  • 3 Data structures
  • 3 algorithms
  • 2 complexity
  • 2 information retrieval
  • 1 (min,+)-convolution
  • Show More...

  • Refine by Type
  • 29 document
  • 1 volume

  • Refine by Publication Year
  • 18 2018
  • 4 2008
  • 2 2010
  • 2 2020
  • 1 1995
  • 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