Study explains Zipf's law using geometric mechanisms from a finite alphabet.
problem Explains Zipf's law in language without relying on linguistic elements.
method Uses the Full Combinatorial Word Model (FCWM) to generate geometric distributions of word lengths.
result Supports predictions of power-law rank-frequency curves, matching various languages.
New method for decomposing vectors into independent components over finite alphabets.
problem Decomposing vectors into independent components without prior generation assumptions.
method Branch and bound search tree algorithm, linear approximations, order permutation.
result Efficiently decomposes the majority of vectors into independent components.
Paper explores using hand gestures to type English letters.
problem Creating easy-to-remember, non-cumbersome gestures for typing.
method Statistical approach to handle randomness in hand movements.
result Achieved 97.33% accuracy with entire English alphabet.
Deep learning uses alphabet frequencies to accurately classify fake news.
problem Classifying fake news from trustworthy news.
method Used deep learning algorithms on alphabet frequencies of text without sequence information.
result Achieved high accuracy (85%) in classifying fake news.
New algorithm for faster feature enumeration over finite fields.
problem Learning k-juntas over finite fields for multi-labeled data.
method Exploits Fourier detection techniques to develop an O(n^0.8k)-time algorithm.
result First non-trivial algorithm for k-juntas over F_q, answering Mossel et al.'s question.
New algorithms reduce rejection sampling complexity for shape-constrained distributions.
problem Generating exact samples from shape-constrained distributions efficiently.
method Sublinear query complexity algorithms for rejection sampling.
result Sublinear complexity algorithms for sampling from shape-constrained distributions.
In this paper we consider the problem of transmitting a continuous alphabet discrete-time source over an AWGN channel. The design of good curves for this purpose relies on geometrical properties of spherical codes and projections of N-dimensional lattices. We propose a constructive scheme based on a set of curves on …
Finite set of Dehn twists describes genus-2 Goeritz group elements.
problem Describing elements of the genus-2 Goeritz group of S3. method Finite generating set of Dehn twists, algorithm to describe elements, complexity measure on reducing spheres.
result Unique description of elements in terms of Dehn twists.
We present some nonparametric methods for graphical modeling. In the discrete case, where the data are binary or drawn from a finite alphabet, Markov random fields are already essentially nonparametric, since the cliques can take only a finite number of values. Continuous data are different. The Gaussian graphical mode…
Study the tradeoff between signal distortion and human perception over finite channels.
problem Characterize the distortion-perception tradeoff for finite channels with arbitrary metrics.
method Solve linear programming problems to compute the distortion-perception function and optimal reconstructions.
result DP function is piecewise linear in the perception index.
Viewing Dehn's algorithm as a rewriting system, we generalise to allow an alphabet containing letters which do not necessarily represent group elements. This extends the class of groups for which the algorithm solves the word problem to include nilpotent groups, many relatively hyperbolic groups including geometrically…
The study optimizes distribution estimation from samples with relative entropy error, adapting to sparse distributions.
problem Estimating discrete distributions with high-probability accuracy in relative entropy.
method Analysis of Laplace estimator and confidence-dependent smoothing techniques, including data-dependent smoothing.
result Optimal high-probability risk bounds for various estimators, including a new data-dependent smoothing method.
New Sauer inequality improves multiclass hypothesis class bounds.
problem Bounding the size of multiclass hypothesis classes.
method Polynomial method and combinatorial parameters (DS, list-DS dimensions).
result Sharp Sauer inequality with optimal polynomial dependence on list size and alphabet size.
Bayesian HMM for protein alignment state estimation.
problem Estimating the MAP state sequence for a Bayesian HMM.
method Training data with Dirichlet priors, iterative algorithms for MAP path estimation.
result Bayesian setup outperforms frequentist estimation in protein alignment.
The task of reconstructing a matrix given a sample of observedentries is known as the matrix completion problem. It arises ina wide range of problems, including recommender systems, collaborativefiltering, dimensionality reduction, image processing, quantum physics or multi-class classificationto name a few. Most works…
New linear algorithms improve ICA over finite fields with lower bounds.
problem Linear Independent Component Analysis over finite fields.
method Greedy algorithm and sub-optimal variant.
result Our algorithms outperform existing methods and reduce overhead as scale increases.
Knots and links are interpreted as homotopy classes of nanowords and nanophrases in an alphabet consisting of 4 letters. Similar results hold for curves on surfaces. We also discuss versions of the Jones link polynomial and the link quandles for nanophrases.
We study the problem of learning overcomplete HMMs---those that have many hidden states but a small output alphabet. Despite having significant practical importance, such HMMs are poorly understood with no known positive or negative results for efficient learning. In this paper, we present several new results---both po…
Robust hypothesis testing designs a test for worst-case distributions using kernel methods.
problem Design a robust test for hypothesis testing under uncertainty sets.
method Data-driven uncertainty sets constructed using kernel mean embeddings and maximum mean discrepancy (MMD). Bayesian and Neyman-Pearson settings investigated.
result Proposed robust kernel tests are exponentially consistent and asymptotically optimal.
Classifies homeomorphism groups of countable Stone spaces up to coarse equivalence.
problem Classifying non-locally compact topological groups using geometric group theory.
method Classification based on coarsely bounded sets and quasi-isometry.
result Groups in the second class are quasi-isometric to the Hamming cube.
A simple text model shows word lengths follow Zipf's law.
problem Understanding word statistics in large language models.
method A non-linguistic model of text with independent symbol draws.
result Word lengths follow a geometric distribution and Zipf's law.
Feature selection aims to select the smallest subset of features for a specified level of performance. The optimal achievable classification performance on a feature subset is summarized by its Receiver Operating Curve (ROC). When infinite data is available, the Neyman- Pearson (NP) design procedure provides the most e…
A scalable framework for continual learning that preserves skills while accelerating progress.
problem Learning new tasks sequentially without forgetting previous ones.
method Two-component network: Knowledge base for previously learned tasks and active column for current task.
result The method achieves faster learning on new tasks while retaining previously learned skills.
RNN model predicts handwritten characters from accelerometer and gyroscope data.
problem Online handwritten character recognition using sensor data.
method RNN-based neural network trained on gyroscope and accelerometer data.
result High accuracy on test data, achieving character prediction.
We discuss a topological approach to words introduced by the author. Words on an arbitrary alphabet are approximated by Gauss words and then studied up to natural modifications inspired by the Reidemeister moves on knot diagrams. This leads us to a notion of homotopy for words. We introduce several homotopy invariants …
The theoretical basis for a candidate variational principle for the information bottleneck (IB) method is formulated within the ambit of the generalized nonadditive statistics of Tsallis. Given a nonadditivity parameter q, the role of the \textit{additive duality} of nonadditive statistics (q∗=2−q) in relating…
Motivation: Proteins are known to undergo conformational changes in the course of their functions. The changes in conformation are often attributable to a small fraction of residues within the protein. Therefore identification of these variable regions is important for an understanding of protein function. Results: We …
Locally private online quantile regression method addresses privacy constraints.
problem Estimating and inferring quantile regression under local differential privacy constraints.
method Developed a finite-alphabet channel where users compute local contributions, apply randomized response, and send reports. A public decoder corrects distortion and reconstructs inputs for averaging.
result Established local privacy, decoder unbiasedness, consistency, asymptotic normality, and inference for scalar contrasts.
Identifies the best-performing algorithm from a set of candidates.
problem Finding the best-performing machine learning algorithm from benchmark performance.
method Subset selection for multinomial distributions, providing asymptotic and finite-sample schemes.
result Significantly improved methods for identifying the best-performing algorithm.
We propose a novel receiver for orthogonal frequency division multiplexing (OFDM) transmissions in impulsive noise environments. Impulsive noise arises in many modern wireless and wireline communication systems, such as Wi-Fi and powerline communications, due to uncoordinated interference that is much stronger than the…
Paper uses EXIT analysis for community detection with side information.
problem Community detection in the presence of side information.
method Imported EXIT method from iterative decoding of error control codes.
result Predicts asymptotic phase transition and residual errors for community detection.
Optimal rates for learning hidden tree structures are determined.
problem Learning hidden tree structures from noisy data.
method Study of the (noisy) information threshold and the Chow-Liu algorithm.
result Optimal rates for structure recovery are inversely proportional to the information threshold squared.
BestChanID identifies the channel with maximal capacity using training sequences.
problem Identifying the channel with maximal capacity among several discrete memoryless channels.
method Formulated as a multi-armed bandit problem, proposed a capacity estimator, and developed gap-elimination algorithms.
result Guaranteed to output the DMC with the largest capacity with a desired confidence.
A two-step approach efficiently selects hyperparameters for FCMs.
problem Efficiently selecting hyperparameters for FCMs in a computationally expensive process.
method Two-step sequential approach: first estimate context length k, then estimate α.
result The proposed method achieves comparable compression performance to exhaustive search but with reduced computational cost.
Paper proposes a fast stochastic algorithm for neural network quantization with error bounds.
problem Error analysis for quantized neural networks with non-convex loss functions and nonlinear activations.
method Greedy path-following mechanism combined with stochastic quantizer.
result Established full-network error bounds for quantized neural networks.
Sparse logistic regression recovers any discrete pairwise graph model.
problem Recovering the Markov graph of discrete pairwise graphical models.
method Maximum conditional log-likelihood with convex optimization.
result The algorithm can recover any arbitrary discrete pairwise graphical model.
Paper improves multi-step chord prediction in jazz music.
problem Chord sequence prediction accuracy is poor in multi-step scenarios.
method Aggregated multi-scale encoder-decoder network architecture.
result Our model outperforms state-of-the-art methods in accuracy and perplexity.
Extends HMM to topological spaces for modeling complex data.
problem Modeling complex, continuous data in infinite-dimensional spaces.
method Use of Onsager-Machlup functional and Cameron-Martin space.
result Demonstrates versatility in identifying sleep states and snowfall patterns.
This study calculates the maximum error of a famous estimation method.
problem Estimating rare items not seen in a sample.
method Characterizes the maximal mean-squared error of the Good-Turing estimator.
result Characterizes the maximal mean-squared error of the Good-Turing estimator.
Study groups formed by words in braid monoid.
problem Invariance properties of braid group presentations.
method Generalized presentations of braid groups and studied their invariance under operations.
result Groups depend only on conjugacy class in braid group under mild hypotheses.
Let Λ be the limit set of a conformal dynamical system, i.e. a Kleinian group acting on either finite- or infinite-dimensional real Hilbert space, a conformal iterated function system, or a rational function. We give an easily expressible sufficient condition, requiring that the limit set is not too much bigger than …
This paper is concerned with jointly recovering n node-variables {xi}1≤i≤n from a collection of pairwise difference measurements. Imagine we acquire a few observations taking the form of xi−xj; the observation pattern is represented by a measurement graph G with an ed…
Visual spoofing bypasses spam filters and plagiarism detection.
problem Vulnerability in spam filters that can be exploited by visually similar but differently encoded characters.
method Replaces characters with visually similar but differently encoded characters from a different alphabet.
result Spammers can create messages that bypass existing spam filters.
A Gauss paragraph is a combinatorial formulation of a generic closed curve with multiple components on some surface. A virtual string is a collection of circles with arrows that represent the crossings of such a curve. Every closed curve has an underlying virtual string and every virtual string has an underlying Gauss …
This primer explains diffusion models in general state spaces.
problem Diffusion models in general state spaces are not well-introduced.
method Develops discrete-time and continuous-time views of diffusion models, deriving Fokker-Planck and master equations.
result Unified understanding of diffusion models across continuous and discrete domains.
We consider the problem of predicting the next observation given a sequence of past observations, and consider the extent to which accurate prediction requires complex algorithms that explicitly leverage long-range dependencies. Perhaps surprisingly, our positive results show that for a broad class of sequences, there …
We consider the problem of the combinatorial computation of the first Chern class of a circle bundle. N.Mnev found such a formula in terms of canonical shellings. It represents certain invariant of a triangulation computed by analyzing cyclic word in 3-character alphabet associated to the bundle. This curvature is a ki…
Bayesian sequence prediction is a simple technique for predicting future symbols sampled from an unknown measure on infinite sequences over a countable alphabet. While strong bounds on the expected cumulative error are known, there are only limited results on the distribution of this error. We prove tight high-probabil…