Zobrazeno 1 - 10
of 30
pro vyhledávání: '"Yodpinyanee, Anak"'
Autor:
Yodpinyanee, Anak
Thesis: Ph. D., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2018.
Cataloged from PDF version of thesis.
Includes bibliographical references (pages 189-199).
In the face of massive d
Cataloged from PDF version of thesis.
Includes bibliographical references (pages 189-199).
In the face of massive d
Externí odkaz:
http://hdl.handle.net/1721.1/120411
In this work, we consider the sample complexity required for testing the monotonicity of distributions over partial orders. A distribution $p$ over a poset is monotone if, for any pair of domain elements $x$ and $y$ such that $x \preceq y$, $p(x) \le
Externí odkaz:
http://arxiv.org/abs/1907.03182
A graph spanner is a fundamental graph structure that faithfully preserves the pairwise distances in the input graph up to a small multiplicative stretch. The common objective in the computation of spanners is to achieve the best-known existential si
Externí odkaz:
http://arxiv.org/abs/1902.08266
We study the classic set cover problem from the perspective of sub-linear algorithms. Given access to a collection of $m$ sets over $n$ elements in the query model, we show that sub-linear algorithms derived from existing techniques have almost tight
Externí odkaz:
http://arxiv.org/abs/1902.03534
Consider an algorithm performing a computation on a huge random object. Is it necessary to generate the entire object up front, or is it possible to provide query access to the object and sample it incrementally "on-the-fly"? Such an implementation s
Externí odkaz:
http://arxiv.org/abs/1711.10692
Autor:
Yodpinyanee, Anak
Thesis: S.M., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2014.
Cataloged from PDF version of thesis.
Includes bibliographical references (pages 41-44).
In the model of local comput
Cataloged from PDF version of thesis.
Includes bibliographical references (pages 41-44).
In the model of local comput
Externí odkaz:
http://hdl.handle.net/1721.1/93050
Autor:
Bosboom, Jeffrey, Demaine, Erik D., Demaine, Martin L., Hesterberg, Adam, Manurangsi, Pasin, Yodpinyanee, Anak
We prove the computational intractability of rotating and placing $n$ square tiles into a $1 \times n$ array such that adjacent tiles are compatible--either equal edge colors, as in edge-matching puzzles, or matching tab/pocket shapes, as in jigsaw p
Externí odkaz:
http://arxiv.org/abs/1701.00146
Autor:
Aliakbarpour, Maryam, Biswas, Amartya Shankha, Gouleakis, Themistoklis, Peebles, John, Rubinfeld, Ronitt, Yodpinyanee, Anak
We study the problem of estimating the value of sums of the form $S_p \triangleq \sum \binom{x_i}{p}$ when one has the ability to sample $x_i \geq 0$ with probability proportional to its magnitude. When $p=2$, this problem is equivalent to estimating
Externí odkaz:
http://arxiv.org/abs/1601.04233
Autor:
Bosboom, Jeffrey, Demaine, Erik D., Demaine, Martin L., Lynch, Jayson, Manurangsi, Pasin, Rudoy, Mikhail, Yodpinyanee, Anak
We prove that it is NP-hard to dissect one simple orthogonal polygon into another using a given number of pieces, as is approximating the fewest pieces to within a factor of $1+1/1080-\varepsilon$.
Comment: 18 pages, 9 figures
Comment: 18 pages, 9 figures
Externí odkaz:
http://arxiv.org/abs/1512.06706
In the model of \emph{local computation algorithms} (LCAs), we aim to compute the queried part of the output by examining only a small (sublinear) portion of the input. Many recently developed LCAs on graph problems achieve time and space complexitie
Externí odkaz:
http://arxiv.org/abs/1502.04022