86 research outputs found
Non-Adaptive Edge Counting and Sampling via Bipartite Independent Set Queries
No full textWe study the problem of estimating the number of edges in an n-vertex graph, accessed via the Bipartite Independent Set query model introduced by Beame et al. (TALG '20). In this model, each query returns a Boolean, indicating the existence of at least one edge between two specified sets of nodes. We present a non-adaptive algorithm that returns a (1± ε) relative error approximation to the number of edges, with query complexity Õ(ε^{-5}log⁵ n), where Õ(⋅) hides poly(log log n) dependencies. This is the first non-adaptive algorithm in this setting achieving poly(1/ε,log n) query complexity. Prior work requires Ω(log² n) rounds of adaptivity. We avoid this by taking a fundamentally different approach, inspired by work on single-pass streaming algorithms. Moreover, for constant ε, our query complexity significantly improves on the best known adaptive algorithm due to Bhattacharya et al. (STACS '22), which requires O(ε^{-2} log^{11} n) queries. Building on our edge estimation result, we give the first {non-adaptive} algorithm for outputting a nearly uniformly sampled edge with query complexity Õ(ε^{-6} log⁶ n), improving on the works of Dell et al. (SODA '20) and Bhattacharya et al. (STACS '22), which require Ω(log³ n) rounds of adaptivity. Finally, as a consequence of our edge sampling algorithm, we obtain a Õ(n log^8 n) query algorithm for connectivity, using two rounds of adaptivity. This improves on a three-round algorithm of Assadi et al. (ESA '21) and is tight; there is no non-adaptive algorithm for connectivity making o(n²) queries
Improved Approximation and Scalability for Fair Max-Min Diversification
No full textGiven an n-point metric space ({},d) where each point belongs to one of m = O(1) different categories or groups and a set of integers k₁, …, k_m, the fair Max-Min diversification problem is to select k_i points belonging to category i ∈ [m], such that the minimum pairwise distance between selected points is maximized. The problem was introduced by Moumoulidou et al. [ICDT 2021] and is motivated by the need to down-sample large data sets in various applications so that the derived sample achieves a balance over diversity, i.e., the minimum distance between a pair of selected points, and fairness, i.e., ensuring enough points of each category are included. We prove the following results:
1) We first consider general metric spaces. We present a randomized polynomial time algorithm that returns a factor 2-approximation to the diversity but only satisfies the fairness constraints in expectation. Building upon this result, we present a 6-approximation that is guaranteed to satisfy the fairness constraints up to a factor 1-ε for any constant ε. We also present a linear time algorithm returning an m+1 approximation with exact fairness. The best previous result was a 3m-1 approximation.
2) We then focus on Euclidean metrics. We first show that the problem can be solved exactly in one dimension. {For constant dimensions, categories and any constant ε > 0, we present a 1+ε approximation algorithm that runs in O(nk) + 2^{O(k)} time where k = k₁+…+k_m.} We can improve the running time to O(nk)+poly(k) at the expense of only picking (1-ε) k_i points from category i ∈ [m].
Finally, we present algorithms suitable to processing massive data sets including single-pass data stream algorithms and composable coresets for the distributed processing
Enhancements of the generic manifold user interface:
No full textManifold is an attempt to create a generic UI which would be application-independent, where the UI can be easily “detached” from one application and “attached” to another one. The Model-View-Controller (MVC) design pattern is a popular design pattern used in User Interfaces which has been employed in manifold. In this pattern, a user generates input device events which are interpreted as actions on the domain model via a Controller. After execution of the requested actions, the model sends notifications about the effect of the actions, and the notifications are visualized as feedback to the user.
Different applications have different sets of inputs and so the UI should be able to translate a users input on manifold’s workspace to that of the domain model. To solve these issues, the MVC design and the Event Frame concept has been incorporated. The EventFrame conveys user’s intentions (event) in a standardized format to the Controller to be acted up on the domain model.
The EventFrame being the only “medium” to communicate to the Controller makes it pivotal in communication between the UI and the domain model. We envision manifold to grow in to a complex application that would cater to various complex domain models on the internet where XML is gaining popularity as a way to share and transport data. In such a situation, the number of messages sent between the manipulator and Controller would be enormous. We felt that in such a situation, the Event Frame would be a bottle neck to performance.
Considerable amount of my work in this thesis concerns with re-engineering the Event Frame in order to make it “web friendly”. We eliminated the Hashtable to represent the EventFrame with a comma separated String that would make it easier for the XML parser to parse data. The modifications made to the application and performance enhancements have been described in detail.
Property editors are used to edit the properties/attributes of a selected glyph. It exposes the glyph’s properties for editing. Every time a new glyph is selected, the old editors are emptied from the viewer, and the new set of editors are loaded. My work in this thesis describes the implementation of newer property editors incorporated in to the property viewer panel that will provide a user with enhanced options to edit a selected glyph. The newer property editors incorporated are a fill color editor which fills the interior of a glyph with a user specified color and a stroke editor which edits the stroke of a glyphs boundary.
Lastly, while the basic feature of being able to draw a glyph and perform actions on them using tools worked, there were certain issues with the property viewer that prevented the properties editors from being displayed in the property viewer pane. My preliminary work was to eliminate these issues. I have described the issues with in the application and the solutions employed to eliminate them.M.S.Includes bibliographical references (p. 82-84)by Raghavendra Y. Sidhant
Recommended from our members
COMBINATORIAL ALGORITHMS FOR GRAPH DISCOVERY AND EXPERIMENTAL DESIGN
No full textIn this thesis, we study the design and analysis of algorithms for discovering the structure and properties of an unknown graph, with applications in two different domains: causal inference and sublinear graph algorithms. In both these domains, graph discovery is possible using restricted forms of experiments, and our objective is to design low-cost experiments. First, we describe efficient experimental approaches to the causal discovery problem, which in its simplest form, asks us to identify the causal relations (edges of the unknown graph) between variables (vertices of the unknown graph) of a given system. For causal discovery, we study algorithms for the problem of learning the causal relationships between a set of observed variables in the presence of hidden or unobserved variables while minimizing a suitable cost of interventions on the observed variables. An intervention on a set of variables helps learn the presence of causal relations adjacent to them. Under various cost models for interventions, we design combinatorial algorithms for causal discovery by identifying new connections between discrete optimization, graph property testing, and efficient intervention design. Next, we investigate query-efficient experimental approaches for estimating various graph properties, such as the number of edges and graph connectivity. The access to the graph, or equivalently performing an experiment, is via a Bipartite Independent Set (BIS) oracle. The BIS oracle is related to the interventional access model used in our work for causal graph discovery, with other applications in group testing and fine-grained complexity. In this setting, we develop non-adaptive algorithms that lead to efficient implementations in highly parallelized and low-memory streaming settings.Doctor of Philosophy (Ph.D.
Electrokinetically-driven deterministic lateral displacement for particle separation in microfluidic device
No full textAn electrokinetically driven deterministic lateral displacement device is proposed for the continuous, two-dimensional fractionation of suspensions in microfluidic platforms. The suspended species are driven through an array of regularly spaced cylindrical posts by applying an electric field across the device. We explore the entire range of orientations of the driving field with respect to the array of obstacles and show that, at specific forcing angles, particles of different size migrate in different directions, thus enabling continuous, two-dimensional separation. We discuss a number of features observed in the motion of the particles, including directional locking and sharp transitions between migration angles upon variations in the direction of the force, that are advantageous for high-resolution two-dimensional separation. A simple model based on individual particle–obstacle interactions accurately describes the migration angle of the particles depending on the orientation of the driving field and can be used to reconfigure the electric field depending on the composition of the samples.Peer reviewe
Systematically controlling the error rates in variation-prone networks-on-chip for energy efficiency
No full textNetworks-on-Chip (NoCs) are prone to within-die process variation as they
span the whole chip. To tolerate variation, their voltages (Vdd) carry overprovisioned
guardbands. As a result, prior work has proposed to save energy
by dynamically managing Vdd, operating at reduced Vdd while occasionally
su ering and xing errors. Unfortunately, these proposals use ad-hoc controller
designs that may not work under other scenarios and do not provide
error bounds.
This thesis develops a scheme that dynamically minimizes the Vdd of groups
of routers in a variation-prone NoC using formal control-theory methods.
The scheme, called Contra, saves substantial energy while guaranteeing the
stability and convergence of error rates. Moreover, the scheme is enhanced
with a low-cost secondary network that retransmits erroneous packets for
higher energy e ciency. The enhanced scheme is called Contra+. Both
Contra and Contra+ are evaluated using simulations of NoCs with 64{100
routers. In an NoC with 8 routers per Vdd domain, the proposed schemes
reduce the average energy consumption of the NoC by 27%; in a futuristic
NoC with one router per Vdd domain, Contra+ and Contra reduce the average
energy consumption by 37% and 32%, respectively. The performance impact
is negligible. These savings are signi cant over the state-of-the-art. The
results categorically state that formal control is essential to attain a stable,
scalable, and energy-efficient design. Additionally, it is found that while the
secondary network helps Contra+ attain higher energy savings, it has a nonnegligible
hardware cost. Hence, Contra is the most cost-effective design.Item withdrawn by Laura Spradlin ([email protected]) on 2014-12-05T17:11:52Z
Item was in collections:
University of Illinois Theses & Dissertations (ID: 1)
No. of bitstreams: 2
Pothukuchi_Raghavendra Pradyumna.pdf: 2697519 bytes, checksum: c06e93f9a071c02f989c1ba7581242d1 (MD5)
Pothukuchi_Raghavendra Pradyumna.pdf: 2697510 bytes, checksum: de24e3ad8adcd82236bb0bab0b9e9c58 (MD5)Made available in DSpace on 2015-01-21T19:59:26Z (GMT). No. of bitstreams: 1
Raghavendra Pradyumna_Pothukuchi.pdf: 2689844 bytes, checksum: 72bd35d68426515996fc837fdba12b2d (MD5)Embargo set by: Seth Robbins for item 73279
Lift date: 2017-01-21T19:59:39Z
Reason: Author requested closed access (OA after 2yrs) in Vireo ETD systemLimited Restriction Lifted for Item 73279 on 2017-01-22T10:15:32Z
Structure-based algorithms for protein-protein interaction prediction
No full textThesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Materials Science and Engineering, 2012.This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections.Cataloged from student submitted PDF version of thesis.Includes bibliographical references (p. 109-124).Protein-protein interactions (PPIs) play a central role in all biological processes. Akin to the complete sequencing of genomes, complete descriptions of interactomes is a fundamental step towards a deeper understanding of biological processes, and has a vast potential to impact systems biology, genomics, molecular biology and therapeutics. PPIs are critical in maintenance of cellular integrity, metabolism, transcription/ translation, and cell-cell communication. This thesis develops new methods that significantly advance our efforts at structure- based approaches to predict PPIs and boost confidence in emerging high-throughput (HTP) data. The aims of this thesis are, 1) to utilize physicochemical properties of protein interfaces to better predict the putative interacting regions and increase coverage of PPI prediction, 2) increase confidence in HTP datasets by identifying likely experimental errors, and 3) provide residue-level information that gives us insights into structure-function relationships in PPIs. Taken together, these methods will vastly expand our understanding of macromolecular networks. In this thesis, I introduce two computational approaches for structure-based proteinprotein interaction prediction: iWRAP and Coev2Net. iWRAP is an interface threading approach that utilizes biophysical properties specific to protein interfaces to improve PPI prediction. Unlike previous structure-based approaches that use single structures to make predictions, iWRAP first builds profiles that characterize the hydrophobic, electrostatic and structural properties specific to protein interfaces from multiple interface alignments. Compatibility with these profiles is used to predict the putative interface region between the two proteins. In addition to improved interface prediction, iWRAP provides better accuracy and close to 50% increase in coverage on genome-scale PPI prediction tasks. As an application, we effectively combine iWRAP with genomic data to identify novel cancer related genes involved in chromatin remodeling, nucleosome organization and ribonuclear complex assembly - processes known to be critical in cancer. Coev2Net addresses some of the limitations of iWRAP, and provides techniques to increase coverage and accuracy even further. Unlike earlier sequence and structure profiles, Coev2Net explicitly models long-distance correlations at protein interfaces. By formulating interface co-evolution as a high-dimensional sampling problem, we enrich sequence/structure profiles with artificial interacting homologus sequences for families which do not have known multiple interacting homologs. We build a spanning-tree based graphical model induced by the simulated sequences as our interface profile. Cross-validation results indicate that this approach is as good as previous methods at PPI prediction. We show that Coev2Net's predictions correlate with experimental observations and experimentally validate some of the high-confidence predictions. Furthermore, we demonstrate how analysis of the predicted interfaces together with human genomic variation data can help us understand the role of these mutations in disease and normal cells.by Raghavendra Hosur.Ph.D
Semantic enrichment of design requirements using Object Type Libraries for automated verification: Towards automated requirements verification system
No full textSuccess of the project depends on compliance to requirements amongst other things (Wheeler, 2003). This forms Requirements Management process an important step in the Systems Engineering life cycle. However, poor definition of requirements is an obstacle in automating the verification process. The existing solutions based on various approaches focus predominantly on building codes requirement verification and is not suitable for the dynamicity of client specific requirements. existing solutions also require users to have expertise on programming and construction domain knowledge. Hence, a general approach for rewriting client requirements in a machine understandable way is needed. The research focuses on developing this general approach using object and properties data from standard libraries such as Object Type Libraries (OTL).Civil Engineering | Construction Management and Engineerin
- …
