5 Search Results for "Ceze, Luis"

Document
DOI: 10.4230/LIPIcs.ESA.2025.111
Hardness of Median and Center in the Ulam Metric

Authors: Nick Fischer, Elazar Goldenberg, Mursalin Habib, and Karthik C. S.

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
The classical rank aggregation problem seeks to combine a set X of n permutations into a single representative "consensus" permutation. In this paper, we investigate two fundamental rank aggregation tasks under the well-studied Ulam metric: computing a median permutation (which minimizes the sum of Ulam distances to X) and computing a center permutation (which minimizes the maximum Ulam distance to X) in two settings. - Continuous Setting: In the continuous setting, the median/center is allowed to be any permutation. It is known that computing a center in the Ulam metric is NP-hard and we add to this by showing that computing a median is NP-hard as well via a simple reduction from the Max-Cut problem. While this result may not be unexpected, it had remained elusive until now and confirms a speculation by Chakraborty, Das, and Krauthgamer [SODA '21]. - Discrete Setting: In the discrete setting, the median/center must be a permutation from the input set. We fully resolve the fine-grained complexity of the discrete median and discrete center problems under the Ulam metric, proving that the naive Õ(n² L)-time algorithm (where L is the length of the permutation) is conditionally optimal. This resolves an open problem raised by Abboud, Bateni, Cohen-Addad, Karthik C. S., and Seddighin [APPROX '23]. Our reductions are inspired by the known fine-grained lower bounds for similarity measures, but we face and overcome several new highly technical challenges.
Cite as

