Results 801 - 810 of 23794
Unclonable cryptography is an emerging area in quantum cryptography that leverages the no-cloning principle of quantum mechanics to achieve novel primitives that are impossible to achieve classically. In this talk, I will discuss new variants of program obfuscation that are tailored for designing unclonable cryptographic primitives. In addition, I will also discuss the important role program obfuscation, and in particular indistinguishability obfuscation, has played in expanding the feasibility landscape of unclonable cryptography.
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
In this talk, we introduce a definition of the Fenchel conjugate and Fenchel biconjugate on Hadamard manifolds based on the tangent bundle. Our definition overcomes the drawback that the conjugate depends on the choice of a specific point on the manifold, as previous definitions required. On the other hand, this new definition retains properties known to hold in the Euclidean setting and even provides a broader interpretation of the Fenchel conjugate in that case. Most notably, our definition yields a Fenchel–Moreau theorem for geodesically convex, proper, lower semicontinuous functions. In addition, this framework allows us to develop a theory of separation of convex sets on Hadamard manifolds, leading to a strict separation theorem.
Representation theoretic multiplicities are subject to major 90-year old problems in algebraic combinatorics. More recently they have appeared as key quantities in the search for computational lower bounds and separation of complexity classes (like VP vs VNP) through methods of geometric complexity theory.
The multiplicities include Littlewood-Richardson, Kronecker and plethysm coefficients which guide how compositions or tensor products of irreducible S_n or GL_n representations decompose into irreducibles. No explicit efficient formulas are known for either, and for the last two not even a positive combinatorial formula (interpretation) is known.
This poses the natural question of what the complexity of computing them is.
In this talk we will introduce the quantities, their background story and importance and discuss recent results on their computational complexity and efficient algorithms in certain cases, both classical and quantum.
In quantum state learning, one is given samples from a quantum state, and the goal is to output an estimate which is close to the quantum state. Quantum state learning is a fundamental problem in both theory and practice, and the last 10 years have seen substantial progress in the design of sample-optimal algorithms for this task.
In this talk, I will give a survey of recent results in this area, with a focus on a recent set of unbiased estimators for quantum state learning which I have developed with my collaborators. These unbiased estimators have allowed us to give a unified and conceptually simpler framework for achieving optimal sample complexities for a number of important quantum state learning applications.
Based on joint work with Angelos Pelecanos, Thilo Scharnhorst, Jack Spilecki, Ewin Tang, and Mark Zhandry.