6 Search Results for "Xie, Min"


Document
Track A: Algorithms, Complexity and Games
Faster Knapsack Algorithms via Bounded Monotone Min-Plus-Convolution

Authors: Karl Bringmann and Alejandro Cassis

Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)


Abstract
We present new exact and approximation algorithms for 0-1-Knapsack and Unbounded Knapsack: - Exact Algorithm for 0-1-Knapsack: 0-1-Knapsack has known algorithms running in time Õ(n + min{n ⋅ OPT, n ⋅ W, OPT², W²}) [Bellman '57], where n is the number of items, W is the weight budget, and OPT is the optimal profit. We present an algorithm running in time Õ(n + (W + OPT)^{1.5}). This improves the running time in case n,W,OPT are roughly equal. - Exact Algorithm for Unbounded Knapsack: Unbounded Knapsack has known algorithms running in time Õ(n + min{n ⋅ p_max, n ⋅ w_max, p_max², w_max²}) [Axiotis, Tzamos '19, Jansen, Rohwedder '19, Chan, He '22], where n is the number of items, w_{max} is the largest weight of any item, and p_max is the largest profit of any item. We present an algorithm running in time Õ(n + (p_max + w_max)^{1.5}), giving a similar improvement as for 0-1-Knapsack. - Approximating Unbounded Knapsack with Resource Augmentation: Unbounded Knapsack has a known FPTAS with running time Õ(min{n/ε, n + 1/ε²}) [Jansen, Kraft '18]. We study weak approximation algorithms, which approximate the optimal profit but are allowed to overshoot the weight constraint (i.e. resource augmentation). We present the first approximation scheme for Unbounded Knapsack in this setting, achieving running time Õ(n + 1/ε^{1.5}). Along the way, we also give a simpler FPTAS with lower order improvement in the standard setting. For all of these problem settings the previously known results had matching conditional lower bounds. We avoid these lower bounds in the approximation setting by allowing resource augmentation, and in the exact setting by analyzing the time complexity in terms of weight and profit parameters (instead of only weight or only profit parameters). Our algorithms can be seen as reductions to Min-Plus-Convolution on monotone sequences with bounded entries. These structured instances of Min-Plus-Convolution can be solved in time O(n^1.5) [Chi, Duan, Xie, Zhang '22] (in contrast to the conjectured n^{2-o(1)} lower bound for the general case). We complement our results by showing reductions in the opposite direction, that is, we show that achieving our results with the constant 1.5 replaced by any constant < 2 implies subquadratic algorithms for Min-Plus-Convolution on monotone sequences with bounded entries.

Cite as

