We initiate the study of a new notion of adversarial loss which we call distributional adversarial loss. In this notion, we assume for each original example, the allowed adversarial perturbation set is a family of distributions, and the adversarial loss over each example is the maximum loss over all the associated distributions. The goal is to minimize the overall adversarial loss. We show sample complexity bounds in the PAC-learning setting for our notion of adversarial loss. Our notion of adversarial loss contrasts the prior work on robust learning that considers a set of points, not distributions, as the perturbation set of each clean example. As an application of our approach, we show how to unify the two lines of work on randomized smoothing and robust learning in the PAC-learning setting and derive sample complexity bounds for randomized smoothing methods. Furthermore, we investigate the role of randomness in achieving robustness against adversarial attacks. We show a general derandomization technique that preserves the extent of a randomized classifier’s robustness against adversarial attacks and show its effectiveness empirically.

We investigate the concept of algorithmic replicability introduced by Impagliazzo et al.(2022) in an online setting. In our model, the input sequence received by the online learner is generated from time-varying distributions chosen by an adversary (obliviously). Our objective is to design low-regret online algorithms that, with high probability, produce the \emph{exact same sequence} of actions when run on two independently sampled input sequences generated as described above. We refer to such algorithms as adversarially replicable. Previous works explored replicability in the online setting under inputs generated independently from a fixed distribution; we term this notion as iid-replicability. Our model generalizes to capture both adversarial and iid input sequences, as well as their mixtures, which can be modeled by setting certain distributions as point-masses. We demonstrate adversarially replicable online learning algorithms for online linear optimization and the experts problem that achieve sub-linear regret. Additionally, we propose a general framework for converting an online learner into an adversarially replicable one within our setting, bounding the new regret in terms of the original algorithm’s regret. We also present a nearly optimal (in terms of regret) iid-replicable online algorithm for the experts problem, highlighting the distinction between the iid and adversarial notions of replicability. Finally, we establish lower bounds on the regret (in terms of the replicability parameter and time) that any replicable online algorithm must incur.

Average Treatment Effect (ATE) estimation is a well-studied problem in causal inference. However, it does not necessarily capture the heterogeneity in the data, and several approaches have been proposed to tackle the issue, including estimating the Quantile Treatment Effects. In the finite population setting containing $n$ individuals, with treatment and control values denoted by the potential outcome vectors $\mathbf{a}, \mathbf{b}$, much of the prior work focused on estimating median$(\mathbf{a}) -$ median$(\mathbf{b})$, as it is easier to estimate than the desired estimand of median$(\mathbf{a-b})$, called the Median Treatment Effect (MTE). In this work, we argue that MTE is not estimable and detail a novel notion of approximation that relies on the sorted order of the values in $\mathbf{a-b}$: we approximate the median by a value whose quantiles in $\mathbf{a-b}$ are close to $0.5$ (median). Next, we identify a quantity called \emph{variability} that exactly captures the complexity of MTE estimation. Using this, we establish that when potential outcomes take values in the set $\{0,1,\ldots,k-1\}$ the worst-case (over inputs $\mathbf{a,b}$) optimal (over algorithms) approximation factor of the MTE is $\frac{1}{2}\cdot \frac{2k-3}{2k-1}$. Further, by drawing connections to the notions of instance-optimality studied in theoretical computer science, we show that \emph{every} algorithm for estimating the MTE obtains an approximation error that is no better than the error of an algorithm that computes variability, on roughly a per input basis: hence, variability leads to an almost instance optimal approximation algorithm for estimating the MTE. Finally, we provide a simple linear time algorithm for computing the variability exactly. Unlike much prior works, a particular highlight of our work is that we make no assumptions about how the potential outcome vectors are generated or how they are correlated, except that the potential outcome values are $k$-ary, i.e., take one of $k$ discrete values $\{0,1,\ldots,k-1\}$.

A subset$\mathcal{C} \subseteq\{0,1,2\}^n$is said to be a trifferent code (of block length$n$) if for every three distinct codewords$x, y, z \in \mathcal{C}$, there is a coordinate$i \in\{1,2, \ldots, n\}$where they all differ, that is,$\{x(i), y(i), z(i)\}=\{0,1,2\}$. Let$T(n)$denote the size of the largest trifferent code of block length$n$. Understanding the asymptotic behavior of$T(n)$is closely related to determining the zero-error capacity of the (3/2)-channel defined by Elias [Eli88], and is a longstanding open problem in the area. Elias had shown that$T(n) \leq 2 \times(3 / 2)^n$and prior to our work the best upper bound was$T(n) \leq 0.6937 \times(3 / 2)^n$due to Kurz [Kur24]. We improve this bound to$T(n) \leq c \times n^{-2 / 5} \times(3 / 2)^n$where$c$is an absolute constant.