Nick Fischer, Elazar Goldenberg, Mursalin Habib, and Karthik C. S.. Hardness of Median and Center in the Ulam Metric. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 111:1-111:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{fischer_et_al:LIPIcs.ESA.2025.111,
  author =	{Fischer, Nick and Goldenberg, Elazar and Habib, Mursalin and Karthik C. S.},
  title =	{{Hardness of Median and Center in the Ulam Metric}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{111:1--111:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.111},
  URN =		{urn:nbn:de:0030-drops-245809},
  doi =		{10.4230/LIPIcs.ESA.2025.111},
  annote =	{Keywords: Ulam distance, median, center, rank aggregation, fine-grained complexity}
}
Document
DOI: 10.4230/LIPIcs.DNA.31.11
Leakless Polymerase-Dependent Strand Displacement Systems

Authors: Zoë Evelyn Mōhalakealoha Derauf and Chris Thachuk

Published in: LIPIcs, Volume 347, 31st International Conference on DNA Computing and Molecular Programming (DNA 31) (2025)

Abstract
A grand challenge facing molecular programmers is the rational development of fast, robust, and isothermal architectures akin to "chemical central processing units" that can sense (bio-)chemical signals from their environment, perform complex computation, and orchestrate a physical response in situ. DNA strand displacement systems (DSDs) remain a compelling candidate, but are hampered by spurious reaction pathways that lead to incorrect output. DSDs that utilize the systematic leakless motif can be made arbitrarily robust at the cost of increasing redundancy and network size (scaling), and thus a degradation of kinetic performance. Another class of architectures utilize DNA hybridization, extension, and signal production of entirely sequestered outputs via strand-displacing polymerases (SDPs) that have resulted in impressive demonstrations; however, they face similar challenges of aberrant behavior such as mis-priming by incorrect signals. Our work introduces a unified polymerase-dependent toehold-mediated strand displacement (PD-TMSD) architecture that integrates the programmed specificity of DSDs with the unique advantages of SDPs. This unification enables systems that can be made arbitrarily robust, at any concentration range, without increasing network size. We propose a number of gate designs and composition rules to compute arbitrary Boolean functions, emulate arbitrary chemical reaction networks, and explore time-bounded probabilistic computation made possible by certain classes of SDPs. Our theoretical exploration is backed by preliminary experimental demonstrations. This contribution was inspired by the belief that molecular programming can meet or exceed the complexity exhibited in biology if we embrace its best understood molecular machinery and couple it with systematic design principles built upon a strong theoretical foundation.
Cite as

Zoë Evelyn Mōhalakealoha Derauf and Chris Thachuk. Leakless Polymerase-Dependent Strand Displacement Systems. In 31st International Conference on DNA Computing and Molecular Programming (DNA 31). Leibniz International Proceedings in Informatics (LIPIcs), Volume 347, pp. 11:1-11:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{derauf_et_al:LIPIcs.DNA.31.11,
  author =	{Derauf, Zo\"{e} Evelyn M\={o}halakealoha and Thachuk, Chris},
  title =	{{Leakless Polymerase-Dependent Strand Displacement Systems}},
  booktitle =	{31st International Conference on DNA Computing and Molecular Programming (DNA 31)},
  pages =	{11:1--11:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-399-7},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{347},
  editor =	{Schaeffer, Josie and Zhang, Fei},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DNA.31.11},
  URN =		{urn:nbn:de:0030-drops-238608},
  doi =		{10.4230/LIPIcs.DNA.31.11},
  annote =	{Keywords: DNA strand displacement, strand-displacing polymerases, molecular computation, energy barriers, kinetics}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2024.22
FaaSLoad: Fine-Grained Performance and Resource Measurement for Function-As-a-Service

Authors: Mathieu Bacou

Published in: LIPIcs, Volume 324, 28th International Conference on Principles of Distributed Systems (OPODIS 2024)

Abstract
Cloud computing relies on a deep stack of system layers: virtual machine, operating system, distributed middleware and language runtime. However, those numerous, distributed, virtual layers prevent any low-level understanding of the properties of FaaS applications, considered as programs running on real hardware. As a result, most research analyses only consider coarse-grained properties such as global performance of an application, and existing datasets include only sparse data. FaaSLoad is a tool to gather fine-grained data about performance and resource usage of the programs that run on Function-as-a-Service cloud platforms. It considers individual instances of functions to collect hardware and operating-system performance information, by monitoring them while injecting a workload. FaaSLoad helps building a dataset of function executions to train machine learning models, studying at fine grain the behavior of function runtimes, and replaying real workload traces for in situ observations. This research software project aims at being useful to cloud system researchers with features such as guaranteeing reproducibility and correctness, and keeping up with realistic FaaS workloads. Our evaluations show that FaaSLoad helps us understanding the properties of FaaS applications, and studying the latter under real conditions.
Cite as

Mathieu Bacou. FaaSLoad: Fine-Grained Performance and Resource Measurement for Function-As-a-Service. In 28th International Conference on Principles of Distributed Systems (OPODIS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 324, pp. 22:1-22:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bacou:LIPIcs.OPODIS.2024.22,
  author =	{Bacou, Mathieu},
  title =	{{FaaSLoad: Fine-Grained Performance and Resource Measurement for Function-As-a-Service}},
  booktitle =	{28th International Conference on Principles of Distributed Systems (OPODIS 2024)},
  pages =	{22:1--22:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-360-7},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{324},
  editor =	{Bonomi, Silvia and Galletta, Letterio and Rivi\`{e}re, Etienne and Schiavoni, Valerio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2024.22},
  URN =		{urn:nbn:de:0030-drops-225581},
  doi =		{10.4230/LIPIcs.OPODIS.2024.22},
  annote =	{Keywords: cloud, serverless, Function-as-a-Service, measurement, performance, resource utilization, dataset generation, workload injection}
}
Document
DOI: 10.4230/LIPIcs.DNA.27.1
Robust Digital Molecular Design of Binarized Neural Networks

Authors: Johannes Linder, Yuan-Jyue Chen, David Wong, Georg Seelig, Luis Ceze, and Karin Strauss

Published in: LIPIcs, Volume 205, 27th International Conference on DNA Computing and Molecular Programming (DNA 27) (2021)

Abstract
Molecular programming - a paradigm wherein molecules are engineered to perform computation - shows great potential for applications in nanotechnology, disease diagnostics and smart therapeutics. A key challenge is to identify systematic approaches for compiling abstract models of computation to molecules. Due to their wide applicability, one of the most useful abstractions to realize is neural networks. In prior work, real-valued weights were achieved by individually controlling the concentrations of the corresponding "weight" molecules. However, large-scale preparation of reactants with precise concentrations quickly becomes intractable. Here, we propose to bypass this fundamental problem using Binarized Neural Networks (BNNs), a model that is highly scalable in a molecular setting due to the small number of distinct weight values. We devise a noise-tolerant digital molecular circuit that compactly implements a majority voting operation on binary-valued inputs to compute the neuron output. The network is also rate-independent, meaning the speed at which individual reactions occur does not affect the computation, further increasing robustness to noise. We first demonstrate our design on the MNIST classification task by simulating the system as idealized chemical reactions. Next, we map the reactions to DNA strand displacement cascades, providing simulation results that demonstrate the practical feasibility of our approach. We perform extensive noise tolerance simulations, showing that digital molecular neurons are notably more robust to noise in the concentrations of chemical reactants compared to their analog counterparts. Finally, we provide initial experimental results of a single binarized neuron. Our work suggests a solid framework for building even more complex neural network computation.
Cite as

Johannes Linder, Yuan-Jyue Chen, David Wong, Georg Seelig, Luis Ceze, and Karin Strauss. Robust Digital Molecular Design of Binarized Neural Networks. In 27th International Conference on DNA Computing and Molecular Programming (DNA 27). Leibniz International Proceedings in Informatics (LIPIcs), Volume 205, pp. 1:1-1:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{linder_et_al:LIPIcs.DNA.27.1,
  author =	{Linder, Johannes and Chen, Yuan-Jyue and Wong, David and Seelig, Georg and Ceze, Luis and Strauss, Karin},
  title =	{{Robust Digital Molecular Design of Binarized Neural Networks}},
  booktitle =	{27th International Conference on DNA Computing and Molecular Programming (DNA 27)},
  pages =	{1:1--1:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-205-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{205},
  editor =	{Lakin, Matthew R. and \v{S}ulc, Petr},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DNA.27.1},
  URN =		{urn:nbn:de:0030-drops-146685},
  doi =		{10.4230/LIPIcs.DNA.27.1},
  annote =	{Keywords: Molecular Computing, Neural Network, Binarized Neural Network, Digital Logic, DNA, Strand Displacement}
}
Document
DOI: 10.4230/LIPIcs.SNAPL.2015.262
Hardware-Software Co-Design: Not Just a Cliché

Authors: Adrian Sampson, James Bornholt, and Luis Ceze

Published in: LIPIcs, Volume 32, 1st Summit on Advances in Programming Languages (SNAPL 2015)

Abstract
The age of the air-tight hardware abstraction is over. As the computing ecosystem moves beyond the predictable yearly advances of Moore's Law, appeals to familiarity and backwards compatibility will become less convincing: fundamental shifts in abstraction and design will look more enticing. It is time to embrace hardware-software co-design in earnest, to cooperate between programming languages and architecture to upend legacy constraints on computing. We describe our work on approximate computing, a new avenue spanning the system stack from applications and languages to microarchitectures. We reflect on the challenges and successes of approximation research and, with these lessons in mind, distill opportunities for future hardware-software co-design efforts.
Cite as

Adrian Sampson, James Bornholt, and Luis Ceze. Hardware-Software Co-Design: Not Just a Cliché. In 1st Summit on Advances in Programming Languages (SNAPL 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 32, pp. 262-273, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{sampson_et_al:LIPIcs.SNAPL.2015.262,
  author =	{Sampson, Adrian and Bornholt, James and Ceze, Luis},
  title =	{{Hardware-Software Co-Design: Not Just a Clich\'{e}}},
  booktitle =	{1st Summit on Advances in Programming Languages (SNAPL 2015)},
  pages =	{262--273},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-80-4},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{32},
  editor =	{Ball, Thomas and Bodík, Rastislav and Krishnamurthi, Shriram and Lerner, Benjamin S. and Morriset, Greg},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SNAPL.2015.262},
  URN =		{urn:nbn:de:0030-drops-50301},
  doi =		{10.4230/LIPIcs.SNAPL.2015.262},
  annote =	{Keywords: approximation, co-design, architecture, verification}
}
  • Refine by Type
  • 5 Document/PDF
  • 3 Document/HTML

  • Refine by Publication Year
  • 3 2025
  • 1 2021
  • 1 2015

  • Refine by Author
  • 2 Ceze, Luis
  • 1 Bacou, Mathieu
  • 1 Bornholt, James
  • 1 Chen, Yuan-Jyue
  • 1 Derauf, Zoë Evelyn Mōhalakealoha
  • Show More...

  • Refine by Series/Journal
  • 5 LIPIcs

  • Refine by Classification
  • 1 Applied computing
  • 1 Applied computing → Chemistry
  • 1 Computer systems organization → Cloud computing
  • 1 Computer systems organization → Molecular computing
  • 1 General and reference → Measurement
  • Show More...

  • Refine by Keyword
  • 1 Binarized Neural Network
  • 1 DNA
  • 1 DNA strand displacement
  • 1 Digital Logic
  • 1 Function-as-a-Service
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact