We introduce a general framework to design and analyze algorithms for the problem of testing homomorphisms between finite groups in the low-soundness regime. In this regime, we give the first constant-query tests for various families of groups. These include tests for: (i) homomorphisms between arbitrary cyclic groups, (ii) homomorphisms between any finite group and $\mathbb{Z}_p$, (iii) automorphisms of dihedral and symmetric groups, (iv) inner automorphisms of non-abelian finite simple groups and extraspecial groups, and (v) testing linear characters of $\mathrm{GL}_n(\mathbb{F}_q)$, and finite-dimensional Lie algebras over $\mathbb{F}_q$. We also recover the result of Kiwi [TCS'03] for testing homomorphisms between $\mathbb{F}_q^n$ and $\mathbb{F}_q$. Prior to this work, such tests were only known for abelian groups with a constant maximal order (such as $\mathbb{F}_q^n$). No tests were known for non-abelian groups. As an additional corollary, our framework gives combinatorial list decoding bounds for cyclic groups with list size dependence of $O(\varepsilon^{-2})$ (for agreement parameter $\varepsilon$). This improves upon the currently best-known bound of $O(\varepsilon^{-105})$ due to Dinur, Grigorescu, Kopparty, and Sudan [STOC'08], and Guo and Sudan [RANDOM'14].

Random walks in distributed networks are useful primitives with numerous applications. In this paper, we focus on efficient distributed algorithms for performing random walks and their application to generating random spanning trees (RST) in arbitrary networks. The goal is to minimize the number of rounds required to output the positions of vertices in a random walk starting from a given source and to generate an RST in the standard CONGEST model.

We present the first sublinear-in-n round algorithm for sampling an approximately uniform spanning tree of an n-vertex graph in the CongestedClique model of distributed computing. In particular, our algorithm requires Õ (n0.657) rounds for sampling a spanning tree within total variation distance 1/nc, for arbitrary constant c > 0, from the uniform distribution. More precisely, our algorithm requires Õ (n1/2+α) rounds, where O (nα) is the running time of matrix multiplication in the CongestedClique model (currently α = 1-2/ω = 0.157, where ω is the sequential matrix multiplication time exponent). We can adapt our algorithm to give exact rather than approximate samples, but with a larger, though still o (n), runtime of Õ(n2/3+α) = O(n0.824).

Abstract. We give an efficient algorithm that transforms any bounded degree expander graph into another that achieves almost-optimal (namely, near-quadratic, [Formula: see text]) trade-off between (any desired) spectral expansion [Formula: see text] and degree [Formula: see text]. Furthermore, the algorithm is local: Every vertex in the new graph can compute its new neighbors as a subset of its original neighborhood of radius [Formula: see text]. The optimal quadratic trade-off is known as the Ramanujan bound, so our construction gives almost-Ramanujan expanders from arbitrary expanders. The locality of the transformation preserves structural properties of the original graph and thus has many consequences. Applied to Cayley graphs, our transformation shows that any expanding finite group has almost-Ramanujan expanding generators. Similarly, one can obtain almost-optimal explicit constructions of quantum expanders, dimension expanders, monotone expanders, etc., from existing (suboptimal) constructions of such objects. Another consequence is a “derandomized” random walk on the original (suboptimal) expander with almost-optimal convergence rate. Our transformation also applies when the degree is not bounded or the expansion is not constant. We obtain our results by a generalization of Ta-Shma’s technique in his breakthrough paper [ STOC 2017 : Proceedings of the 49 th Annual ACM SIGACT Symposium on Theory of Computing, ACM, 2017, pp. 238–251], used to obtain explicit almost-optimal binary codes. Specifically, our spectral amplification extends Ta-Shma’s analysis of bias amplification from scalars to matrices of arbitrary dimension in a very natural way. Curiously, while Ta-Shma’s explicit bias amplification derandomizes a well-known probabilistic argument (underlying the Gilbert–Varshamov bound), there seems to be no known probabilistic (or other existential) way of achieving our explicit operator-valued spectral amplification.

Random walks in expander graphs and their various derandomizations (e.g., replacement/zig-zag product) are invaluable tools from pseudorandomness. Recently, Ta-Shma used$s$-wide replacement walks in his breakthrough construction of a binary linear code almost matching the Gilbert-Varshamov bound (STOC 2017). Ta-Shma’s original analysis was entirely linear algebraic, and subsequent developments have inherited this viewpoint. In this work, we rederive Ta-Shma’s analysis from a combinatorial point of view using repeated application of the expander mixing lemma. We hope that this alternate perspective will yield a better understanding of Ta-Shma’s construction. As an additional application of our techniques, we give an alternate proof of the expander hitting set lemma.

We give an efficient algorithm for list-decoding the binary code by Ta-Shma (STOC 2017) to the Johnson Bound. Ta-Shma’s code has distance $\frac{1-\varepsilon}{2}$ and rate $\Omega\left(\varepsilon^{2+o(1)}\right)$ and thus it almost achieves the Gilbert-Varshamov bound. Johnson bound states that such codes are combinatorially list decodable upto $\frac{1-\rho}{2}-$ fraction of errors as long as $\rho \geq \sqrt{\varepsilon}$. We give a polynomial time decoding algorithm that nearly achieves this bound. Thus our result implies the only known binary code that simultaneously nearly achieves both the Gilbert-Varshamov and the Johnson bounds. Our decoding algorithm is based on semidefinite programming hierarchies and includes a new rounding step which might be of independent interest.

We give an efficient algorithm that transforms any bounded degree expander graph into another that achieves almost optimal (namely, near-quadratic, $d\leq 1/\lambda^{2+o(1)}$) trade-off between (any desired) spectral expansion $\lambda$ and degree d. Furthermore, the algorithm is local: every vertex can compute its new neighbors as a subset of its original neighborhood of radius $O(\log(1/\lambda))$. The optimal quadratic trade-off is known as the Ramanujan bound, so our construction gives almost Ramanujan expanders from arbitrary expanders. The locality of the transformation preserves structural properties of the original graph, and thus has many consequences. Applied to Cayley graphs, our transformation shows that any expanding finite group has almost Ramanujan expanding generators. Similarly, one can obtain almost optimal explicit constructions of quantum expanders, dimension expanders, monotone expanders, etc., from existing (suboptimal) constructions of such objects. Another consequence is a “derandomized” random walk on the original (suboptimal) expander with almost optimal convergence rate. Our transformation also applies when the degree is not bounded or the expansion is not constant. We obtain our results by a generalization of Ta-Shma’s technique in his breakthrough paper [STOC 2017], used to obtain explicit almost optimal binary codes. Specifically, our spectral amplification extends Ta-Shma’s analysis of bias amplification from scalars to matrices of arbitrary dimension in a very natural way. Curiously, while Ta-Shma’s explicit bias amplification derandomizes a well-known probabilistic argument (underlying the Gilbert-Varshamov bound), there seems to be no known probabilistic (or other existential) way of achieving our explicit (high-dimensional”) spectral amplification.

In this paper, we show the mixing of three-term progressions (x, xg, xg²) in every finite quasirandom group, fully answering a question of Gowers. More precisely, we show that for any D-quasirandom group G and any three sets A₁, A₂, A₃ ⊂ G, we have |Pr_{x,y∼ G}[x ∈ A₁, xy ∈ A₂, xy² ∈ A₃] - ∏_{i = 1}³ Pr_{x∼ G}[x ∈ A_i]| ≤ (2/(√{D)})^{1/4}. Prior to this, Tao answered this question when the underlying quasirandom group is SL_{d}(𝔽_q). Subsequently, Peluse extended the result to all non-abelian finite simple groups. In this work, we show that a slight modification of Peluse’s argument is sufficient to fully resolve Gowers' quasirandom conjecture for 3-term progressions. Surprisingly, unlike the proofs of Tao and Peluse, our proof is elementary and only uses basic facts from non-abelian Fourier analysis.

Minimization of labeling effort for person re-identification in camera networks is an important problem as most of the existing popular methods are supervised and they require large amount of manual annotations, acquiring which is a tedious job. In this work, we focus on this labeling effort minimization problem and approach it as a subset selection task where the objective is to select an optimal subset of image-pairs for labeling without compromising performance. Towards this goal, our proposed scheme first represents any camera network (with k number of cameras) as an edge weighted complete k-partite graph where each vertex denotes a person and similarity scores between persons are used as edge-weights. Then in the second stage, our algorithm selects an optimal subset of pairs by solving a triangle free subgraph maximization problem on the k-partite graph. This sub-graph weight maximization problem is NP-hard (at least for k = 4) which means for large datasets the optimization problem becomes intractable. In order to make our framework scalable, we propose two polynomial time approximately-optimal algorithms. The first algorithm is a 1/2-approximation algorithm which runs in linear time in the number of edges. The second algorithm is a greedy algorithm with sub-quadratic (in number of edges) time-complexity. Experiments on three state-of-the-art datasets depict that the proposed approach requires on an average only 8-15% manually labeled pairs in order to achieve the performance when all the pairs are manually annotated.

Deep neural networks are efficient learning machines which leverage upon a large amount of manually labeled data for learning discriminative features. However, acquiring substantial amount of supervised data, especially for videos can be a tedious job across various computer vision tasks. This necessitates learning of visual features from videos in an unsupervised setting. In this paper, we propose a computationally simple, yet effective, framework to learn spatio-temporal feature embedding from unlabeled videos. We train a Convolutional 3D Siamese network using positive and negative pairs mined from videos under certain probabilistic assumptions. Experimental results on three datasets demonstrate that our proposed framework is able to learn weights which can be used for same as well as cross dataset and tasks.