62 research outputs found
Polynomial Pass Semi-Streaming Lower Bounds for K-Cores and Degeneracy
No full textThe following question arises naturally in the study of graph streaming algorithms:
Is there any graph problem which is "not too hard", in that it can be solved efficiently with total communication (nearly) linear in the number n of vertices, and for which, nonetheless, any streaming algorithm with Õ(n) space (i.e., a semi-streaming algorithm) needs a polynomial n^Ω(1) number of passes?
Assadi, Chen, and Khanna [STOC 2019] were the first to prove that this is indeed the case. However, the lower bounds that they obtained are for rather non-standard graph problems.
Our first main contribution is to present the first polynomial-pass lower bounds for natural "not too hard" graph problems studied previously in the streaming model: k-cores and degeneracy. We devise a novel communication protocol for both problems with near-linear communication, thus showing that k-cores and degeneracy are natural examples of "not too hard" problems. Indeed, previous work have developed single-pass semi-streaming algorithms for approximating these problems. In contrast, we prove that any semi-streaming algorithm for exactly solving these problems requires (almost) Ω(n^{1/3}) passes.
The lower bound follows by a reduction from a generalization of the hidden pointer chasing (HPC) problem of Assadi, Chen, and Khanna, which is also the basis of their earlier semi-streaming lower bounds.
Our second main contribution is improved round-communication lower bounds for the underlying communication problems at the basis of these reductions:
- We improve the previous lower bound of Assadi, Chen, and Khanna for HPC to achieve optimal bounds for this problem.
- We further observe that all current reductions from HPC can also work with a generalized version of this problem that we call MultiHPC, and prove an even stronger and optimal lower bound for this generalization. These two results collectively allow us to improve the resulting pass lower bounds for semi-streaming algorithms by a polynomial factor, namely, from n^{1/5} to n^{1/3} passes
Centrifugal forming and mechanical properties of silicone-based elastomers for soft robotic actuators
No full textThis thesis describes the centrifugal forming and resulting mechanical properties of silicone-based elastomers for the manufacture of soft robotic actuators. This process is effective at removing bubbles that get entrapped within 3D-printed, enclosed molds. Conventional methods for rapid prototyping of soft robotic actuators to remove entrapped bubbles typically involve degassing under vacuum, with open-faced molds that limit the layout of formed parts to raised 2D geometries. As the functionality and complexity of soft robots increase, there is a need to mold complete 3D structures with controlled thicknesses or curvatures on multiples surfaces. In addition, characterization of the mechanical properties of common elastomers for these soft robots has lagged the development of new designs. As such, relationships between resulting material properties and processing parameters are virtually non-existent. One of the goals of this thesis is to provide guidelines and physical insights to relate the design, processing conditions, and resulting properties of soft robotic components to each other. Centrifugal forming with accelerations on the order of 100 g’s is capable of forming bubble-free, true 3D components for soft robotic actuators, and resulting demonstrations in this work include an aquatic locomotor, soft gripper, and an actuator that straightens when pressurized. Finally, this work shows that the measured mechanical properties of 3D geometries fabricated within enclosed molds through centrifugal forming possess comparable mechanical properties to vacuumed materials formed from open-faced molds with raised 2D features.M.S.Includes bibliographical referencesby Parth Kulkarn
Pseudonáhodné procházky a chip-firing games
No full textStudujeme dva deterministické procesy analogické náhodným procházkám na grafech. První je hra s vystřelováním žetonů, chip-firing game, zavedená Björnerem a Lovászem. Jedná se o hru jednoho hráče hranou pohybem žetonů po orientovaném grafu. Našli jsme efektivní simulaci booleovských obvodů a Turingových strojů pomocí této hry. Druhým procesem je Prop- pův stroj, neboli rotor-router model, pseudonáhodný proces zavedený Priez- zhevem. Zlepšujeme výsledky Kijima a spol. a ukazujeme novou horní mez O(m) na diskrepanci tohoto procesu na grafech stupně d s m hranami. 1We study two deterministic analogues of random walks. The first is the chip-firing game, a single player game played by moving chips around a directed graph, popularised by Björner and Lovász. We find an efficient simulation of boolean circuits and Turing machines using instances of the chip-firing game - after assigning a fixed strategy to the player. The second is the Propp machine, or the rotor router model, a quasirandom model intro- duced by Priezzhev. We improve results of Kijima et al. and show a bound of O(m) on the discrepancy of this process from a random walk on d-regular graphs with m edges. 1Computer Science Institute of Charles UniversityInformatický ústav Univerzity KarlovyMatematicko-fyzikální fakultaFaculty of Mathematics and Physic
Pseudorandom walks and chip firing games
No full textWe study two deterministic analogues of random walks. The first is the chip-firing game, a single player game played by moving chips around a directed graph, popularised by Björner and Lovász. We find an efficient simulation of boolean circuits and Turing machines using instances of the chip-firing game - after assigning a fixed strategy to the player. The second is the Propp machine, or the rotor router model, a quasirandom model intro- duced by Priezzhev. We improve results of Kijima et al. and show a bound of O(m) on the discrepancy of this process from a random walk on d-regular graphs with m edges.
Characterization and optimization of UAV power system for aerial and submersible multi-medium multirotor vehicle
No full textEven as an emerging technology, Unmanned Aerial Vehicles (UAVs) have had a tremendous impact on the world. From the way wars are fought, to the way we take selfies, drones are well on their way to revolutionizing our daily lives. One of the most innovative applications of these vehicles in the Naviator submersible-UAV. This unique multirotor is capable of aerial flight and underwater operations with seamless Air-Water transitions. In this thesis, the power system of a multirotor UAS is characterized using standard performance models with the goal of designing and optimizing the systems of a new Naviator V5 prototype. Test beds were created to collect data on BLDC motors and propellers and their performance was assessed in air and water. Theoretical models using BEM theory and the 3-constant motor model were validated for their accuracy. Experiments found that RC air propellers are similarly efficient in air and water and BLDC motor performance is partially diminished due to the higher viscosity of water. The effects of input voltage, throttle, Kv rating, and motor size were also evaluated using motor torque curves. Using this data, an optimal power system for the Naviator V5 prototype was designed, tested, and evaluated.M.S.T.Includes bibliographical referencesby Parth V. Son
Evacuation of Kobylnice village in extraordinary event
No full textCílem této práce je sestavení evakuačního plánu pro obec Kobylnice. Teoretická část přibližuje problematiku mimořádných událostí a možných následků, zpracovává dostupnou literaturu a uvádí zákony a vyhlášky spojené s evakuačním plánováním. V praktické části se autor zmiňuje o programech, které jsou použitelné při mimořádných a krizových situacích a sestavuje plán evakuace.The aim of this work is evacuation plan setup for Kobylnice Corporation. The theoretical parth explains issue of extraordinary events and possible consequences, processes available information and shows the laws and public notices are being used in evacuative planning. In the practical parth author presents programs, which are applicability to extraordinary events and crisis situations. She draws a plan of evacuation.Institut bezpečnostních technologiíobhájen
Foundations of the law on industrial organisations in Russia and the former republics of the USSR: 1985-1990
No full textThe industrial organisations introduced into the law of the USSR from 1987, and thereafter
into the law of the former republics, developed upon a foundation that was rooted in Soviet
law and was constructed during the period from 1985 to mid-1990.
While this study focuses on the industrial economy, certain aspects of the agrarian economy,
and in particular the early history and structure of the collective farm, are considered where
appropriate.
The thesis presents an entirely new understanding both of the nature of these developments
and of the significance of the law on ownership. The foundations of the law on industrial
organisations are conceptualised within specific heuristic models which are elaborated in an
attempt to consolidate and highlight the key steps in this history. It is argued that Soviet law
did not contain a concept of the "generic owner" or a developed understanding of the
ownership of a juridical person, in particular by multiple owners holding "ownership
interests" of that juridical person; and that their absence critically impaired a rational and
coherent structure for the foundations of the law on industrial organisations both within the
Stalin economic settlement and the new economic constitution of 1990
Electrochemical screening and surface analysis of environmentally friendly corrosion inhibitors for aerospace aluminium alloy
No full textFor the past few decades, the aerospace industry has been actively looking for measures to tackle the problem of localized corrosion of aluminium alloy 2024-T3. One such measure was the use of hexavalent chromium salts as corrosion inhibitors. However, recent studies have reflected the environmental concerns and health impacts associated with these compounds. Since then, there has been a quest for alternatives that can be used as corrosion inhibitors for AA2024-T3. This thesis is aimed at studying these compounds by testing their inhibitive properties. Selecting an inhibitor from a set of compounds and recommending the best one is a crucial process. The research focuses on the screening of these inhibitors through various electrochemical techniques such as Potentiodynamic Polarisation(PDP), Linear Polarisation Resistance(LPR), and Electrochemical Impedance Spectroscopy(EIS). The electrochemical experiments during the first 24-hour exposure of AA2024-T3 to inhibitors exhibited that 2,5-Dimercapto-1,3,4-thiadiazole acts as a corrosion accelerator, while Na-Mercaptoacetate and Mercaptobenzimidazole showed the most inhibitive performance among the tested organic compounds. On monitoring their nature during 24 hours, it was observed that they show stable polarisation resistance values after 6 hours. Among the inorganics, Cerium compounds were seen to have better inhibitive properties than the Lithiumcompounds. Additionally, surface studies such as Fourier Transform Infrared Spectroscopy (FTIR) revealed the presence of thiol/mercaptan and carboxyl groups on samples exposed toNa-Mercaptoacetate. X-ray Photoelectron Spectroscopy (XPS) showed oxides of Cerium on samples exposed to Cerium Nitrate. Finally, the correlations between the inhibition efficiencies calculated from different electrochemical testing methods were illustrated using Pearson’s correlation method.Materials Science and Engineerin
Towards Designing Reliable and Efficient Millimeter-Wave Wireless LANS
No full textWith the increasing amount of mobile data and the demand for high data rates, current 2.4GHz/5GHz wireless local area networks (WLANs) are facing the problem of limited capacity. Millimeter-wave (mmWave) networks with gigahertz of channel bandwidth can provide multi-gigabit per second data rates, making it possible to support novel applications such as augmented/virtual reality (AR/VR), mobile offloading, high-resolution video streaming, etc. However, despite the potential, the directional nature of mmWave WLAN makes it prone to blockages and mobility. The dense deployment of Access Points (APs) brings unpredictable interference and non-negligible beamforming overhead. Moreover, current mmWave WLANs are application agnostic, resulting in inefficient usage of resources in supporting AR/VR type bandwidth-intensive applications. In this dissertation, I propose novel solutions to four key challenges, aiming to build practical, reliable, and efficient mmWave WLANs. Firstly, I explore a proactive blockage mitigation technique that utilizes joint transmissions of multiple APs to provide blockage resilience. Secondly, I characterize interference in dense mmWave WLANs and implement three interference mitigation techniques using commercial-off-the-shelf (COTS) devices. Thirdly, focusing on reducing the beamforming overhead, I propose a “Networked beamforming” model to reduce the number of APs that conduct beamforming in dense mmWave WLANs, resulting in significant improvements in network throughput. Lastly, I design novel solutions for blockage prediction and prefetching based on users’ six-degree-of-freedom (6DoF) position and orientation information to facilitate high-quality volumetric video streaming over mmWave WLANs.This work is embargoed by the author and will not be publicly available until 2024-08-31.2024-08-3
- …