Karl Bringmann and Alejandro Cassis. Faster Knapsack Algorithms via Bounded Monotone Min-Plus-Convolution. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 31:1-31:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{bringmann_et_al:LIPIcs.ICALP.2022.31,
  author =	{Bringmann, Karl and Cassis, Alejandro},
  title =	{{Faster Knapsack Algorithms via Bounded Monotone Min-Plus-Convolution}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{31:1--31:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-235-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{229},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.31},
  URN =		{urn:nbn:de:0030-drops-163727},
  doi =		{10.4230/LIPIcs.ICALP.2022.31},
  annote =	{Keywords: Knapsack, Approximation Schemes, Fine-Grained Complexity, Min-Plus Convolution}
}
Document
Online Linear Extractors for Independent Sources

Authors: Yevgeniy Dodis, Siyao Guo, Noah Stephens-Davidowitz, and Zhiye Xie

Published in: LIPIcs, Volume 199, 2nd Conference on Information-Theoretic Cryptography (ITC 2021)


Abstract
In this work, we characterize linear online extractors. In other words, given a matrix A ∈ F₂^{n×n}, we study the convergence of the iterated process S ← AS⊕X, where X∼D is repeatedly sampled independently from some fixed (but unknown) distribution D with (min)-entropy k. Here, we think of S ∈ {0,1}ⁿ as the state of an online extractor, and X ∈ {0,1}ⁿ as its input. As our main result, we show that the state S converges to the uniform distribution for all input distributions D with entropy k > 0 if and only if the matrix A has no non-trivial invariant subspace (i.e., a non-zero subspace V ⊊ F₂ⁿ such that AV ⊆ V). In other words, a matrix A yields a linear online extractor if and only if A has no non-trivial invariant subspace. For example, the linear transformation corresponding to multiplication by a generator of the field F_{2ⁿ} yields a good linear online extractor. Furthermore, for any such matrix convergence takes at most Õ(n²(k+1)/k²) steps. We also study the more general notion of condensing - that is, we ask when this process converges to a distribution with entropy at least l, when the input distribution has entropy at least k. (Extractors corresponding to the special case when l = n.) We show that a matrix gives a good condenser if there are relatively few vectors w ∈ F₂ⁿ such that w, A^Tw, …, (A^T)^{n-k}w are linearly dependent. As an application, we show that the very simple cyclic rotation transformation A(x₁,…, x_n) = (x_n,x₁,…, x_{n-1}) condenses to l = n-1 bits for any k > 1 if n is a prime satisfying a certain simple number-theoretic condition. Our proofs are Fourier-analytic and rely on a novel lemma, which gives a tight bound on the product of certain Fourier coefficients of any entropic distribution.

Cite as

Yevgeniy Dodis, Siyao Guo, Noah Stephens-Davidowitz, and Zhiye Xie. Online Linear Extractors for Independent Sources. In 2nd Conference on Information-Theoretic Cryptography (ITC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 199, pp. 14:1-14:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{dodis_et_al:LIPIcs.ITC.2021.14,
  author =	{Dodis, Yevgeniy and Guo, Siyao and Stephens-Davidowitz, Noah and Xie, Zhiye},
  title =	{{Online Linear Extractors for Independent Sources}},
  booktitle =	{2nd Conference on Information-Theoretic Cryptography (ITC 2021)},
  pages =	{14:1--14:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-197-9},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{199},
  editor =	{Tessaro, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2021.14},
  URN =		{urn:nbn:de:0030-drops-143339},
  doi =		{10.4230/LIPIcs.ITC.2021.14},
  annote =	{Keywords: feasibility of randomness extraction, randomness condensers, Fourier analysis}
}
Document
Single-Source Bottleneck Path Algorithm Faster than Sorting for Sparse Graphs

Authors: Ran Duan, Kaifeng Lyu, and Yuanhang Xie

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)


Abstract
In a directed graph G=(V,E) with a capacity on every edge, a bottleneck path (or widest path) between two vertices is a path maximizing the minimum capacity of edges in the path. For the single-source all-destination version of this problem in directed graphs, the previous best algorithm runs in O(m+n log n) (m=|E| and n=|V|) time, by Dijkstra search with Fibonacci heap [Fredman and Tarjan 1987]. We improve this time bound to O(m sqrt{log n}+sqrt{mn log n log log n}), which is O(n sqrt{log n log log n}) when m=O(n), thus it is the first algorithm which breaks the time bound of classic Fibonacci heap when m=o(n sqrt{log n}). It is a Las-Vegas randomized approach. By contrast, the s-t bottleneck path has algorithm with running time O(m beta(m,n)) [Chechik et al. 2016], where beta(m,n)=min{k >= 1: log^{(k)}n <= m/n}.

Cite as

Ran Duan, Kaifeng Lyu, and Yuanhang Xie. Single-Source Bottleneck Path Algorithm Faster than Sorting for Sparse Graphs. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 43:1-43:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{duan_et_al:LIPIcs.ICALP.2018.43,
  author =	{Duan, Ran and Lyu, Kaifeng and Xie, Yuanhang},
  title =	{{Single-Source Bottleneck Path Algorithm Faster than Sorting for Sparse Graphs}},
  booktitle =	{45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
  pages =	{43:1--43:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.43},
  URN =		{urn:nbn:de:0030-drops-90475},
  doi =		{10.4230/LIPIcs.ICALP.2018.43},
  annote =	{Keywords: Graph Algorithm, Bottleneck Path, Combinatorial Optimization}
}
Document
QoE Vadis? (Dagstuhl Perspectives Workshop 16472)

Authors: Markus Fiedler, Sebastian Möller, Peter Reichl, and Min Xie

Published in: Dagstuhl Manifestos, Volume 7, Issue 1 (2018)


Abstract
The goal of the Dagstuhl Perspectives Workshop 16472 has been to discuss and outline the strategic evolution of Quality of Experience as a key topic for future Internet research. The resulting manifesto, which is presented here, reviews the state of the art in the Quality of Experience (QoE) domain, along with a SWOT analysis. Based on those, it discusses how the QoE research area might develop in the future, and how QoE research will lead to innovative and improved products and services. It closes by providing a set of recommendations for the scientific community and industry, as well as for future funding of QoE-related activities.

Cite as

Markus Fiedler, Sebastian Möller, Peter Reichl, and Min Xie. QoE Vadis? (Dagstuhl Perspectives Workshop 16472). In Dagstuhl Manifestos, Volume 7, Issue 1, pp. 30-51, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@Article{fiedler_et_al:DagMan.7.1.30,
  author =	{Fiedler, Markus and M\"{o}ller, Sebastian and Reichl, Peter and Xie, Min},
  title =	{{QoE Vadis? (Dagstuhl Perspectives Workshop 16472)}},
  pages =	{30--51},
  journal =	{Dagstuhl Manifestos},
  ISSN =	{2193-2433},
  year =	{2018},
  volume =	{7},
  number =	{1},
  editor =	{Fiedler, Markus and M\"{o}ller, Sebastian and Reichl, Peter and Xie, Min},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagMan.7.1.30},
  URN =		{urn:nbn:de:0030-drops-86830},
  doi =		{10.4230/DagMan.7.1.30},
  annote =	{Keywords: multimedia, network and application management, network quality monitoring and measurement, quality of experience, socio-economic and business aspects}
}
Document
QoE Vadis? (Dagstuhl Perspectives Workshop 16472)

Authors: Markus Fiedler, Sebastian Möller, Peter Reichl, and Min Xie

Published in: Dagstuhl Reports, Volume 6, Issue 11 (2017)


Abstract
This report documents the program and the outcomes of Dagstuhl Perspectives Workshop 16472 "QoE Vadis?", which was preceded by the three Dagstuhl Seminars 09192 "From Quality of Service to Quality of Experience" (2009), 12181 "Quality of Experience: From User Perception to Instrumental Metrics" (2012), and 15022 "Quality of Experience: From Assessment to Application" (2015). As suggested by the name, the Perspectives Workshop set out to jointly and critically reflect on future perspectives and directions of Quality of Experience (QoE) research. This report reflects upon the organization of the workshop. It also provides a set of personal statements and feedbacks (through the innovative "Advocatus Diaboli" approach), as well as a marriage proposal with the area of User Experience (UX). Finally, an overview of the recommendations in the upcoming Dagstuhl Manifesto is given.

Cite as

Markus Fiedler, Sebastian Möller, Peter Reichl, and Min Xie. QoE Vadis? (Dagstuhl Perspectives Workshop 16472). In Dagstuhl Reports, Volume 6, Issue 11, pp. 129-141, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)


Copy BibTex To Clipboard

@Article{fiedler_et_al:DagRep.6.11.129,
  author =	{Fiedler, Markus and M\"{o}ller, Sebastian and Reichl, Peter and Xie, Min},
  title =	{{QoE Vadis? (Dagstuhl Perspectives Workshop 16472)}},
  pages =	{129--141},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2017},
  volume =	{6},
  number =	{11},
  editor =	{Fiedler, Markus and M\"{o}ller, Sebastian and Reichl, Peter and Xie, Min},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.6.11.129},
  URN =		{urn:nbn:de:0030-drops-71056},
  doi =		{10.4230/DagRep.6.11.129},
  annote =	{Keywords: multimedia, network and application management, network quality monitoring and measurement, quality of experience, socio-economic and business aspects user experience}
}
Document
Breaking the $\epsilon$-Soundness Bound of the Linearity Test over GF(2)

Authors: Tali Kaufman, Simon Litsyn, and Ning Xie

Published in: Dagstuhl Seminar Proceedings, Volume 8341, Sublinear Algorithms (2008)


Abstract
For Boolean functions that are $epsilon$-far from the set of linear functions, we study the lower bound on the rejection probability (denoted by $extsc{rej}(epsilon)$) of the linearity test suggested by Blum, Luby and Rubinfeld. This problem is arguably the most fundamental and extensively studied problem in property testing of Boolean functions. The previously best bounds for $extsc{rej}(epsilon)$ were obtained by Bellare, Coppersmith, H{{a}}stad, Kiwi and Sudan. They used Fourier analysis to show that $ extsc{rej}(epsilon) geq e$ for every $0 leq epsilon leq frac{1}{2}$. They also conjectured that this bound might not be tight for $epsilon$'s which are close to $1/2$. In this paper we show that this indeed is the case. Specifically, we improve the lower bound of $ extsc{rej}(epsilon) geq epsilon$ by an additive constant that depends only on $epsilon$: $extsc{rej}(epsilon) geq epsilon + min {1376epsilon^{3}(1-2epsilon)^{12}, frac{1}{4}epsilon(1-2epsilon)^{4}}$, for every $0 leq epsilon leq frac{1}{2}$. Our analysis is based on a relationship between $extsc{rej}(epsilon)$ and the weight distribution of a coset of the Hadamard code. We use both Fourier analysis and coding theory tools to estimate this weight distribution.

Cite as

Tali Kaufman, Simon Litsyn, and Ning Xie. Breaking the $\epsilon$-Soundness Bound of the Linearity Test over GF(2). In Sublinear Algorithms. Dagstuhl Seminar Proceedings, Volume 8341, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)


Copy BibTex To Clipboard

@InProceedings{kaufman_et_al:DagSemProc.08341.3,
  author =	{Kaufman, Tali and Litsyn, Simon and Xie, Ning},
  title =	{{Breaking the \$\backslashepsilon\$-Soundness Bound of the Linearity Test over GF(2)}},
  booktitle =	{Sublinear Algorithms},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8341},
  editor =	{Artur Czumaj and S. Muthu Muthukrishnan and Ronitt Rubinfeld and Christian Sohler},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.08341.3},
  URN =		{urn:nbn:de:0030-drops-16971},
  doi =		{10.4230/DagSemProc.08341.3},
  annote =	{Keywords: Linearity test, Fourier analysis, coding theory}
}
  • Refine by Author
  • 2 Fiedler, Markus
  • 2 Möller, Sebastian
  • 2 Reichl, Peter
  • 2 Xie, Min
  • 1 Bringmann, Karl
  • Show More...

  • Refine by Classification
  • 2 Theory of computation → Design and analysis of algorithms
  • 1 Mathematics of computing → Information theory
  • 1 Theory of computation → Expander graphs and randomness extractors

  • Refine by Keyword
  • 2 Fourier analysis
  • 2 multimedia
  • 2 network and application management
  • 2 network quality monitoring and measurement
  • 2 quality of experience
  • Show More...

  • Refine by Type
  • 6 document

  • Refine by Publication Year
  • 2 2018
  • 1 2008
  • 1 2017
  • 1 2021
  • 1 2022

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