The multiplicity Schwartz-Zippel lemma bounds the total multiplicity of zeroes of a multivariate polynomial on a product set. This lemma motivates the multiplicity codes of Kopparty, Saraf and Yekhanin [J. ACM, 2014], who showed how to use this lemma to construct high-rate locally-decodable codes. However, the algorithmic results about these codes crucially rely on the fact that the polynomials are evaluated on a vector space and not an arbitrary product set. In this work, we show how to decode multivariate multiplicity codes of large multiplicities in polynomial time over finite product sets (over fields of large characteristic and zero characteristic). Previously such decoding algorithms were not known even for a positive fraction of errors. In contrast, our work goes all the way to the distance of the code and in particular exceeds both the unique-decoding bound and the Johnson radius. For errors exceeding the Johnson radius, even combinatorial list-decodablity of these codes was not known. Our algorithm is an application of the classical polynomial method directly to the multivariate setting. In particular, we do not rely on a reduction from the multivariate to the univariate case as is typical of many of the existing results on decoding codes based on multivariate polynomials. However, a vanilla application of the polynomial method in the multivariate setting does not yield a polynomial upper bound on the list size. We obtain a polynomial bound on the list size by taking an alternative view of multivariate multiplicity codes. In this view, we glue all the partial derivatives of the same order together using a fresh set$\mathbf {z}$of variables. We then apply the polynomial method by viewing this as a problem over the field$\mathbb {F} (\mathbf {z})$of rational functions in$\mathbf {z}$.

In this work, we present an abstract framework for some algebraic error-correcting codes with the aim of capturing codes that are list-decodable to capacity, along with their decoding algorithms. In the polynomial ideal framework, a code is specified by some ideals in a polynomial ring, messages are polynomials and the encoding of a message polynomial is the collection of residues of that polynomial modulo the ideals. We present an alternate way of viewing this class of codes in terms of linear operators, and show that this alternate view makes their algorithmic list-decodability amenable to analysis. Our framework leads to a new class of codes that we call affine Folded Reed-Solomon codes (which are themselves a special case of the broader class we explore). These codes are common generalizations of the well-studied Folded Reed-Solomon codes and Univariate Multiplicity codes as well as the less-studied Additive Folded Reed-Solomon codes, and lead to a large family of codes that were not previously known/studied. More significantly our framework also captures the algorithmic list-decodability of the constituent codes. Specifically, we present a unified view of the decoding algorithm for ideal-theoretic codes and show that the decodability reduces to the analysis of the distance of some related codes. We show that a good bound on this distance leads to a capacity-achieving performance of the underlying code, providing a unifying explanation of known capacity-achieving results. In the specific case of affine Folded Reed-Solomon codes, our framework shows that they are efficiently list-decodable up to capacity (for appropriate setting of the parameters), thereby unifying the previous results for Folded Reed-Solomon, Multiplicity and Additive Folded Reed-Solomon codes.

The multiplicity Schwartz-Zippel lemma asserts that over a field, a low-degree polynomial cannot vanish with high multiplicity very often on a sufficiently large product set. Since its discovery in a work of Dvir, Kopparty, Saraf and Sudan [DKSS13], the lemma has found numerous applications in both math and computer science; in particular, in the definition and properties of multiplicity codes by Kopparty, Saraf and Yekhanin [KSY14]. In this work, we show how to algorithmize the multiplicity Schwartz-Zippel lemma for arbitrary product sets over any field. In other words, we give an efficient algorithm for unique decoding of multivariate multiplicity codes from half their minimum distance on arbitrary product sets over all fields. Previously, such an algorithm was known either when the underlying product set had a nice algebraic structure (for instance, was a subfield) [Kop15] or when the underlying field had large (or zero) characteristic, the multiplicity parameter was sufficiently large and the multiplicity code had distance bounded away from 1 [BHKS21b]. In particular, even unique decoding of bivariate multiplicity codes with multiplicity two from half their minimum distance was not known over arbitrary product sets over any field. Our algorithm builds upon a result of Kim & Kopparty [KK17] who gave an algorithmic version of the Schwartz-Zippel lemma (without multiplicities) or equivalently, an efficient algorithm for unique decoding of Reed-Muller codes over arbitrary product sets. We introduce a refined notion of distance based on the multiplicity Schwartz-Zippel lemma and design a unique decoding algorithm for this distance measure. On the way, we give an alternate analysis of Forney's classical generalized minimum distance decoder that might be of independent interest. * The full version of the paper which includes the missing proofs can be accessed at [BHKS21a]. Research of the first, second and fourth authors supported by the Department of Atomic Energy, Government of India, under project 12-R&D-TFR-5.01-0500. This work was done while the first author was at TIFR, where he was supported in part by the Google PhD Fellowship and at the Simons Institute for the Theory of Computing where he was supported by the Simons-Berkeley Postdoctoral Fellowship. Research of the second author supported in part by the Swarnajayanti Fellowship.

