1,185 research outputs found
Preconditioning for the Geometric Transportation Problem
No full textIn the geometric transportation problem, we are given a collection of points P in d-dimensional Euclidean space, and each point is given a supply of mu(p) units of mass, where mu(p) could be a positive or a negative integer, and the total sum of the supplies is 0. The goal is to find a flow (called a transportation map) that transports mu(p) units from any point p with mu(p) > 0, and transports -mu(p) units into any point p with mu(p) < 0. Moreover, the flow should minimize the total distance traveled by the transported mass. The optimal value is known as the transportation cost, or the Earth Mover’s Distance (from the points with positive supply to those with negative supply). This problem has been widely studied in many fields of computer science: from theoretical work in computational geometry, to applications in computer vision, graphics, and machine learning.
In this work we study approximation algorithms for the geometric transportation problem. We give an algorithm which, for any fixed dimension d, finds a (1+epsilon)-approximate transportation map in time nearly-linear in n, and polynomial in epsilon^{-1} and in the logarithm of the total supply. This is the first approximation scheme for the problem whose running time depends on n as n * polylog(n). Our techniques combine the generalized preconditioning framework of Sherman, which is grounded in continuous optimization, with simple geometric arguments to first reduce the problem to a minimum cost flow problem on a sparse graph, and then to design a good preconditioner for this latter problem
Noisy Radio Network Lower Bounds via Noiseless Beeping Lower Bounds
No full textMuch of today’s communication is carried out over large wireless systems with different input-output behaviors. In this work, we compare the power of central abstractions of wireless communication through the general notion of boolean symmetric f-channels: In every round of the f-channel, each of its n parties decides to either broadcast or not, and the channel outputs f(m), where m is the number of broadcasting parties.
Our first result is that the well studied beeping channel, where f is the threshold-1 function, is not stronger than any other f-channel. To this end, we design a protocol over the f-channel and prove that any protocol that simulates it over the beeping channel blows up the round complexity by a factor of Ω(log n). Our lower bound technique may be of independent interest, as it essentially generalizes the popular fooling set technique by exploiting a "local" relaxation of combinatorial rectangles.
Curiously, while this result shows the limitations of a noiseless channel, namely, the beeping channel, we are able to use it to show the limitations of the noisy version of many other channels. This includes the extensively studied single-hop radio network model with collisions-as-silence (CAS), which is equivalent to the f-channel with f(m) = 1 iff m = 1.
In particular, our second and main result, obtained from the first, shows that converting CAS protocols to noise resilient ones may incur a large performance overhead, i.e., no constant rate interactive code exists. To this end, we design a CAS protocol and prove that any protocol that simulates it over the noisy CAS model with correlated stochastic noise, blows up the round complexity by a factor of Ω(log n). We mention that the Ω(log n) overhead in both our results is tight
Protecting Single-Hop Radio Networks from Message Drops
No full textSingle-hop radio networks (SHRN) are a well studied abstraction of communication over a wireless channel. In this model, in every round, each of the n participating parties may decide to broadcast a message to all the others, potentially causing collisions. We consider the SHRN model in the presence of stochastic message drops (i.e., erasures), where in every round, the message received by each party is erased (replaced by ⊥) with some small constant probability, independently.
Our main result is a constant rate coding scheme, allowing one to run protocols designed to work over the (noiseless) SHRN model over the SHRN model with erasures. Our scheme converts any protocol Π of length at most exponential in n over the SHRN model to a protocol Π' that is resilient to constant fraction of erasures and has length linear in the length of Π.
We mention that for the special case where the protocol Π is non-adaptive, i.e., the order of communication is fixed in advance, such a scheme was known. Nevertheless, adaptivity is widely used and is known to hugely boost the power of wireless channels, which makes handling the general case of adaptive protocols Π both important and more challenging. Indeed, to the best of our knowledge, our result is the first constant rate scheme that converts adaptive protocols to noise resilient ones in any multi-party model
Characterizing the Multi-Pass Streaming Complexity for Solving Boolean CSPs Exactly
No full textWe study boolean constraint satisfaction problems (CSPs) Max-CSP^f_n for all predicates f: {0,1}^k → {0,1}. In these problems, given an integer v and a list of constraints over n boolean variables, each obtained by applying f to a sequence of literals, we wish to decide if there is an assignment to the variables that satisfies at least v constraints. We consider these problems in the streaming model, where the algorithm makes a small number of passes over the list of constraints.
Our first and main result is the following complete characterization: For every predicate f, the streaming space complexity of the Max-CSP^f_n problem is Θ̃(n^deg(f)), where deg(f) is the degree of f when viewed as a multilinear polynomial. While the upper bound is obtained by a (very simple) one-pass streaming algorithm, our lower bound shows that a better space complexity is impossible even with constant-pass streaming algorithms.
Building on our techniques, we are also able to get an optimal Ω(n²) lower bound on the space complexity of constant-pass streaming algorithms for the well studied Max-CUT problem, even though it is not technically a Max-CSP^f_n problem as, e.g., negations of variables and repeated constraints are not allowed
Writing the Time of Troubles, False Dmitry in Russian Literature (Book Review)
No full textThis book discusses the Time of Troubles (Smutnoe vremya) period and the pretenders who appeared after the killing of Ivan the Terrible’s legal heir, Ivan, leaving the Empire without leadership. The power struggle began immediately after the death of Tsar Ivan which brought the Rurikid dynasty to an end; rival boyars created a weak government and autocracy. The book discusses these issues and the representations of Dmitry, the son of Ivan the Terrible within the context of Russian literature. The absence of legitimate royal authority after the demise of the Rurikid dynasty in 1598 caused a dynastic crisis. This period known as the Time of Troubles was characterized by a dynastic struggle that nearly resulted in the shattering of the Muscovite state. It finally came to an end in 1613 with the appearance of the new dynasty, the Romanovs. The book consists of six chapter. In the Introduction the author states that she will examine the “protagonist”, Dmitry, within the context of Russian literature. She examines Dmitry both as a literary figure and a real historical one, and describes Dmitry as a “tabula rasa” because he died under mysterious circumstances with no credible witnesses to confirm how he died. In her book, the author conducts her research both chronologically and diachronically. Chapter I is an introductory chapter that provides information on the eighteenth and nineteenth-century Russian texts Tulupov’s Life of St. Dmitry, The Story of Grishka Otrepev and Tale of Recovery that illustrate the prehistory of Dmitry. The author compares seventeenth century text types and arrives at the conclusion that all three works express a political message and that all of them contain a hagiographical structure and explication. Chapter II examines Russia’s historical experience in the eighteenth century and its literary tradition. In this chapter, the author examines Sumarokov’s tragedy Dmitry the Pretender and Narezhny’s Dmitry the Pretender. The author compares the main causes of his usurpation and its interpretation in literary works of the seventeenth century and the eighteenth century, and concludes that the writers of the seventeenth century crafted quasi-literary, polemical, monological interpretations of the period and determined who was the sole man qualified to rule. Prose treatments of the Dmitry material were the most appropriate way to shape their literature. Eighteenth century writers, on the other hand, recognized a large number of candidates to the throne and their interpretation of the period was multifaceted; tragedy was the most popular literary genres. In Chapter III, the author examines the body of works discussing Dmitry and the Time of Troubles in the 1820s and 1830s: Alexander Pushkin’s Comedy about Tsar Boris and Grishka Otrepev, Faddey Bulgarin’s Dmitry the Pretender, Alexey Khomyakov’s Dmitry the Pretender, Mikhail Pogodin’s Historical Portrait of Dmitry the Pretender. She states that the writers of Russia’s early nineteenth century were fascinated with the Dmitry materials, and each writer depicted him as a man who lived among others and saw him as an alternative to the reigning autocracy. However, they later arrived at the conclusion that there was no viable alternative to the reigning autocracy. Chapter IV deals with two plays written in response to the Era of Great Reforms in 1866: Alexander Ostrovsky’s Dmitry the Pretender and Vasily Shuisky and Nikolay Chaev’s Dmitry the Pretender. She criticizes both authors’ works on a number of fronts, regarding all of them as being overly ambitious in that they attempt to treat too many unrelated issues, and that the miscellaneous political issues raised in these dramatic works have no clear connection to one another. In the Chapter V, the author states that Dmitry disappears from Russian novels and plays for a century and reappears after the demise of the Soviet Union. She examines Daniil Mordovtsev’s False Dmitry: A Historical Novel of the Time of Troubles, Vasily Avenarius’s In Service to the Tsarevich, Nikolay Alekseev’s The False Tsarevich and Alexey Suvorin’s Tsar Dmitry the Pretender and Tsarevna Xenya. The author concludes that each writer has presented his own interpretation of Dmitry and his era, that these works are clearly independent and any similarities among them are merely coincidental with no pattern to them. Since each writer has selected his own particular assortment of “facts”, the novels each follow their own unique line of development. On a more general note, the author argues that the collection of late nineteenth century works on the Time of Troubles should be interpreted in the context of both their local frame of reference and national pride in the country’s cultural heritage. However, in the Soviet period Dmitry’s disappearance was the result of the Soviets’ emphasis on shaping the nation’s future rather than linking present realities to the national past. In the Conclusion, the author points out that all of the works discussed simultaneously deal with two distinct periods in time – the time in which the works are set and the time in which they were composed. For seventeenth century writers, marking the passing of the old dynasty was important, but the establishment of a new dynasty was just as significant. In the two eighteenth century works that were examined, contemporary political issues were treated in the context of Dmitry’s era. Nineteenth century works more closely resemble seventeenth century works in that the contemporary relevance of the historical events these works deal with is their main focus. According to the author, as long as writers continue to deal with political issues in literature or the theater, the figure of Dmitry will remain a relevant character. This book is very well written source examining the Time of Troubles period, a period when there was no legal heir to run the state, when dynastic struggle began the process of bringing an end to the Rurik Dynasty and leading to a period pretenders. The author provides different interpretations for the “protagonist”, Dmitry, within the context of Russian literature. The author particularly examines different writers’ works in chronological order and discusses the legitimacy of Dmitry by comparing the treatments of the pretenders. This book should be of interest to anyone interested in the period of the Time of Troubles and usurpation and their interpretation in Russian literature
A multi-lepton search for new physics in 35pb⁻¹ proton-proton collisions at the LHC for a center of mass energy of √s = 7 TeV using the CMS detector
No full textThis thesis describes a model independent search for new physics with a decay signature of three or more leptons and missing transverse energy in 35pb⁻¹ of proton-proton collisions at the LHC at a center mass energy √s = 7 TeV using the CMS detector. Standard Model backgrounds are predicted using both simulations and collision data. The observed events are consistent with the Standard Model predictions. The results are interpreted using various supersymmetric models: gravity mediated symmetry breaking, gauge mediated symmetry breaking with slepton co-NLSP, and leptonic R-parity violating.Ph. D.Includes bibliographical referencesby Dmitry Hit
Information Dissemination via Broadcasts in the Presence of Adversarial Noise
No full textWe initiate the study of error correcting codes over the multi-party adversarial broadcast channel. Specifically, we consider the classic information dissemination problem where n parties, each holding an input bit, wish to know each other’s input. For this, they communicate in rounds, where, in each round, one designated party sends a bit to all other parties over a channel governed by an adversary that may corrupt a constant fraction of the received communication. We mention that the dissemination problem was studied in the stochastic noise model since the 80’s.
While stochastic noise in multi-party channels has received quite a bit of attention, the case of adversarial noise has largely been avoided, as such channels cannot handle more than a 1/n-fraction of errors. Indeed, this many errors allow an adversary to completely corrupt the incoming or outgoing communication for one of the parties and fail the protocol. Curiously, we show that by eliminating these "trivial" attacks, one can get a simple protocol resilient to a constant fraction of errors. Thus, a model that rules out such attacks is both necessary and sufficient to get a resilient protocol.
The main shortcoming of our dissemination protocol is its length: it requires Θ(n²) communication rounds whereas n rounds suffice in the absence of noise. Our main result is a matching lower bound of Ω(n²) on the length of any dissemination protocol in our model. Our proof first "gets rid" of the channel noise by converting it to a form of "input noise", showing that a noisy dissemination protocol implies a (noiseless) protocol for a version of the direct sum gap-majority problem. We conclude the proof with a tight lower bound for the latter problem, which may be of independent interest
Recommended from our members
Computation over the Noisy Broadcast Channel with Malicious Parties
No full textWe study the n-party noisy broadcast channel with a constant fraction of malicious parties. Specifically, we assume that each non-malicious party holds an input bit, and communicates with the others in order to learn the input bits of all non-malicious parties. In each communication round, one of the parties broadcasts a bit to all other parties, and the bit received by each party is flipped with a fixed constant probability (independently for each recipient). How many rounds are needed?
Assuming there are no malicious parties, Gallager gave an (n log log n)-round protocol for the above problem, which was later shown to be optimal. This protocol, however, inherently breaks down in the presence of malicious parties.
We present a novel n ⋅ ̃(√{log n})-round protocol, that solves this problem even when almost half of the parties are malicious. Our protocol uses a new type of error correcting code, which we call a locality sensitive code and which may be of independent interest. Roughly speaking, these codes map "close" messages to "close" codewords, while messages that are not close are mapped to codewords that are very far apart.
We view our result as a first step towards a theory of property preserving interactive coding, i.e., interactive codes that preserve useful properties of the protocol being encoded. In our case, the naive protocol over the noiseless broadcast channel, where all the parties broadcast their input bit and output all the bits received, works even in the presence of malicious parties. Our simulation of this protocol, unlike Gallager’s, preserves this property of the original protocol
Outstanding Surgeon and Scientist Dmitry Alekseevich Arapov
No full textIn 2022, we are approaching 125 years since the birth of Dmitry Alekseevich Arapov, a prominent domestic surgeon, scientist, experimenter, organizer of the military medical services. Dmitry A. Arapov, one of the most prominent representatives of the S.S. Yudin scientific school, worked at the N.V. Sklifosovsky Research Institute for Emergency Medicine from 1929 till 1984. He quickly proved himself not only as an excellent doctor and a skilled surgeon, but also as a researcher, and soon became one of the closest students and associates of S.S. Yudin. Dmitry A. Arapov drafted as a field surgeon during the Soviet-Finnish war of 1939-1940, from the first to the last day he went through the Great Patriotic War, being the Head of the surgical service of the Northern Fleet in Polyarny. In this position, he significantly improved the system for providing emergency surgical care on ships and in naval hospitals, based on the experience gained over the years of work at the N.V. Sklifosovsky Research Institute for Emergency Medicine. From July 1950 Dmitry A. Arapov was Chief Surgeon of the USSR Navy, from May 1953 he was Deputy Chief surgeon of the Main Military Sanitary Directorate of the USSR Ministry of Defense, and from May 1955 again Chief Surgeon of the USSR Navy, until his retirement in October, 1968. At the same time, Dmitry A. Arapov did not leave his work at the N.V. Sklifosovsky Research Institute for Emergency Medicine until the last days of his life. Dmitry A. Arapov is the author of more than 200 research papers, including 14 monographs. Scientific interests of Dmitry A. Arapov went far beyond emergency surgery, to which he naturally paid most attention. His works are devoted to various issues of military and emergency surgery of the abdominal and thoracic organs, topical issues of burn injuries, surgical site infections, reconstructive surgery, neurosurgery, treatment of endocrine disorders, and anesthesiology and resuscitation. Also Dmitry A. Arapov successfully dealt with the problems of autotransfusion, blood reinfusion from the chest and abdomen, transfusion of fibrinolytic blood. The main directions of scientific research, laid down by Dmitry A. Arapov, are currently being continued at the Scientific Department of Emergency Surgery, Endoscopy and Intensive Care of the N.V. Sklifosovsky Research Institute for Emergency Medicine. Memory of Dmitry A. Arapov has been preserved to this day. To the 100th anniversary of the birth of D.A. Arapov, a scientific conference was held at our Institute. The naval hospital in the town of Polyarny, Murmansk region, was named after Dmitry A. Arapov, and in honor of D.A. Arapov, a memorial plaque was installed on its building. In the 70s of the twentieth century, People’s Artist of the USSR L.E. Kerbel created a sculpture of Dmitry A. Arapov, which was stored in the local history museum of the town of Polyarny. His bust portrait (by artist T.S. Smagina) is exhibited at the Scientific Department of Emergency Surgery, Endoscopy and Intensive Care of the N.V. Sklifosovsky Research Institute for Emergency Medicine. In addition, the N.V. Sklifosovsky Research Institute for Emergency Medicine owns an earlier portrait of Dmitry A. Arapov by artist F.S. Bulgak. We introduce these portraits into scientific circulation for the first time. We are confident that they will be able to tell contemporaries a lot about this scientist, surgeon and man who made a great contribution to surgery and military medicine, and rightfully entered the history of Russian medicine
Student Years of Dmitry Mushketov at St. Petersburg Mining Institute
No full textСтатья посвящена годам обучения в Горном институте в Петербурге выдающегося ученого-геолога СССР Дмитрия Ивановича Мушкетова, будущего ректора этого института (1918-1926). Раскрыіваются программа обучения, успехи в ее освоении, круг преподавателей, летние геологические практики, первые научные работы, написанные по их материалам.The article focuses on student years of the outstanding Soviet scientist and geologist Dmitry Mushketov (1918-1926), who later became the rector of St.Petersburg Mining Institute. The author gives an overview of the Institute’s curriculum and Dmitry Mushketov’s educational trajectory and describes the impact that his mentors had on his development as a scientist
- …
