DNA assembly for nanopore data storage readout

Autor: Randolph Lopez, Yuan-Jyue Chen, Siena Dumas Ang, Sergey Yekhanin, Konstantin Makarychev, Miklos Z Racz, Georg Seelig, Karin Strauss, Luis Ceze

Publikováno v: Nature Communications, Vol 10, Iss 1, Pp 1-9 (2019)

A major bottleneck in using DNA as a data storage medium is the slowness of sequencing. Here the authors decode 1.67 megabytes of information using a portable nanopore platform with an assembly strategy for increased throughput.

Externí odkaz: https://doaj.org/article/e07599e4d5704cedbc045adf5c88720f

THE GROTHENDIECK CONSTANT IS STRICTLY SMALLER THAN KRIVINE’S BOUND

Autor: MARK BRAVERMAN, KONSTANTIN MAKARYCHEV, YURY MAKARYCHEV, ASSAF NAOR

Publikováno v: Forum of Mathematics, Pi, Vol 1 (2013)

The (real) Grothendieck constant ${K}_{G} $ is the infimum over those $K\in (0, \infty )$ such that for every $m, n\in \mathbb{N} $ and every $m\times n$ real matrix $({a}_{ij} )$ we have $$\begin{eqnarray*}\displaystyle \max _{\{ x_{i}\} _{i= 1}^{m}

Externí odkaz: https://doaj.org/article/5370349c5ba846f19f1dd03dbcc18316

Robust Algorithms with Polynomial Loss for Near-Unanimity CSPs

Autor: Jakub Opršal, Konstantin Makarychev, Víctor Dalmau, Yury Makarychev, Marcin Kozik, Andrei Krokhin

Publikováno v: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms
Scopus-Elsevier
(2017). Proceedings of the twenty-eighth Annual ACM-SIAM symposium on discrete algorithms. : SIAM, pp. 340-357

An instance of the Constraint Satisfaction Problem (CSP) is given by a family of constraints on overlapping sets of variables, and the goal is to assign values from a fixed domain to the variables so that all constraints are satisfied. In the optimiz

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::5080721e50ca6c5fef2500cbd4652e14
https://doi.org/10.1137/18m1163932

Maximizing Polynomials Subject to Assignment Constraints

Autor: Maxim Sviridenko, Konstantin Makarychev

Publikováno v: ACM Transactions on Algorithms. 13:1-15

We study the q -adic assignment problem. We first give an O ( n (q−1)/2) )-approximation algorithm for the Koopmans--Beckman version of the problem, improving upon the result of Barvinok. Then, we introduce a new family of instances satisfying “t

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_________::01bc5c332fa29344d392802c2b4b435a
https://doi.org/10.1145/3147137

Nonlinear dimension reduction via outer Bi-Lipschitz extensions

Autor: Yury Makarychev, Ilya Razenshteyn, Sepideh Mahabadi, Konstantin Makarychev

Publikováno v: STOC

We introduce and study the notion of an outer bi-Lipschitz extension of a map between Euclidean spaces. The notion is a natural analogue of the notion of a Lipschitz extension of a Lipschitz map. We show that for every map $f$ there exists an outer b

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::b84a74b7a0c4c606767bab7c50a91fc5
https://doi.org/10.1145/3188745.3188828