Results 791 - 800 of 23787
Abstract not available.
Succinct randomized encodings allow encoding the input $x$ of a time-$t$ uniform computation $M(x)$ in sub-linear time $o(t)$. The resulting encoding $\Tilde{x}$ allows recovering the result of the computation $M(x)$, but hides any other information about $x$. These encodings have powerful applications, including time-lock puzzles, reducing communication in MPC, and bootstrapping advanced encryption schemes.
Until not long ago, the only known constructions were based on indistinguishability obfuscation, and in particular were not based on standard post-quantum assumptions. In terms of efficiency, these constructions' encoding time is $\rm{polylog}(t)$, essentially the best one can hope for. Recently, a new construction was presented based on Circular Learning with Errors, an assumption similar to the one used in fully-homomorphic encryption schemes, and which is widely considered to be post-quantum resistant. However, the encoding efficiency significantly falls behind obfuscation-based scheme and is $\approx \sqrt{t} \cdot s$, where $s$ is the space of the computation.
We construct, under the same assumption, succinct randomized encodings with encoding time $\approx t^{\varepsilon} \cdot s$ for arbitrarily small constant $\varepsilon<1$. Our construction is relatively simple, generic and relies on any laconic function evaluation scheme that satisfies a natural {\em efficiency preservation} property.
Under sub-exponential assumptions, the encoding time can be further reduced to $\approx \sqrt{s}$, but at the account of a huge security loss.
As a corollary, assuming also bounded-space languages that are worst-case hard-to-parallelize, we obtain time-lock puzzles with an arbitrary polynomial gap between encoding and decoding times.
This is a joint work with Nir Bitansky.
When a group acts on a set, it naturally partitions it into orbits, giving rise to orbit problems. These are natural algorithmic problems, as symmetries are central in numerous questions and structures in physics, mathematics, computer science, optimization, and more. Accordingly, it is of high interest to understand their computational complexity. Recently, Bürgisser et al. (2021) gave the first polynomial-time algorithms for orbit problems of torus actions, that is, actions of commutative continuous groups on Euclidean space. In this work, motivated by theoretical and practical applications, we study the computational complexity of robust generalizations of these orbit problems, which amount to approximating the distance of orbits up to a factor gamma. In particular, this allows deciding whether two inputs are approximately in the same orbit or far from being so. On the one hand, we prove the NP-hardness of this problem for gamma=n^(1/loglogn) by reducing the closest vector problem for lattices to it. On the other hand, we describe algorithms for solving this problem for an approximation factor gamma=exp(poly(n)). Our algorithms combine tools from invariant theory and algorithmic lattice theory, and they also provide group elements witnessing the proximity of the given orbits (in contrast to the algebraic algorithms of prior work). We prove that they run in polynomial time if and only if a version of the famous number-theoretic abc-conjecture holds – establishing a new and surprising connection between computational complexity and number theory.
I will review several constructions of generating sets of rational invariants of group actions and examine their orbit separating properties.
We compute the quantum max flow for tensor networks built from simple fixed tensors and show that, in some cases, the value obtained is macroscopically larger than the quantum min cut of the network. In particular, we study in detail the case of the flip tensor amplified by identity operators and compute explicitly the gap between the maximum flow and the cut of the corresponding networks. The talk is based on a joint work with Fulvio Gesmundo, Miao Hu, and Tristan Klein.
Event webpage link: https://events.berkeley.edu/math/event/309097-mathematics-department-colloquium-positive-random
Sponsor(s): Mathematics, Department of
Speaker: Joel A. Tropp, Caltech
On the real line, a random walk that can only move in the positive direction is very unlikely to remain close to its origin. After a fixed number of steps, the left tail has a Gaussian profile, under minimal assumptions. Remarkably, the same phenomenon occurs when we consider a positive random walk on the cone of positive-semidefinite matrices. After a fixed number of steps, the minimum eigenvalue is also described by a Gaussian random matrix model.
This talk introduces a new way to make this intuition rigorous. The methodology provides the solution to an open problem in computational mathematics about sparse random embeddings. The presentation is targeted at a general mathematical audience.
Preprint: https://arxiv.org/abs/2501.16578
Joel A. Tropp, Caltech
Contact Info:
Lin, Lin, linlin@berkeley.edu
Access Coordinator:
Office Administrator, event_accommodation@math.berkeley.edu, 510-642-6550