4 Search Results for "Mark, Alan E."

Document
DOI: 10.4230/LIPIcs.ITCS.2023.26
Rounding via Low Dimensional Embeddings

Authors: Mark Braverman and Dor Minzer

Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)

Abstract
A regular graph G = (V,E) is an (ε,γ) small-set expander if for any set of vertices of fractional size at most ε, at least γ of the edges that are adjacent to it go outside. In this paper, we give a unified approach to several known complexity-theoretic results on small-set expanders. In particular, we show: 1) Max-Cut: we show that if a regular graph G = (V,E) is an (ε,γ) small-set expander that contains a cut of fractional size at least 1-δ, then one can find in G a cut of fractional size at least 1-O(δ/(εγ⁶)) in polynomial time. 2) Improved spectral partitioning, Cheeger’s inequality and the parallel repetition theorem over small-set expanders. The general form of each one of these results involves square-root loss that comes from certain rounding procedure, and we show how this can be avoided over small set expanders. Our main idea is to project a high dimensional vector solution into a low-dimensional space while roughly maintaining 𝓁₂² distances, and then perform a pre-processing step using low-dimensional geometry and the properties of 𝓁₂² distances over it. This pre-processing leverages the small-set expansion property of the graph to transform a vector valued solution to a different vector valued solution with additional structural properties, which give rise to more efficient integral-solution rounding schemes.
Cite as

