146 research outputs found
Recommended from our members
Block Rigidity: Strong Multiplayer Parallel Repetition Implies Super-Linear Lower Bounds for Turing Machines
No full textWe prove that a sufficiently strong parallel repetition theorem for a special case of multiplayer (multiprover) games implies super-linear lower bounds for multi-tape Turing machines with advice. To the best of our knowledge, this is the first connection between parallel repetition and lower bounds for time complexity and the first major potential implication of a parallel repetition theorem with more than two players.
Along the way to proving this result, we define and initiate a study of block rigidity, a weakening of Valiant’s notion of rigidity [Valiant, 1977]. While rigidity was originally defined for matrices, or, equivalently, for (multi-output) linear functions, we extend and study both rigidity and block rigidity for general (multi-output) functions. Using techniques of Paul, Pippenger, Szemerédi and Trotter [Paul et al., 1983], we show that a block-rigid function cannot be computed by multi-tape Turing machines that run in linear (or slightly super-linear) time, even in the non-uniform setting, where the machine gets an arbitrary advice tape.
We then describe a class of multiplayer games, such that, a sufficiently strong parallel repetition theorem for that class of games implies an explicit block-rigid function. The games in that class have the following property that may be of independent interest: for every random string for the verifier (which, in particular, determines the vector of queries to the players), there is a unique correct answer for each of the players, and the verifier accepts if and only if all answers are correct. We refer to such games as independent games. The theorem that we need is that parallel repetition reduces the value of games in this class from v to v^Ω(n), where n is the number of repetitions.
As another application of block rigidity, we show conditional size-depth tradeoffs for boolean circuits, where the gates compute arbitrary functions over large sets
Polynomial Bounds on Parallel Repetition for All 3-Player Games with Binary Inputs
No full textWe prove that for every 3-player (3-prover) game G with value less than one, whose query distribution has the support S = {(1,0,0), (0,1,0), (0,0,1)} of Hamming weight one vectors, the value of the n-fold parallel repetition G^{⊗n} decays polynomially fast to zero; that is, there is a constant c = c(G) > 0 such that the value of the game G^{⊗n} is at most n^{-c}.
Following the recent work of Girish, Holmgren, Mittal, Raz and Zhan (STOC 2022), our result is the missing piece that implies a similar bound for a much more general class of multiplayer games: For every 3-player game G over binary questions and arbitrary answer lengths, with value less than 1, there is a constant c = c(G) > 0 such that the value of the game G^{⊗n} is at most n^{-c}.
Our proof technique is new and requires many new ideas. For example, we make use of the Level-k inequalities from Boolean Fourier Analysis, which, to the best of our knowledge, have not been explored in this context prior to our work
First person – Kunal Chopra
No full textFirst Person is a series of interviews with the first authors of a selection of papers published in Biology Open, helping early-career researchers promote themselves alongside their papers. Kunal Chopra is first author on ‘Zebrafish duox mutations provide a model for human congenital hypothyroidism’, published in BIO. Kunal is a PhD student in the lab of Enrique Amaya at the University of Manchester, investigating reactive oxygen species in wound healing and regeneration
Parallel Repetition for the GHZ Game: A Simpler Proof
No full textWe give a new proof of the fact that the parallel repetition of the (3-player) GHZ game reduces the value of the game to zero polynomially quickly. That is, we show that the value of the n-fold GHZ game is at most n^{-Ω(1)}. This was first established by Holmgren and Raz [Holmgren and Raz, 2020]. We present a new proof of this theorem that we believe to be simpler and more direct. Unlike most previous works on parallel repetition, our proof makes no use of information theory, and relies on the use of Fourier analysis.
The GHZ game [Greenberger et al., 1989] has played a foundational role in the understanding of quantum information theory, due in part to the fact that quantum strategies can win the GHZ game with probability 1. It is possible that improved parallel repetition bounds may find applications in this setting.
Recently, Dinur, Harsha, Venkat, and Yuen [Dinur et al., 2017] highlighted the GHZ game as a simple three-player game, which is in some sense maximally far from the class of multi-player games whose behavior under parallel repetition is well understood. Dinur et al. conjectured that parallel repetition decreases the value of the GHZ game exponentially quickly, and speculated that progress on proving this would shed light on parallel repetition for general multi-player (multi-prover) games
Learning Arithmetic Formulas in the Presence of Noise: A General Framework and Applications to Unsupervised Learning
No full textWe present a general framework for designing efficient algorithms for unsupervised learning problems, such as mixtures of Gaussians and subspace clustering. Our framework is based on a meta algorithm that learns arithmetic formulas in the presence of noise, using lower bounds. This builds upon the recent work of Garg, Kayal and Saha (FOCS '20), who designed such a framework for learning arithmetic formulas without any noise. A key ingredient of our meta algorithm is an efficient algorithm for a novel problem called Robust Vector Space Decomposition. We show that our meta algorithm works well when certain matrices have sufficiently large smallest non-zero singular values. We conjecture that this condition holds for smoothed instances of our problems, and thus our framework would yield efficient algorithms for these problems in the smoothed setting
Watershed modeling using HEC-RAS, HEC-HMS, and GIS models: a case study of the Wreck Pond Brook Watershed in Monmouth County, New Jersey
No full textManaging stormwater on a watershed basis is considered the best strategy to address flooding. A watershed model should provide temporal and spatial distribution of runoff response for a given storm. GIS applicability in watershed modeling is increasing due to the availability of spatial information, fast processors and interfaces such as ArcHydro, HEC-GeoHMS, and HEC-GeoRAS linking hydrologic and hydraulic models to the ArcGIS environment.
Soil Conservation Service methods are used widely in hydrologic models. Several parameters inherent to these empirical methods are average values derived from various watershed conditions. These average values overestimate peak flows for flat, low-lying coastal terrains. The design of flood control structures based on these flow values allow more post-development discharge, make the system more hydraulically efficient, increase project costs, and cause flooding for areas downstream. In this study, Wreck Pond Brook Watershed (WPBW), a coastal New Jersey area was used for sensitivity studies of the initial abstraction ratio and peak rate factor. The HEC-HMS modeling results indicated use of a lower peak rate factor (e.g. 284) and 5% initial abstraction ratio provided better characterization of stream response. These updated parameters provide new technical information for improving stormwater management in coastal areas.
An important limitation in hydraulic modeling is the economic constraint on cross-section spacing for surveying channels and floodplains. Applying GIS techniques in hydraulic modeling eliminated this constraint. Floodplain analysis was done using ArcGIS, HEC-GeoRAS and HEC-RAS. Detailed elevation data (LIDAR information from Monmouth County) was incorporated into the HEC-RAS using GIS models. This innovation was important for improving model efficiency. The modeled floodplain demonstrated close agreement to the observed floodplain for the October 2005 storm and showed greater accuracy compared to the FEMA floodplain for the 100-year storm. This study validated use of LIDAR elevation data in floodplain analysis for the second-order streams in coastal NJ.
Finally, an approach was demonstrated using modeled floodplain and HEC-HMS for flood control analysis. This study presents an innovative watershed modeling approach using GIS models while addressing the limitations of traditional hydrologic and hydraulic methods using WPBW as an example.Ph.D.Includes bibliographical references (p. 259-263)by Kunal P. Pate
Opportunities and challenges of investing in Indian real estate
No full textThesis (S.M.)--Massachusetts Institute of Technology, Program in Real Estate Development in Conjunction with the Center for Real Estate , 2009.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. 125-128).In recent years, global real estate investment has become an important component of efficient global mixed asset portfolios. Although these investments carry increased political, regulatory and currency risk, international real estate investment has been on the rise. Compelling macroeconomic and demographic trends along with improvements in structural and regulatory conditions and investment in infrastructure are driving strong real estate capital flows into the emerging markets. This thesis provides a study of the opportunities and challenges of investing in one emerging market, India. With a population of over 1 billion, India has been a major beneficiary of the "Globalization of Real Estate". This thesis identifies the opportunities in India that have caused global capital to flow into Indian real estate and the key factors driving Indian real estate. It explains the challenges of investing in Indian real estate and seeks to provide strategies for navigating the real estate landscape in India.by Kunal Wadhwani.S.M
Computational modeling of intrinsic dissipation in nano-structure
No full textIn this work, using computational modeling, we study the different mechanisms of intrinsic dissipation in nano-electro mechanical systems (NEMS). We, first, use molecular dynamics (MD) simulation and gain an understanding of the underlying loss mechanisms. Using insights from the MD simulation, a multi-scale method to model intrinsic damping is developed. The high frequency vibration in NEMS have important applications. A few examples include the sensing of atomic mass, detection of biological molecules and observation of quantum effects in macroscopic objects. For all these potential applications, dissipation plays a limiting role. While a number of experimental and theoretical studies have been performed, the individual role of different mechanisms remains unclear. In this work, we attempt to isolate and understand the surface and size effect on some of the intrinsic mechanisms. We, first, consider the case of the Akhiezer damping. The Akhiezer dynamics is expected to play an important role in nano-resonators with frequencies in the GHz range. Using a judiciously devised MD set-up, we isolate Akhiezer dynamics. We show that the surfaces aid in reducing the dissipation rate through increasing the rate of thermalization of the phonons. We, next, study damping under the flexure mode of operation. A comparative analysis with the stretching mode shows that the flexure mode is less dissipative. A reduced order model is considered to understand this novel behavior. We, also, investigate the role of tension on the Q factor, a measure of the inverse of dissipation rate.
From these studies, we conclude that Akhiezer dynamics plays a dominant role in nano-resonators. We, then, develop a quasi-harmonic based multi-scale method to model Akhiezer damping. A stress component, that characterizes the non-equilibrium phonon population, is derived. We obtain constitutive relation that governs the time evolution of the non-equilibrium stress. Different methods to parametrize the constitutive relation are discussed. Using the proposed formulation, we compute the dissipation rate for different cases. The results are compared with those obtained using MD. Next, we use the Boltzmann transport equation and investigate the Q factor due to the thermo-elastic dissipation (TED). The Q factor obtained shows deviations from the classical theory of TED. Correction to the classical formula, for the case of longitudinal modes, is provided.
We, then, study damping is low dimensional structure. We first consider the case of two dimensional graphene sheet and under in-plane stretching. We show that the coupling between the in-plane and the out-of-plane motions plays an important role in the loss of mechanical energy. Further, a hysteresis behavior in the out-of-plane dynamics is observed. Next, we investigate the stretching motion of graphene nano-ribbon. A normal mode Langevin dynamics is devised to understand the results from the MD simulation.Submission published under a 24 month embargo labeled 'U of I Access', the embargo will last until 2018-05-01The student, Kumar Kunal, accepted the attached license on 2015-12-23 at 11:24.The student, Kumar Kunal, submitted this Dissertation for approval on 2015-12-23 at 11:27.This Dissertation was approved for publication on 2016-01-04 at 13:54.DSpace SAF Submission Ingestion Package generated from Vireo submission #9026 on 2016-07-07 at 13:48:03Made available in DSpace on 2016-07-07T20:26:39Z (GMT). No. of bitstreams: 2
KUNAL-DISSERTATION-2016.pdf: 3947483 bytes, checksum: 9a73090ecdaf3fc5edf73524d5cea5b2 (MD5)
LICENSE.txt: 4208 bytes, checksum: 44cbdc30f5d645ce6b2621afb8dd4a62 (MD5)
Previous issue date: 2016-01-04Embargo set by: Seth Robbins for item 93059
Lift date: 2018-07-07T20:28:14Z
Reason: Author requested U of Illinois access only (OA after 2yrs) in Vireo ETD systemEmbargo set by: Seth Robbins for item 93059
Lift date: 2018-07-07T20:35:34Z
Reason: Author requested U of Illinois access only (OA after 2yrs) in Vireo ETD systemU of I Only Restriction Lifted for Item 93059 on 2018-07-08T09:15:36Z
INDEPENDENT HEROES: Supporting Type 1 Diabetic Young Adults’ Transition to Independent Living
No full textThis Master of Design Thesis project focuses on the condition of severe hypoglycemia (low blood sugar) in young adults living with type 1 diabetes by carefully understanding the unique challenges they face in transitioning to adult care. This research surfaces the needs that often get blurred in the transition process and offers a design for an appropriate solution to support the identified issues. Canadian young adults living with type 1 diabetes often find themselves at the risk of hypoglycemia during emerging adulthood. The concept of emerging adulthood has not been considered extensively in managing chronic illness and transition from pediatric to adult care. Yet, this is a critical time when a person may first assume full responsibility for their diabetes self-care while simultaneously facing all the usual challenges young adults face. Additionally, the fear of hypoglycemia is strongest in this group. A review of the literature informs us about previous work done in this field. However, most current interventions are in the form of bulky printed materials. Another critical issue with the development of most recent tools is the absence of user involvement in the creative process leading to unmet user needs. In this project, participatory design methodologies were introduced in a human-centered approach, collaborating with young adults to understand and address the transition process gap. It included actively listening to user narratives and co-creating the solution. The synthesis of primary and secondary research resulted in the designed outcome of a smart wearable device that will work in conjunction with the Continuous glucose monitor (CGM) and alerts the bystander and emergency contacts by turning them into potential lifesavers. It will inform them of a diabetic emergency and guide them through the life-saving instructions. Additionally, it will alert the medical emergency services for prompt assistance if needed. The solution attempts to provide early intervention during emergency and could also alleviate the fear of hypoglycemia in young adults. This in turn will reduce the load on the already burdened healthcare system
- …