In the financial market, Bitcoin analytics has gained lots of attention due to its high-risk high-reward nature. It is interesting to find better techniques to analyze and predict the Bitcoin price change. In this paper, we propose Bitcoin Evolution Analytics, which aims to predict the Bitcoin price change after one hour as Bearish or Bullish. For the prediction, the approach combines the Sentiment analysis and the Technical indicators. For Sentiment analysis of tweets related to Bitcoin, the approach uses three Natural Language Processing (NLP) libraries, namely VADER, FinBERT, and TextBlob, which generated eight different sentiment scores. For Technical indicators, the approach used three features of Bitcoin: User Sentiment Score, Aroon Indicators, and Accumulation/Distribution Line Indicators. We represented all these features of Bitcoin Data over time, which created a novel Bitcoin State Series. To predict the price change of the next hour as Bearish or Bullish, we built the state series for each hour of continuous 13 months (March 2021 - March 2022). To find the most reliable set of features, we have trained 27 ML models. For each feature set, we compared the average and maximum of the accuracies and f-measures. The results of our experiment show that considering the followers of the user as the "weight" of the sentiment gives a more accurate prediction. We found that a combination of Sentiment Analysis and Technical Indicators performs better than using only Sentiment Analysis.

We study the following natural question on random sets of points in 𝔽₂^m: Given a random set of k points Z = {z₁, z₂, … , z_k} ⊆ 𝔽₂^m, what is the dimension of the space of degree at most r multilinear polynomials that vanish on all points in Z? We show that, for r ≤ γ m (where γ > 0 is a small, absolute constant) and k = (1-ε)⋅binom(m, ≤ r) for any constant ε > 0, the space of degree at most r multilinear polynomials vanishing on a random set Z = {z_1,…, z_k} has dimension exactly binom(m, ≤ r) - k with probability 1 - o(1). This bound shows that random sets have a much smaller space of degree at most r multilinear polynomials vanishing on them, compared to the worst-case bound (due to Wei (IEEE Trans. Inform. Theory, 1991)) of binom(m, ≤ r) - binom(log₂ k, ≤ r) ≫ binom(m, ≤ r) - k. Using this bound, we show that high-degree Reed-Muller codes (RM(m,d) with d > (1-γ) m) "achieve capacity" under the Binary Erasure Channel in the sense that, for any ε > 0, we can recover from (1-ε)⋅binom(m, ≤ m-d-1) random erasures with probability 1 - o(1). This also implies that RM(m,d) is also efficiently decodable from ≈ binom(m, ≤ m-(d/2)) random errors for the same range of parameters.