Mark Braverman and Dor Minzer. Rounding via Low Dimensional Embeddings. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 26:1-26:30, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{braverman_et_al:LIPIcs.ITCS.2023.26,
  author =	{Braverman, Mark and Minzer, Dor},
  title =	{{Rounding via Low Dimensional Embeddings}},
  booktitle =	{14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
  pages =	{26:1--26:30},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-263-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{251},
  editor =	{Tauman Kalai, Yael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.26},
  URN =		{urn:nbn:de:0030-drops-175291},
  doi =		{10.4230/LIPIcs.ITCS.2023.26},
  annote =	{Keywords: Parallel Repetition, Small Set Expanders, Semi-Definite Programs}
}
Document
DOI: 10.4230/LIPIcs.DISC.2019.8
On the Computational Power of Radio Channels

Authors: Mark Braverman, Gillat Kol, Rotem Oshman, and Avishay Tal

Published in: LIPIcs, Volume 146, 33rd International Symposium on Distributed Computing (DISC 2019)

Abstract
Radio networks can be a challenging platform for which to develop distributed algorithms, because the network nodes must contend for a shared channel. In some cases, though, the shared medium is an advantage rather than a disadvantage: for example, many radio network algorithms cleverly use the shared channel to approximate the degree of a node, or estimate the contention. In this paper we ask how far the inherent power of a shared radio channel goes, and whether it can efficiently compute "classicaly hard" functions such as Majority, Approximate Sum, and Parity. Using techniques from circuit complexity, we show that in many cases, the answer is "no". We show that simple radio channels, such as the beeping model or the channel with collision-detection, can be approximated by a low-degree polynomial, which makes them subject to known lower bounds on functions such as Parity and Majority; we obtain round lower bounds of the form Omega(n^{delta}) on these functions, for delta in (0,1). Next, we use the technique of random restrictions, used to prove AC^0 lower bounds, to prove a tight lower bound of Omega(1/epsilon^2) on computing a (1 +/- epsilon)-approximation to the sum of the nodes' inputs. Our techniques are general, and apply to many types of radio channels studied in the literature.
Cite as

Mark Braverman, Gillat Kol, Rotem Oshman, and Avishay Tal. On the Computational Power of Radio Channels. In 33rd International Symposium on Distributed Computing (DISC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 146, pp. 8:1-8:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{braverman_et_al:LIPIcs.DISC.2019.8,
  author =	{Braverman, Mark and Kol, Gillat and Oshman, Rotem and Tal, Avishay},
  title =	{{On the Computational Power of Radio Channels}},
  booktitle =	{33rd International Symposium on Distributed Computing (DISC 2019)},
  pages =	{8:1--8:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-126-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{146},
  editor =	{Suomela, Jukka},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2019.8},
  URN =		{urn:nbn:de:0030-drops-113152},
  doi =		{10.4230/LIPIcs.DISC.2019.8},
  annote =	{Keywords: radio channel, lower bounds, approximate majority}
}
Document
DOI: 10.4230/LIPIcs.WABI.2018.16
Multiple-Choice Knapsack for Assigning Partial Atomic Charges in Drug-Like Molecules

Authors: Martin S. Engler, Bertrand Caron, Lourens Veen, Daan P. Geerke, Alan E. Mark, and Gunnar W. Klau

Published in: LIPIcs, Volume 113, 18th International Workshop on Algorithms in Bioinformatics (WABI 2018)

Abstract
A key factor in computational drug design is the consistency and reliability with which intermolecular interactions between a wide variety of molecules can be described. Here we present a procedure to efficiently, reliably and automatically assign partial atomic charges to atoms based on known distributions. We formally introduce the molecular charge assignment problem, where the task is to select a charge from a set of candidate charges for every atom of a given query molecule. Charges are accompanied by a score that depends on their observed frequency in similar neighbourhoods (chemical environments) in a database of previously parameterised molecules. The aim is to assign the charges such that the total charge equals a known target charge within a margin of error while maximizing the sum of the charge scores. We show that the problem is a variant of the well-studied multiple-choice knapsack problem and thus weakly NP-complete. We propose solutions based on Integer Linear Programming and a pseudo-polynomial time Dynamic Programming algorithm. We show that the results obtained for novel molecules not included in the database are comparable to the ones obtained performing explicit charge calculations while decreasing the time to determine partial charges for a molecule by several orders of magnitude, that is, from hours or even days to below a second. Our software is openly available at https://github.com/enitram/charge_assign.
Cite as

Martin S. Engler, Bertrand Caron, Lourens Veen, Daan P. Geerke, Alan E. Mark, and Gunnar W. Klau. Multiple-Choice Knapsack for Assigning Partial Atomic Charges in Drug-Like Molecules. In 18th International Workshop on Algorithms in Bioinformatics (WABI 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 113, pp. 16:1-16:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{engler_et_al:LIPIcs.WABI.2018.16,
  author =	{Engler, Martin S. and Caron, Bertrand and Veen, Lourens and Geerke, Daan P. and Mark, Alan E. and Klau, Gunnar W.},
  title =	{{Multiple-Choice Knapsack for Assigning Partial Atomic Charges in Drug-Like Molecules}},
  booktitle =	{18th International Workshop on Algorithms in Bioinformatics (WABI 2018)},
  pages =	{16:1--16:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-082-8},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{113},
  editor =	{Parida, Laxmi and Ukkonen, Esko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2018.16},
  URN =		{urn:nbn:de:0030-drops-93187},
  doi =		{10.4230/LIPIcs.WABI.2018.16},
  annote =	{Keywords: Multiple-choice knapsack, integer linear programming, pseudo-polynomial dynamic programming, partial charge assignment, molecular dynamics simulations}
}
Document
DOI: 10.4230/OASIcs.CMN.2014.209
Modifying Entity Relationship Models for Collaborative Fiction Planning and its Impact on Potential Authors

Authors: Alan Tapscott, Joaquim Colàs, Ayman Moghnieh, and Josep Blat

Published in: OASIcs, Volume 41, 2014 Workshop on Computational Models of Narrative

Abstract
We propose a modified Entity Relationship (E-R) model, traditionally used for software engineering, to structure, store and share plot data. The flexibility of E-R modelling has been demonstrated by its decades of usage in a wide variety of situations. The success of the E-R model suggests that it could be useful for collaborating fiction authors, adding a certain degree of computational power to their process. We changed the E-R model syntax to better suit the story plans, switching the emphasis from generic types to instanced story entities, but preserving relationships and attributes. We conducted a small-scale basic experiment to study the impact of using our modified E-R model on authors when understanding and contributing into a pre-existing fiction story plan. The results analysis revealed that the E-R model supports authors as effectively as written text in reading comprehension, memory, and contributing. In addition, the results show that, when combined together, the written text and the E-R model help participants achieve better comprehension--always within the frame of our experiment. We discuss potential applications of these findings.
Cite as

Alan Tapscott, Joaquim Colàs, Ayman Moghnieh, and Josep Blat. Modifying Entity Relationship Models for Collaborative Fiction Planning and its Impact on Potential Authors. In 2014 Workshop on Computational Models of Narrative. Open Access Series in Informatics (OASIcs), Volume 41, pp. 209-221, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{tapscott_et_al:OASIcs.CMN.2014.209,
  author =	{Tapscott, Alan and Col\`{a}s, Joaquim and Moghnieh, Ayman and Blat, Josep},
  title =	{{Modifying Entity Relationship Models for Collaborative Fiction Planning and its Impact on Potential Authors}},
  booktitle =	{2014 Workshop on Computational Models of Narrative},
  pages =	{209--221},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-71-2},
  ISSN =	{2190-6807},
  year =	{2014},
  volume =	{41},
  editor =	{Finlayson, Mark A. and Meister, Jan Christoph and Bruneau, Emile G.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.CMN.2014.209},
  URN =		{urn:nbn:de:0030-drops-46588},
  doi =		{10.4230/OASIcs.CMN.2014.209},
  annote =	{Keywords: storytelling, story planning, Entity Relationship Model}
}
  • Refine by Author
  • 2 Braverman, Mark
  • 1 Blat, Josep
  • 1 Caron, Bertrand
  • 1 Colàs, Joaquim
  • 1 Engler, Martin S.
  • Show More...

  • Refine by Classification
  • 1 Applied computing → Chemistry
  • 1 Theory of computation → Communication complexity
  • 1 Theory of computation → Discrete optimization
  • 1 Theory of computation → Distributed computing models
  • 1 Theory of computation → Problems, reductions and completeness

  • Refine by Keyword
  • 1 Entity Relationship Model
  • 1 Multiple-choice knapsack
  • 1 Parallel Repetition
  • 1 Semi-Definite Programs
  • 1 Small Set Expanders
  • Show More...

  • Refine by Type
  • 4 document

  • Refine by Publication Year
  • 1 2014
  • 1 2018
  • 1 2019
  • 1 2023

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
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact