355 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
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
Responsible ML Datasets
No full textIn this study, we discuss the importance of Responsible Machine Learning Datasets through the lens of fairness, privacy, and regulatory compliance and present a large audit of Computer Vision datasets. The audit is conducted through evaluation of the proposed responsible rubric. After surveying over 100 datasets, our detailed analysis of 60 distinct datasets highlights a universal susceptibility to fairness, privacy, and regulatory compliance issues.
Please cite the paper below.
Mittal, Surbhi, Kartik Thakral, Richa Singh, Mayank Vatsa, Tamar Glaser, Cristian Canton Ferrer, Tal Hassner. "On Responsible Machine Learning Datasets Emphasizing Fairness Privacy and Regulatory Norms with Examples in Biometrics and Healthcare." Nature Machine Intelligence (2024).
@article{mittal2024responsible,
title={On Responsible Machine Learning Datasets Emphasizing Fairness Privacy and Regulatory Norms with Examples in Biometrics and Healthcare},
author={Mittal, Surbhi, and Thakral, Kartik and Singh, Richa and Vatsa, Mayank and Glaser, Tamar and Ferrer, Cristian Canton and Hassner, Tal},
journal={Nature Machine Intelligence},
year={2024},
publisher={Nature Publishing Group UK London}
Responsible ML Datasets
No full textIn this study, we discuss the importance of Responsible Machine Learning Datasets through the lens of fairness, privacy, and regulatory compliance and present a large audit of Computer Vision datasets. The audit is conducted through evaluation of the proposed responsible rubric. After surveying over 100 datasets, our detailed analysis of 60 distinct datasets highlights a universal susceptibility to fairness, privacy, and regulatory compliance issues.
Please cite the paper below.
Mittal, Surbhi, Kartik Thakral, Richa Singh, Mayank Vatsa, Tamar Glaser, Cristian Canton Ferrer, Tal Hassner. "On Responsible Machine Learning Datasets Emphasizing Fairness Privacy and Regulatory Norms with Examples in Biometrics and Healthcare." Nature Machine Intelligence (2024).
@article{mittal2024responsible,
title={On Responsible Machine Learning Datasets Emphasizing Fairness Privacy and Regulatory Norms with Examples in Biometrics and Healthcare},
author={Mittal, Surbhi, and Thakral, Kartik and Singh, Richa and Vatsa, Mayank and Glaser, Tamar and Ferrer, Cristian Canton and Hassner, Tal},
journal={Nature Machine Intelligence},
year={2024},
publisher={Nature Publishing Group UK London}
Approximation of Signals (Functions) by Trigonometric Polynomials in Lp-Norm
No full textMittal and Rhoades (1999, 2000) and Mittal et al. (2011) have initiated a study of error estimates En(f) through
trigonometric-Fourier approximation (tfa) for the situations in which the summability matrix T does not have monotone rows. In this paper, the first author continues the work in the direction for T to be a Np-matrix. We extend two theorems on summability matrix Np of Deger et al. (2012) where they have extended two theorems of Chandra (2002) using Cλ-method obtained by deleting a set of rows from Cesàro matrix C1. Our theorems also generalize two theorems of Leindler (2005) to Np-matrix which in turn generalize the result of Chandra (2002) and Quade (1937)
Highly scalable solution of incompressible Navier-Stokes equations using the spectral element method with overlapping grids
No full textWe present a highly-flexible Schwarz overlapping framework for simulating turbulent fluid/thermal transport in complex domains. The approach is based on a variant of the Schwarz alternating method in which the solution is advanced in parallel in separate overlapping subdomains. In each domain, the governing equations are discretized with an efficient high-order spectral element method (SEM). At each step, subdomain boundary data are determined by interpolating from the overlapping region of adjacent subdomains. The data are either lagged in time or extrapolated to higher-order temporal accuracy using a novel stabilized predictor-corrector algorithm. Matrix stability analysis is used to determine the optimal number of corrector iterations. Stability and accuracy are further improved with an optimal mass flux correction to guarantee mass conservation throughout the domain. The method supports an arbitrary number of subdomains. A new multirate time-stepping scheme is developed (a first for incompressible flow simulations) that allows the underlying equations to be advanced with time-step sizes varying as much as an order-of-magnitude between adjacent domains. All the developments maintain the third-order temporal convergence and exponential convergence of the originating SEM framework. This dissertation also presents a mesh optimizer that has been specifically designed for meshes generated for turbulent flow problems. The optimizer supports surface mesh improvement, which minimizes geometrical approximation errors. The smoother is shown to reduce the computational cost of numerical calculations by as much as 40%. Numerous examples illustrate the effectiveness of these new technologies for analyzing challenging turbulence problems that were previously infeasible.Submission published under a 24 month embargo labeled 'U of I Access', the embargo will last until 2021-12-01The student, Ketan Mittal, accepted the attached license on 2019-10-07 at 11:58.The student, Ketan Mittal, submitted this Dissertation for approval on 2019-10-07 at 12:08.This Dissertation was approved for publication on 2019-10-09 at 15:36.DSpace SAF Submission Ingestion Package generated from Vireo submission #14486 on 2020-02-28 at 17:20:54Made available in DSpace on 2020-03-02T22:12:10Z (GMT). No. of bitstreams: 2
MITTAL-DISSERTATION-2019.pdf: 43195402 bytes, checksum: ee2355b57595dfdb6f0483c839c4b9ce (MD5)
LICENSE.txt: 4209 bytes, checksum: db35dd4507774e72a4ad849ff9b8751d (MD5)
Previous issue date: 2019-10-09Embargo set by: Seth Robbins for item 113863
Lift date: 2022-03-02T22:12:26Z
Reason: Author requested U of Illinois access only (OA after 2yrs) in Vireo ETD systemEmbargo set by: Seth Robbins for item 113863
Lift date: 2022-03-02T22:15:21Z
Reason: Author requested U of Illinois access only (OA after 2yrs) in Vireo ETD systemEmbargo set by: Seth Robbins for item 113863
Lift date: 2022-03-02T22:18:25Z
Reason: Author requested U of Illinois access only (OA after 2yrs) in Vireo ETD systemOpen Restriction set for Item 113863 on 2020-03-04T16:22:37Z with date null by [email protected] Restriction set for Item 113863 on 2020-03-04T16:22:39Z with date null by [email protected]
Application of SDP to product rules and quantum query complexity
No full textIn recent years, semidefinite programming has played a vital role in shaping complexity theory and quantum computing. There have been numerous applications ranging from estimating quantum values, over approximating combinatorial quantities, to proving various bounds. This work extends the use of semidefinite programs (SDPs) to proving product rules and to characterizing quantum query complexity. In the first application, we provide a general framework to establishing product rules for quantities that can be expressed (or approximated) using SDPs. We use duality theory to give product rules, which bound the value of the ``product'' of two problems in terms of their value. Some previous results have implicitly used the properties of SDPs to give such product rules. Here we give sufficient and necessary conditions under which these approaches work, thereby enabling us to capture these previous results under our unified framework. We also include a discussion about alternate definitions of what a ``product'' means and how they fit into our approach. The second application provides an SDP characterization of quantum query complexity, which is one of the ways in which complexity of a function can be measured. It is known that quantum query complexity can be lower bounded by the so-called ``adversary method'' which is expressible as a semidefinite program. Recently, Ben Reichardt showed that the adversary method leads to a tight lower bound for boolean functions by converting the solution of this SDP (of adversary method) into an algorithm. We show that a related SDP, called ``witness size'' in this thesis, provides a tight bound on the quantum query complexity of non boolean functions (total as well as partial). This witness size SDP is also used to give composition results for quantum query complexity. We also show that the witness size is bounded by a constant multiple of the adversary bound. Finally, we briefly explore whether other convex programming paradigms can be useful in complexity theory. One of them is copositive programming. We show that one of the recent result about parallel repetition of unique games, by Barak et.al., can be interpreted as an application of copositive programming.Ph.D.Includes bibliographical referencesIncludes vitaby Rajat Mitta
- …
