41 results on '"Bhowmick, Abhishek"'
Search Results
2. Federated Evaluation and Tuning for On-Device Personalization: System Design & Applications
- Author
-
Paulik, Matthias, Seigel, Matt, Mason, Henry, Telaar, Dominic, Kluivers, Joris, van Dalen, Rogier, Lau, Chi Wai, Carlson, Luke, Granqvist, Filip, Vandevelde, Chris, Agarwal, Sudeep, Freudiger, Julien, Byde, Andrew, Bhowmick, Abhishek, Kapoor, Gaurav, Beaumont, Si, Cahill, Áine, Hughes, Dominic, Javidbakht, Omid, Dong, Fei, Rishi, Rehan, and Hung, Stanley
- Subjects
Computer Science - Machine Learning - Abstract
We describe the design of our federated task processing system. Originally, the system was created to support two specific federated tasks: evaluation and tuning of on-device ML systems, primarily for the purpose of personalizing these systems. In recent years, support for an additional federated task has been added: federated learning (FL) of deep neural networks. To our knowledge, only one other system has been described in literature that supports FL at scale. We include comparisons to that system to help discuss design decisions and attached trade-offs. Finally, we describe two specific large scale personalization use cases in detail to showcase the applicability of federated tuning to on-device personalization and to highlight application specific solutions., Comment: 11 pages, 1 figure
- Published
- 2021
3. Protection Against Reconstruction and Its Applications in Private Federated Learning
- Author
-
Bhowmick, Abhishek, Duchi, John, Freudiger, Julien, Kapoor, Gaurav, and Rogers, Ryan
- Subjects
Statistics - Machine Learning ,Computer Science - Machine Learning - Abstract
In large-scale statistical learning, data collection and model fitting are moving increasingly toward peripheral devices---phones, watches, fitness trackers---away from centralized data collection. Concomitant with this rise in decentralized data are increasing challenges of maintaining privacy while allowing enough information to fit accurate, useful statistical models. This motivates local notions of privacy---most significantly, local differential privacy, which provides strong protections against sensitive data disclosures---where data is obfuscated before a statistician or learner can even observe it, providing strong protections to individuals' data. Yet local privacy as traditionally employed may prove too stringent for practical use, especially in modern high-dimensional statistical and machine learning problems. Consequently, we revisit the types of disclosures and adversaries against which we provide protections, considering adversaries with limited prior information and ensuring that with high probability, ensuring they cannot reconstruct an individual's data within useful tolerances. By reconceptualizing these protections, we allow more useful data release---large privacy parameters in local differential privacy---and we design new (minimax) optimal locally differentially private mechanisms for statistical learning problems for \emph{all} privacy levels. We thus present practicable approaches to large-scale locally private model training that were previously impossible, showing theoretically and empirically that we can fit large-scale image classification and language models with little degradation in utility.
- Published
- 2018
4. Changing Socioeconomic Structure of Paudi Bhuyans, a Particular Vulnerable Tribe of Odisha, India
- Author
-
Bhowmick, Abhishek, primary
- Published
- 2022
- Full Text
- View/download PDF
5. A Framework for Accelerating Bottlenecks in GPU Execution with Assist Warps
- Author
-
Vijaykumar, Nandita, Pekhimenko, Gennady, Jog, Adwait, Ghose, Saugata, Bhowmick, Abhishek, Ausavarangnirun, Rachata, Das, Chita, Kandemir, Mahmut, Mowry, Todd C., and Mutlu, Onur
- Subjects
Computer Science - Hardware Architecture - Abstract
Modern Graphics Processing Units (GPUs) are well provisioned to support the concurrent execution of thousands of threads. Unfortunately, different bottlenecks during execution and heterogeneous application requirements create imbalances in utilization of resources in the cores. For example, when a GPU is bottlenecked by the available off-chip memory bandwidth, its computational resources are often overwhelmingly idle, waiting for data from memory to arrive. This work describes the Core-Assisted Bottleneck Acceleration (CABA) framework that employs idle on-chip resources to alleviate different bottlenecks in GPU execution. CABA provides flexible mechanisms to automatically generate "assist warps" that execute on GPU cores to perform specific tasks that can improve GPU performance and efficiency. CABA enables the use of idle computational units and pipelines to alleviate the memory bandwidth bottleneck, e.g., by using assist warps to perform data compression to transfer less data from memory. Conversely, the same framework can be employed to handle cases where the GPU is bottlenecked by the available computational units, in which case the memory pipelines are idle and can be used by CABA to speed up computation, e.g., by performing memoization using assist warps. We provide a comprehensive design and evaluation of CABA to perform effective and flexible data compression in the GPU memory hierarchy to alleviate the memory bandwidth bottleneck. Our extensive evaluations show that CABA, when used to implement data compression, provides an average performance improvement of 41.7% (as high as 2.6X) across a variety of memory-bandwidth-sensitive GPGPU applications.
- Published
- 2016
6. Quantifying and Visualizing Uncertainties in Molecular Models
- Author
-
Rasheed, Muhibur, Clement, Nathan, Bhowmick, Abhishek, and Bajaj, Chandrajit
- Subjects
Computer Science - Computational Engineering, Finance, and Science ,F.2 ,G.3 - Abstract
Computational molecular modeling and visualization has seen significant progress in recent years with sev- eral molecular modeling and visualization software systems in use today. Nevertheless the molecular biology community lacks techniques and tools for the rigorous analysis, quantification and visualization of the associated errors in molecular structure and its associated properties. This paper attempts at filling this vacuum with the introduction of a systematic statistical framework where each source of structural uncertainty is modeled as a ran- dom variable (RV) with a known distribution, and properties of the molecules are defined as dependent RVs. The framework consists of a theoretical basis, and an empirical implementation where the uncertainty quantification (UQ) analysis is achieved by using Chernoff-like bounds. The framework enables additionally the propagation of input structural data uncertainties, which in the molecular protein world are described as B-factors, saved with almost all X-ray models deposited in the Protein Data Bank (PDB). Our statistical framework is also able and has been applied to quantify and visualize the uncertainties in molecular properties, namely solvation interfaces and solvation free energy estimates. For each of these quantities of interest (QOI) of the molecular models we provide several novel and intuitive visualizations of the input, intermediate, and final propagated uncertainties. These methods should enable the end user achieve a more quantitative and visual evaluation of various molecular PDB models for structural and property correctness, or the lack thereof., Comment: 19 figures, 30 pages
- Published
- 2015
7. Bias vs structure of polynomials in large fields, and applications in information theory
- Author
-
Bhowmick, Abhishek and Lovett, Shachar
- Subjects
Computer Science - Discrete Mathematics ,Mathematics - Combinatorics ,Mathematics - Number Theory ,11C08 ,F.2.2 - Abstract
Let $f$ be a polynomial of degree $d$ in $n$ variables over a finite field $\mathbb{F}$. The polynomial is said to be unbiased if the distribution of $f(x)$ for a uniform input $x \in \mathbb{F}^n$ is close to the uniform distribution over $\mathbb{F}$, and is called biased otherwise. The polynomial is said to have low rank if it can be expressed as a composition of a few lower degree polynomials. Green and Tao [Contrib. Discrete Math 2009] and Kaufman and Lovett [FOCS 2008] showed that bias implies low rank for fixed degree polynomials over fixed prime fields. This lies at the heart of many tools in higher order Fourier analysis. In this work, we extend this result to all prime fields (of size possibly growing with $n$). We also provide a generalization to nonprime fields in the large characteristic case. However, we state all our applications in the prime field setting for the sake of simplicity of presentation. Using the above generalization to large fields as a starting point, we are also able to settle the list decoding radius of fixed degree Reed-Muller codes over growing fields. The case of fixed size fields was solved by Bhowmick and Lovett [STOC 2015], which resolved a conjecture of Gopalan-Klivans-Zuckerman [STOC 2008]. Here, we show that the list decoding radius is equal the minimum distance of the code for all fixed degrees, even when the field size is possibly growing with $n$. Additionally, we effectively resolve the weight distribution problem for Reed-Muller codes of fixed degree over all fields, first raised in 1977 in the classic textbook by MacWilliams and Sloane [Research Problem 15.1 in Theory of Error Correcting Codes].
- Published
- 2015
8. Using higher-order Fourier analysis over general fields
- Author
-
Bhattacharyya, Arnab and Bhowmick, Abhishek
- Subjects
Computer Science - Data Structures and Algorithms ,Computer Science - Computational Complexity ,Computer Science - Information Theory ,Mathematics - Combinatorics - Abstract
Higher-order Fourier analysis, developed over prime fields, has been recently used in different areas of computer science, including list decoding, algorithmic decomposition and testing. We extend the tools of higher-order Fourier analysis to analyze functions over general fields. Using these new tools, we revisit the results in the above areas. * For any fixed finite field $\mathbb{K}$, we show that the list decoding radius of the generalized Reed Muller code over $\mathbb{K}$ equals the minimum distance of the code. Previously, this had been proved over prime fields [BL14] and for the case when $|\mathbb{K}|-1$ divides the order of the code [GKZ08]. * For any fixed finite field $\mathbb{K}$, we give a polynomial time algorithm to decide whether a given polynomial $P: \mathbb{K}^n \to \mathbb{K}$ can be decomposed as a particular composition of lesser degree polynomials. This had been previously established over prime fields [Bha14, BHT15]. * For any fixed finite field $\mathbb{K}$, we prove that all locally characterized affine-invariant properties of functions $f: \mathbb{K}^n \to \mathbb{K}$ are testable with one-sided error. The same result was known when $\mathbb{K}$ is prime [BFHHL13] and when the property is linear [KS08]. Moreover, we show that for any fixed finite field $\mathbb{F}$, an affine-invariant property of functions $f: \mathbb{K}^n \to \mathbb{F}$, where $\mathbb{K}$ is a growing field extension over $\mathbb{F}$, is testable if it is locally characterized by constraints of bounded weight.
- Published
- 2015
9. On primitive elements in finite fields of low characteristic
- Author
-
Bhowmick, Abhishek and Lê, Thái Hoàng
- Subjects
Mathematics - Number Theory ,Computer Science - Computational Complexity ,11Lxx ,G.2 - Abstract
We discuss the problem of constructing a small subset of a finite field containing primitive elements of the field. Given a finite field, $\mathbb{F}_{q^n}$, small $q$ and large $n$, we show that the set of all low degree polynomials contains the expected number of primitive elements. The main theorem we prove is a bound for character sums over short intervals in function fields. Our result is unconditional and slightly better than what is known (conditionally under GRH) in the integer case and might be of independent interest.
- Published
- 2014
10. Nonclassical polynomials as a barrier to polynomial lower bounds
- Author
-
Bhowmick, Abhishek and Lovett, Shachar
- Subjects
Computer Science - Computational Complexity ,68Qxx ,F.0 - Abstract
The problem of constructing explicit functions which cannot be approximated by low degree polynomials has been extensively studied in computational complexity, motivated by applications in circuit lower bounds, pseudo-randomness, constructions of Ramsey graphs and locally decodable codes. Still, most of the known lower bounds become trivial for polynomials of super-logarithmic degree. Here, we suggest a new barrier explaining this phenomenon. We show that many of the existing lower bound proof techniques extend to nonclassical polynomials, an extension of classical polynomials which arose in higher order Fourier analysis. Moreover, these techniques are tight for nonclassical polynomials of logarithmic degree.
- Published
- 2014
11. On Low Discrepancy Samplings in Product Spaces of Motion Groups
- Author
-
Bajaj, Chandrajit, Bhowmick, Abhishek, Chattopadhyay, Eshan, and Zuckerman, David
- Subjects
Computer Science - Computational Geometry ,52CXX (Primary) 68Q25, 68W01 (Secondary) ,I.3.5 ,F.2.2 - Abstract
Deterministically generating near-uniform point samplings of the motion groups like SO(3), SE(3) and their n-wise products SO(3)^n, SE(3)^n is fundamental to numerous applications in computational and data sciences. The natural measure of sampling quality is discrepancy. In this work, our main goal is construct low discrepancy deterministic samplings in product spaces of the motion groups. To this end, we develop a novel strategy (using a two-step discrepancy construction) that leads to an almost exponential improvement in size (from the trivial direct product). To the best of our knowledge, this is the first nontrivial construction for SO(3)^n, SE(3)^n and the hypertorus T^n. We also construct new low discrepancy samplings of S^2 and SO(3). The central component in our construction for SO(3) is an explicit construction of N points in S^2 with discrepancy \tilde{\O}(1/\sqrt{N}) with respect to convex sets, matching the bound achieved for the special case of spherical caps in \cite{ABD_12}. We also generalize the discrepancy of Cartesian product sets \cite{Chazelle04thediscrepancy} to the discrepancy of local Cartesian product sets. The tools we develop should be useful in generating low discrepancy samplings of other complicated geometric spaces.
- Published
- 2014
12. Deterministic Extractors for Additive Sources
- Author
-
Bhowmick, Abhishek, Gabizon, Ariel, Lê, Thái Hoàng, and Zuckerman, David
- Subjects
Computer Science - Computational Complexity - Abstract
We propose a new model of a weakly random source that admits randomness extraction. Our model of additive sources includes such natural sources as uniform distributions on arithmetic progressions (APs), generalized arithmetic progressions (GAPs), and Bohr sets, each of which generalizes affine sources. We give an explicit extractor for additive sources with linear min-entropy over both $\mathbb{Z}_p$ and $\mathbb{Z}_p^n$, for large prime $p$, although our results over $\mathbb{Z}_p^n$ require that the source further satisfy a list-decodability condition. As a corollary, we obtain explicit extractors for APs, GAPs, and Bohr sources with linear min-entropy, although again our results over $\mathbb{Z}_p^n$ require the list-decodability condition. We further explore special cases of additive sources. We improve previous constructions of line sources (affine sources of dimension 1), requiring a field of size linear in $n$, rather than $\Omega(n^2)$ by Gabizon and Raz. This beats the non-explicit bound of $\Theta(n \log n)$ obtained by the probabilistic method. We then generalize this result to APs and GAPs.
- Published
- 2014
13. List decoding Reed-Muller codes over small fields
- Author
-
Bhowmick, Abhishek and Lovett, Shachar
- Subjects
Computer Science - Computational Complexity ,Computer Science - Information Theory ,68P30, 11T71 - Abstract
The list decoding problem for a code asks for the maximal radius up to which any ball of that radius contains only a constant number of codewords. The list decoding radius is not well understood even for well studied codes, like Reed-Solomon or Reed-Muller codes. Fix a finite field $\mathbb{F}$. The Reed-Muller code $\mathrm{RM}_{\mathbb{F}}(n,d)$ is defined by $n$-variate degree-$d$ polynomials over $\mathbb{F}$. In this work, we study the list decoding radius of Reed-Muller codes over a constant prime field $\mathbb{F}=\mathbb{F}_p$, constant degree $d$ and large $n$. We show that the list decoding radius is equal to the minimal distance of the code. That is, if we denote by $\delta(d)$ the normalized minimal distance of $\mathrm{RM}_{\mathbb{F}}(n,d)$, then the number of codewords in any ball of radius $\delta(d)-\varepsilon$ is bounded by $c=c(p,d,\varepsilon)$ independent of $n$. This resolves a conjecture of Gopalan-Klivans-Zuckerman [STOC 2008], who among other results proved it in the special case of $\mathbb{F}=\mathbb{F}_2$; and extends the work of Gopalan [FOCS 2010] who proved the conjecture in the case of $d=2$. We also analyse the number of codewords in balls of radius exceeding the minimal distance of the code. For $e \leq d$, we show that the number of codewords of $\mathrm{RM}_{\mathbb{F}}(n,d)$ in a ball of radius $\delta(e) - \varepsilon$ is bounded by $\exp(c \cdot n^{d-e})$, where $c=c(p,d,\varepsilon)$ is independent of $n$. The dependence on $n$ is tight. This extends the work of Kaufman-Lovett-Porat [IEEE Inf. Theory 2012] who proved similar bounds over $\mathbb{F}_2$. The proof relies on several new ingredients: an extension of the Frieze-Kannan weak regularity to general function spaces, higher-order Fourier analysis, and an extension of the Schwartz-Zippel lemma to compositions of polynomials., Comment: fixed a bug in the proof of claim 5.6 (now lemma 5.5)
- Published
- 2014
14. New Lower Bounds for Matching Vector Codes
- Author
-
Bhowmick, Abhishek, Dvir, Zeev, and Lovett, Shachar
- Subjects
Computer Science - Computational Complexity ,Computer Science - Discrete Mathematics ,Mathematics - Combinatorics ,68Q17 - Abstract
A Matching Vector (MV) family modulo $m$ is a pair of ordered lists $U=(u_1,...,u_t)$ and $V=(v_1,...,v_t)$ where $u_i,v_j \in \mathbb{Z}_m^n$ with the following inner product pattern: for any $i$, $< u_i,v_i>=0$, and for any $i \ne j$, $< u_i,v_j> \ne 0$. A MV family is called $q$-restricted if inner products $< u_i,v_j>$ take at most $q$ different values. Our interest in MV families stems from their recent application in the construction of sub-exponential locally decodable codes (LDCs). There, $q$-restricted MV families are used to construct LDCs with $q$ queries, and there is special interest in the regime where $q$ is constant. When $m$ is a prime it is known that such constructions yield codes with exponential block length. However, for composite $m$ the behaviour is dramatically different. A recent work by Efremenko [STOC 2009] (based on an approach initiated by Yekhanin [JACM 2008]) gives the first sub-exponential LDC with constant queries. It is based on a construction of a MV family of super-polynomial size by Grolmusz [Combinatorica 2000] modulo composite $m$. In this work, we prove two lower bounds on the block length of LDCs which are based on black box construction using MV families. When $q$ is constant (or sufficiently small), we prove that such LDCs must have a quadratic block length. When the modulus $m$ is constant (as it is in the construction of Efremenko) we prove a super-polynomial lower bound on the block-length of the LDCs, assuming a well-known conjecture in additive combinatorics, the polynomial Freiman-Ruzsa conjecture over $\mathbb{Z}_m$., Comment: Fixed typos and small bugs
- Published
- 2012
15. Finding top-k similar pairs of objects annotated with terms from an ontology
- Author
-
Bhattacharya, Arnab, Bhowmick, Abhishek, and Singh, Ambuj K.
- Subjects
Computer Science - Databases ,H.2.4 - Abstract
With the growing focus on semantic searches and interpretations, an increasing number of standardized vocabularies and ontologies are being designed and used to describe data. We investigate the querying of objects described by a tree-structured ontology. Specifically, we consider the case of finding the top-k best pairs of objects that have been annotated with terms from such an ontology when the object descriptions are available only at runtime. We consider three distance measures. The first one defines the object distance as the minimum pairwise distance between the sets of terms describing them, and the second one defines the distance as the average pairwise term distance. The third and most useful distance measure, earth mover's distance, finds the best way of matching the terms and computes the distance corresponding to this best matching. We develop lower bounds that can be aggregated progressively and utilize them to speed up the search for top-k object pairs when the earth mover's distance is used. For the minimum pairwise distance, we devise an algorithm that runs in O(D + Tk log k) time, where D is the total information size and T is the total number of terms in the ontology. We also develop a novel best-first search strategy for the average pairwise distance that utilizes lower bounds generated in an ordered manner. Experiments on real and synthetic datasets demonstrate the practicality and scalability of our algorithms., Comment: 17 pages, 13 figures
- Published
- 2010
16. New Bounds for Matching Vector Families
- Author
-
Bhowmick, Abhishek, Dvir, Zeev, and Lovett, Shachar
- Subjects
matching vector families ,restricted modular intersections ,locally decodable codes ,Pure Mathematics ,Computation Theory and Mathematics ,Computation Theory & Mathematics - Abstract
A matching vector (MV) family modulo m is a pair of ordered lists U = (u1,ut) and V = (v1,vt) where ui, vj ∈ ℤnm with the following inner product pattern: for any i, 〈ui, vi〉 = 0, and for any i ≠ j, 〈ui, vj〉 ≠ 0. An MV family is called q-restricted if inner products 〈ui, vj〉 take at most q different values. Our interest in MV families stems from their recent application in the construction of subexponential locally decodable codes (LDCs). There, q-restricted MV families are used to construct LDCs with q queries, and there is special interest in the regime where q is constant. When m is a prime it is known that such constructions yield codes with exponential block length. However, for composite m the behavior is dramatically different. A recent work by Efremenko [SIAM J. Comput., 40 (2011), pp. 1154-1178] (based on an approach initiated by Yekhanin [J. ACM, 55 (2008), pp. 1-16]) gives the first subexponential LDC with constant queries. It is based on a construction of an MV family of superpolynomial size by Grolmusz [Combinatorica, 20 (2000), pp. 71-86] modulo composite m. In this work, we prove two lower bounds on the block length of LDCs which are based on black box construction using MV families. When q is constant (or sufficiently small), we prove that such LDCs must have a quadratic block length. When the modulus m is constant (as it is in the construction of Efremenko) we prove a superpolynomial lower bound on the block-length of the LDCs, assuming a well-known conjecture in additive combinatorics, the polynomial Freiman.Ruzsa conjecture over ℤm.
- Published
- 2014
17. Noiseless Database Privacy
- Author
-
Bhaskar, Raghav, Bhowmick, Abhishek, Goyal, Vipul, Laxman, Srivatsan, Thakurta, Abhradeep, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Lee, Dong Hoon, editor, and Wang, Xiaoyun, editor
- Published
- 2011
- Full Text
- View/download PDF
18. Bounds on the Leakage of the Input’s Distribution in Information-Hiding Protocols
- Author
-
Bhowmick, Abhishek, Palamidessi, Catuscia, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Kaklamanis, Christos, editor, and Nielson, Flemming, editor
- Published
- 2009
- Full Text
- View/download PDF
19. THE ROLE OF WEEKLY MARKET AMONG THE PAUDIBHUYANS OF KEONJHAR DISTRICT ODISHA
- Author
-
Bhowmick, Abhishek, primary
- Published
- 2022
- Full Text
- View/download PDF
20. Finding Top-k Similar Pairs of Objects Annotated with Terms from an Ontology
- Author
-
Bhattacharya, Arnab, primary, Bhowmick, Abhishek, additional, and Singh, Ambuj K., additional
- Published
- 2010
- Full Text
- View/download PDF
21. Bounds on the Leakage of the Input’s Distribution in Information-Hiding Protocols
- Author
-
Bhowmick, Abhishek, primary and Palamidessi, Catuscia, additional
- Published
- 2009
- Full Text
- View/download PDF
22. Statistical Framework for Uncertainty Quantification in Computational Molecular Modeling
- Author
-
Rasheed, Muhibur, primary, Clement, Nathan, additional, Bhowmick, Abhishek, additional, and Bajaj, Chandrajit L., additional
- Published
- 2019
- Full Text
- View/download PDF
23. The List Decoding Radius for Reed–Muller Codes Over Small Fields
- Author
-
Bhowmick, Abhishek, primary and Lovett, Shachar, additional
- Published
- 2018
- Full Text
- View/download PDF
24. On Higher-Order Fourier Analysis over Non-Prime Fields
- Author
-
Bhattacharyya, Arnab, Bhowmick, Abhishek, and Gupta, Chetan
- Subjects
000 Computer science, knowledge, general works ,Computer Science - Abstract
The celebrated Weil bound for character sums says that for any low-degree polynomial P and any additive character chi, either chi(P) is a constant function or it is distributed close to uniform. The goal of higher-order Fourier analysis is to understand the connection between the algebraic and analytic properties of polynomials (and functions, generally) at a more detailed level. For instance, what is the tradeoff between the equidistribution of chi(P) and its "structure"? Previously, most of the work in this area was over fields of prime order. We extend the tools of higher-order Fourier analysis to analyze functions over general finite fields. Let K be a field extension of a prime finite field F_p. Our technical results are: 1. If P: K^n -> K is a polynomial of degree |K|^{-s} for some s > 0 and non-trivial additive character chi, then P is a function of O_{d, s}(1) many non-classical polynomials of weight degree < d. The definition of non-classical polynomials over non-prime fields is one of the contributions of this work. 2. Suppose K and F are of bounded order, and let H be an affine subspace of K^n. Then, if P: K^n -> K is a polynomial of degree d that is sufficiently regular, then (P(x): x in H) is distributed almost as uniformly as possible subject to constraints imposed by the degree of P. Such a theorem was previously known for H an affine subspace over a prime field. The tools of higher-order Fourier analysis have found use in different areas of computer science, including list decoding, algorithmic decomposition and testing. Using our new results, we revisit some of these areas. (i) For any fixed finite field K, we show that the list decoding radius of the generalized Reed Muller code over K equals the minimum distance of the code. (ii) For any fixed finite field K, we give a polynomial time algorithm to decide whether a given polynomial P: K^n -> K can be decomposed as a particular composition of lesser degree polynomials. (iii) For any fixed finite field K, we prove that all locally characterized affine-invariant properties of functions f: K^n -> K are testable with one-sided error.
- Published
- 2016
- Full Text
- View/download PDF
25. A note on character sums in finite fields
- Author
-
Bhowmick, Abhishek, primary, Lê, Thái Hoàng, additional, and Liu, Yu-Ru, additional
- Published
- 2017
- Full Text
- View/download PDF
26. On Higher-Order Fourier Analysis over Non-Prime Fields
- Author
-
Arnab Bhattacharyya and Abhishek Bhowmick and Chetan Gupta, Bhattacharyya, Arnab, Bhowmick, Abhishek, Gupta, Chetan, Arnab Bhattacharyya and Abhishek Bhowmick and Chetan Gupta, Bhattacharyya, Arnab, Bhowmick, Abhishek, and Gupta, Chetan
- Abstract
The celebrated Weil bound for character sums says that for any low-degree polynomial P and any additive character chi, either chi(P) is a constant function or it is distributed close to uniform. The goal of higher-order Fourier analysis is to understand the connection between the algebraic and analytic properties of polynomials (and functions, generally) at a more detailed level. For instance, what is the tradeoff between the equidistribution of chi(P) and its "structure"? Previously, most of the work in this area was over fields of prime order. We extend the tools of higher-order Fourier analysis to analyze functions over general finite fields. Let K be a field extension of a prime finite field F_p. Our technical results are: 1. If P: K^n -> K is a polynomial of degree <= d, and E[chi(P(x))] > |K|^{-s} for some s > 0 and non-trivial additive character chi, then P is a function of O_{d, s}(1) many non-classical polynomials of weight degree < d. The definition of non-classical polynomials over non-prime fields is one of the contributions of this work. 2. Suppose K and F are of bounded order, and let H be an affine subspace of K^n. Then, if P: K^n -> K is a polynomial of degree d that is sufficiently regular, then (P(x): x in H) is distributed almost as uniformly as possible subject to constraints imposed by the degree of P. Such a theorem was previously known for H an affine subspace over a prime field. The tools of higher-order Fourier analysis have found use in different areas of computer science, including list decoding, algorithmic decomposition and testing. Using our new results, we revisit some of these areas. (i) For any fixed finite field K, we show that the list decoding radius of the generalized Reed Muller code over K equals the minimum distance of the code. (ii) For any fixed finite field K, we give a polynomial time algorithm to decide whether a given polynomial P: K^n -> K can be decomposed as a particular composition of lesser degree polynomials. (iii)
- Published
- 2016
- Full Text
- View/download PDF
27. Statistical Framework for Uncertainty Quantification in Computational Molecular Modeling
- Author
-
Rasheed, Muhibur, primary, Clement, Nathan, additional, Bhowmick, Abhishek, additional, and Bajaj, Chandrajit, additional
- Published
- 2016
- Full Text
- View/download PDF
28. Nonclassical Polynomials as a Barrier to Polynomial Lower Bounds
- Author
-
Bhowmick, Abhishek, Lovett, Shachar, Bhowmick, Abhishek, and Lovett, Shachar
- Abstract
The problem of constructing explicit functions which cannot be approximated by low degree polynomials has been extensively studied in computational complexity, motivated by applications in circuit lower bounds, pseudo-randomness, constructions of Ramsey graphs and locally decodable codes. Still, most of the known lower bounds become trivial for polynomials of super-logarithmic degree. Here, we suggest a new barrier explaining this phenomenon. We show that many of the existing lower bound proof techniques extend to nonclassical polynomials, an extension of classical polynomials which arose in higher order Fourier analysis. Moreover, these techniques are tight for nonclassical polynomials of logarithmic degree.
- Published
- 2015
- Full Text
- View/download PDF
29. Nonclassical Polynomials as a Barrier to Polynomial Lower Bounds
- Author
-
Abhishek Bhowmick and Shachar Lovett, Bhowmick, Abhishek, Lovett, Shachar, Abhishek Bhowmick and Shachar Lovett, Bhowmick, Abhishek, and Lovett, Shachar
- Abstract
The problem of constructing explicit functions which cannot be approximated by low degree polynomials has been extensively studied in computational complexity, motivated by applications in circuit lower bounds, pseudo-randomness, constructions of Ramsey graphs and locally decodable codes. Still, most of the known lower bounds become trivial for polynomials of super-logarithmic degree. Here, we suggest a new barrier explaining this phenomenon. We show that many of the existing lower bound proof techniques extend to nonclassical polynomials, an extension of classical polynomials which arose in higher order Fourier analysis. Moreover, these techniques are tight for nonclassical polynomials of logarithmic degree.
- Published
- 2015
- Full Text
- View/download PDF
30. On primitive elements in finite fields of low characteristic
- Author
-
Bhowmick, Abhishek, primary and Lê, Thái Hoàng, additional
- Published
- 2015
- Full Text
- View/download PDF
31. The List Decoding Radius of Reed-Muller Codes over Small Fields
- Author
-
Bhowmick, Abhishek, primary and Lovett, Shachar, additional
- Published
- 2015
- Full Text
- View/download PDF
32. A case for core-assisted bottleneck acceleration in GPUs
- Author
-
Vijaykumar, Nandita, primary, Pekhimenko, Gennady, additional, Jog, Adwait, additional, Bhowmick, Abhishek, additional, Ausavarungnirun, Rachata, additional, Das, Chita, additional, Kandemir, Mahmut, additional, Mowry, Todd C., additional, and Mutlu, Onur, additional
- Published
- 2015
- Full Text
- View/download PDF
33. Deterministic Extractors for Additive Sources
- Author
-
Bhowmick, Abhishek, primary, Gabizon, Ariel, additional, Le, Thái Hoang, additional, and Zuckerman, David, additional
- Published
- 2015
- Full Text
- View/download PDF
34. Bounds on the leakage of the input's distribution in information-hiding protocols
- Author
-
Bhowmick, Abhishek, Palamidessi, Catuscia, Electrical Engineering, Indian Institute of Technology Kanpur (IIT Kanpur), Concurrency, Mobility and Transactions (COMETE), Laboratoire d'informatique de l'École polytechnique [Palaiseau] (LIX), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), and Christos Kaklamanis and Flemming Nielson
- Subjects
TheoryofComputation_MISCELLANEOUS ,[INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR] ,Computer Science::Multimedia ,Computer Science::Cryptography and Security - Abstract
International audience; In information-hiding, an adversary that tries to infer the secret information has a higher probability of success if it knows the distribution on the secrets. We show that if the system leaks probabilistically some information about the secrets, (that is, if there is a probabilistic correlation between the secrets and some observables) then the adversary can approximate such distribution by repeating the observations. More precisely, it can approximate the distribution on the observables by computing their frequencies, and then derive the distribution on the secrets by using the correlation in the inverse direction. We illustrate this method, and then we study the bounds on the approximation error associated with it, for various natural notions of error. As a case study, we apply our results to Crowds, a protocol for anonymous communication.
- Published
- 2008
35. Statistical Framework for Uncertainty Quantification in Computational Molecular Modeling.
- Author
-
Rasheed, Muhibur, Clement, Nathan, Bhowmick, Abhishek, and Bajaj, Chandrajit
- Published
- 2016
- Full Text
- View/download PDF
36. The dirty-block index
- Author
-
Seshadri, Vivek, primary, Bhowmick, Abhishek, additional, Mutlu, Onur, additional, Gibbons, Phillip B., additional, Kozuch, Michael A., additional, and Mowry, Todd C., additional
- Published
- 2014
- Full Text
- View/download PDF
37. A case for Core-Assisted Bottleneck Acceleration in GPUs: Enabling flexible data compression with assist warps.
- Author
-
Vijaykumar, Nandita, Pekhimenko, Gennady, Jog, Adwait, Bhowmick, Abhishek, Ausavarungnirun, Rachata, Das, Chita, Kandemir, Mahmut, Mowry, Todd C., and Mutlu, Onur
- Published
- 2015
- Full Text
- View/download PDF
38. New bounds for matching vector families
- Author
-
Bhowmick, Abhishek, primary, Dvir, Zeev, additional, and Lovett, Shachar, additional
- Published
- 2013
- Full Text
- View/download PDF
39. The dirty-block index.
- Author
-
Seshadri, Vivek, Bhowmick, Abhishek, Mutlu, Onur, Gibbons, Phillip B., Kozuch, Michael A., and Mowry, Todd C.
- Published
- 2014
40. Algebraic and analytic techniques in coding theory
- Author
-
Bhowmick, Abhishek
- Subjects
- Polynomials, Coding theory
- Abstract
Error correcting codes are designed to tackle the problem of reliable trans- mission of data through noisy channels. A major challenge in coding theory is to efficiently recover the original message even when many symbols of the received data have been corrupted. This is called the unique decoding problem of error correcting codes. More precisely, if the user wants to send K bits, the code stretches K bits to N bits to tolerate errors in the N bits. Then the goal is to recover the original K bits of the message. Often, the receiver requires only a certain part of the message. In such cases, analyzing the entire received data (word) becomes prohibitive. The challenge is to design a local decoder which queries only few locations of the received word and outputs the part of the message required. This is known as local decoding of an error correcting code. The unique decoding problem faces a certain combinatorial barrier. That is, there is a limit to the number of errors it can tolerate in order to uniquely identify the correct message. This is called the unique decoding radius. A major open problem is to understand what happens if one allows for errors beyond this threshold. The goal is to design an algorithm that can recover the right message, or possibly a list of messages (preferably a small number). This is referred to as list decoding of an error correcting code. At the core of many such codes lies polynomials. Polynomials play a fundamental role in computer science with important applications in algorithm design, complexity theory, pseudo-randomness and machine learning. In this dissertation, we improve our understanding of well known classes of codes and discover various properties of polynomials. As an additional consequence, we obtain results in a suite of problems in effective algebraic geometry, including Hilbert’s nullstellensatz, ideal membership problem and counting rational points in a variety.
- Published
- 2015
41. Statistical Framework for Uncertainty Quantification in Computational Molecular Modeling.
- Author
-
Rasheed M, Clement N, Bhowmick A, and Bajaj C
- Abstract
As computational modeling, simulation, and predictions are becoming integral parts of biomedical pipelines, it behooves us to emphasize the reliability of the computational protocol. For any reported quantity of interest (QOI), one must also compute and report a measure of the uncertainty or error associated with the QOI. This is especially important in molecular modeling, since in most practical applications the inputs to the computational protocol are often noisy, incomplete, or low-resolution. Unfortunately, currently available modeling tools do not account for uncertainties and their effect on the final QOIs with sufficient rigor. We have developed a statistical framework that expresses the uncertainty of the QOI as the probability that the reported value deviates from the true value by more than some user-defined threshold. First, we provide a theoretical approach where this probability can be bounded using Azuma-Hoeffding like inequalities. Second, we approximate this probability empirically by sampling the space of uncertainties of the input and provide applications of our framework to bound uncertainties of several QOIs commonly used in molecular modeling. Finally, we also present several visualization techniques to effectively and quantitavely visualize the uncertainties: in the input, final QOIs, and also intermediate states.
- Published
- 2016
- Full Text
- View/download PDF
Catalog
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.