We present a randomized algorithm that takes as input an undirected $n$-vertex graph $G$ with maximum degree $\Delta$ and an integer $k > 3\Delta$ and returns a random proper $k$-coloring of $G$. The distribution of the coloring is perfectly uniform over the set of all proper $k$-colorings; the expected running time of the algorithm is ${poly}(k,n)=\widetilde{O}(n\Delta^2\cdot \log(k))$. This improves upon a result of Huber [ Proceedings of the $30$th ACM Symposium on Theory of Computing (STOC), 1998, pp. 31--40], who obtained a polynomial time perfect sampling algorithm for $k>\Delta^2+2\Delta$. Prior to our work, no algorithm with expected running time ${poly}(k,n)$ was known to guarantee perfectly sampling with a subquadratic number of colors in general. Our algorithm (like several other perfect sampling algorithms including Huber's) is based on the coupling from the past method. Inspired by the bounding chain approach, pioneered independently by Huber (STOC 1998) and Häggström and Nelander [ Scand. J. Stat., 26 (1999), pp. 395--411], we employ a novel bounding chain to derive our result for the graph coloring problem.

Let$\mathcal {X}= \{x_{1},x_{2},\ldots, x_{q}\}$and let$n(m,q,\ell)$be the smallest$n$for which there is a code$C \subseteq \mathcal {X} ^{n}$of$m$elements such that for every list$w_{1}, w_{2}, \ldots, w_{\ell +1}$of distinct codewords from$C$, there is a coordinate$j \in [n]$such that$\{w_{1}[j], w_{2}[j], \ldots, w_{\ell +1}[j]\} = \mathcal {X}$. We show that there is a constant$A>0$such that for$\epsilon < 1/5$, for all large$q$and large enough$m$($m>q^{5}$), we have$n(m,q, \lceil \epsilon q\ln {q}\rceil) \geq \exp {(Aq^{1-5\epsilon })}\log _{2}{m}$. This bound has consequences for the zero-error list-decoding capacity of the$q/(q-1)$channel studied by Elias (1988). Our result implies that for$A$and$\epsilon $as above, the zero-error list-decoding capacity of the$q/(q-1)$channel with list-size$\epsilon q\ln {q}$is at most$\exp (-Aq^{1-5\epsilon })$, that is, it falls exponentially as$q$increases. This confirms a conjecture of Chakrabortyet al.(2006).

In this work, we present an abstract framework for some algebraic error-correcting codes with the aim of capturing codes that are list-decodable to capacity, along with their decoding algorithm. In the polynomial ideal framework, a code is specified by some ideals in a polynomial ring, messages are polynomials and their encoding is the residue modulo the ideals. We present an alternate way of viewing this class of codes in terms of linear operators, and show that this alternate view makes their algorithmic list-decodability amenable to analysis. Our framework leads to a new class of codes that we call affine Folded Reed-Solomon codes (which are themselves a special case of the broader class we explore). These codes are common generalizations of the well-studied Folded Reed-Solomon codes and Multiplicity codes, while also capturing the less-studied Additive Folded Reed-Solomon codes as well as a large family of codes that were not previously known/studied. More significantly our framework also captures the algorithmic list-decodability of the constituent codes. Specifically, we present a unified view of the decoding algorithm for ideal theoretic codes and show that the decodability reduces to the analysis of the distance of some related codes. We show that good bounds on this distance lead to capacity-achieving performance of the underlying code, providing a unifying explanation of known capacity-achieving results. In the specific case of affine Folded Reed-Solomon codes, our framework shows that they are list-decodable up to capacity (for appropriate setting of the parameters), thereby unifying the previous results for Folded Reed-Solomon, Multiplicity and Additive Folded Reed-Solomon codes.

The multiplicity Schwartz-Zippel lemma bounds the total multiplicity of zeroes of a multivariate polynomial on a product set. This lemma motivates the multiplicity codes of Kopparty, Saraf and Yekhanin [J. ACM, 2014], who showed how to use this lemma to construct high-rate locally-decodable codes. However, the algorithmic results about these codes crucially rely on the fact that the polynomials are evaluated on a vector space and not an arbitrary product set.

We present a randomized algorithm that takes as input an undirected n-vertex graph G with maximum degree Δ and an integer k > 3Δ, and returns a random proper k-coloring of G. The distribution of the coloring is perfectly uniform over the set of all proper k-colorings; the expected running time of the algorithm is poly(k,n)=O(nΔ2· log(k)). This improves upon a result of Huber (STOC 1998) who obtained a polynomial time perfect sampling algorithm for k>Δ2+2Δ. Prior to our work, no algorithm with expected running time poly(k,n) was known to guarantee perfectly sampling with sub-quadratic number of colors in general.

We consider the problem of determining the zero-error list-decoding capacity of the q/(q-1) channel studied by Elias (1988). The q/(q-1) channel has input and output alphabet consisting of q symbols, say, X={x1, x2, ..., xq}; when the channel receives an input x ∈ X, it outputs a symbol other than x itself. Let n(m, q, ℓ) be the smallest n for which there is a code C ⊆ Xnof m elements such that for every list w1, w2,..., wℓ+1of distinct code-words from C, there is a coordinate j ∈ [n] that satisfies {w1[j], w2[j],..., wℓ+1[j]}=X. We show that for all constants α ≥ 1, we have n(m, q, αq)=exp(Ω(q)) log m. The lower bound obtained by Fredman and Komlós (1984) for perfect hashing implies that n(m, q, q-1)=exp(Ω(q)) log m; similarly, the lower bound obtained by Körner (1986) for nearly-perfect hashing implies that n(m, q, q)=exp(Ω(q)) log m. These results show that the zero-error list-decoding capacity of the q/(q-1) channel with lists of size at most q is exponentially small. Extending these bounds, Chakraborty et al. (2006) showed that the capacity remains exponentially small even if the list size is allowed to be as large as 1.58q. Our result implies that the zero-error list-decoding capacity of the q/(q-1) with list size αq (for every constant α ≥ 1) channel is exponentially small in q.