Arrow Research search

Author name cluster

Umesh V. Vazirani

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

42 papers
2 author rows

Possible papers

42

STOC Conference 2023 Conference Paper

A Polynomial-Time Classical Algorithm for Noisy Random Circuit Sampling

  • Dorit Aharonov
  • Xun Gao
  • Zeph Landau
  • Yunchao Liu 0002
  • Umesh V. Vazirani

We give a polynomial time classical algorithm for sampling from the output distribution of a noisy random quantum circuit in the regime of anti-concentration to within inverse polynomial total variation distance. The algorithm is based on a quantum analog of noise induced low degree approximations of Boolean functions, which takes the form of the truncation of a Feynman path integral in the Pauli basis.

Details

STOC Conference 2022 Conference Paper

Deniable encryption in a Quantum world

  • Andrea Coladangelo
  • Shafi Goldwasser
  • Umesh V. Vazirani

(Sender-)Deniable encryption provides a very strong privacy guarantee: a sender who is coerced by an attacker into “opening” their ciphertext after-the-fact is able to generate “fake” local random choices that are consistent with any plaintext of their choice. The only known fully-efficient constructions of public-key deniable encryption rely on indistinguishability obfuscation (iO) (which currently can only be based on sub-exponential hardness assumptions). In this work, we study (sender-)deniable encryption in a setting where the encryption procedure is a quantum algorithm, but the ciphertext is classical. First, we propose a quantum analog of the classical definition in this setting. We give a fully efficient construction satisfying this definition, assuming the quantum hardness of the Learning with Errors (LWE) problem. Second, we show that quantum computation unlocks a fundamentally stronger form of deniable encryption, which we call perfect unexplainability . The primitive at the heart of unexplainability is a quantum computation for which there is provably no efficient way, such as exhibiting the “history of the computation,” to establish that the output was indeed the result of the computation. We give a construction which is secure in the random oracle model , assuming the quantum hardness of LWE. Crucially, this notion implies a form of protection against coercion “before-the-fact”, a property that is impossible to achieve classically.

Details

STOC Conference 2021 Conference Paper

(Sub)Exponential advantage of adiabatic Quantum computation with no sign problem

  • András Gilyén
  • Matthew B. Hastings
  • Umesh V. Vazirani

We demonstrate the possibility of (sub)exponential quantum speedup via a quantum algorithm that follows an adiabatic path of a gapped Hamiltonian with no sign problem. The Hamiltonian that exhibits this speed-up comes from the adjacency matrix of an undirected graph whose vertices are labeled by n -bit strings, and we can view the adiabatic evolution as an efficient O ( poly ( n ))-time quantum algorithm for finding a specific “EXIT” vertex in the graph given the “ENTRANCE” vertex. On the other hand we show that if the graph is given via an adjacency-list oracle, there is no classical algorithm that finds the “EXIT” with probability greater than exp(− n δ ) using at most exp( n δ ) queries for δ= 1/5 − o (1). Our construction of the graph is somewhat similar to the “welded-trees” construction of Childs et al., but uses additional ideas of Hastings for achieving a spectral gap and a short adiabatic path.

Details

FOCS Conference 2018 Conference Paper

A Cryptographic Test of Quantumness and Certifiable Randomness from a Single Quantum Device

  • Zvika Brakerski
  • Paul F. Christiano
  • Urmila Mahadev
  • Umesh V. Vazirani
  • Thomas Vidick

We give a protocol for producing certifiable randomness from a single untrusted quantum device that is polynomial-time bounded. The randomness is certified to be statistically close to uniform from the point of view of any computationally unbounded quantum adversary, that may share entanglement with the quantum device. The protocol relies on the existence of post-quantum secure trapdoor claw-free functions, and introduces a new primitive for constraining the power of an untrusted quantum device. We then show how to construct this primitive based on the hardness of the learning with errors (LWE) problem. The randomness protocol can also be used as the basis for an efficiently verifiable "quantum supremacy" proposal, thus answering an outstanding challenge in the field.

Details

FOCS Conference 2014 Conference Paper

Local Tests of Global Entanglement and a Counterexample to the Generalized Area Law

  • Dorit Aharonov
  • Aram W. Harrow
  • Zeph Landau
  • Daniel Nagaj
  • Mario Szegedy
  • Umesh V. Vazirani

We introduce a technique for applying quantum expanders in a distributed fashion, and use it to solve two basic questions: testing whether a bipartite quantum state shared by two parties is the maximally entangled state and disproving a generalized area law. In the process these two questions which appear completely unrelated turn out to be two sides of the same coin. Strikingly in both cases a constant amount of resources are used to verify a global property.

Details

FOCS Conference 2011 Conference Paper

The 1D Area Law and the Complexity of Quantum States: A Combinatorial Approach

  • Dorit Aharonov
  • Itai Arad
  • Zeph Landau
  • Umesh V. Vazirani

The classical description of quantum states is in general exponential in the number of qubits. Can we get polynomial descriptions for more restricted sets of states such as ground states of interesting subclasses of local Hamiltonians? This is the basic problem in the study of the complexity of ground states, and requires an understanding of multi-particle entanglement and quantum correlations in such states. Area laws provide a fundamental ingredient in the study of the complexity of ground states, since they offer a way to bound in a quantitative way the entanglement in such states. Although they have long been conjectured for many body systems in arbitrary dimensions, a general rigorous was only recently proved in Hastings' seminal paper [8] for ID systems. In this paper, we give a combinatorial proof of the ID area law for the special case of frustration free systems, improving by an exponential factor the scaling in terms of the inverse spectral gap and the dimensionality of the particles. The scaling in terms of the dimension of the particles is a potentially important issue in the context of resolving the 2D case and higher dimensions, which is one of the most important open questions in Hamiltonian complexity. Our proof is based on a reformulation of the detectability lemma, introduced by us in the context of quantum gap amplification [1]. We give an alternative proof of the detectability lemma, which is not only simpler and more intuitive than the original proof, but also removes a key restriction in the original statement, making it more suitable for this new context. We also give a one page proof of Hastings' proof that the correlations in the ground states of gapped Hamiltonians decay exponentially with the distance, demonstrating the simplicity of the combinatorial approach for those problems.

Details

FOCS Conference 2007 Conference Paper

Quantum Algorithms for Hidden Nonlinear Structures

  • Andrew M. Childs
  • Leonard J. Schulman
  • Umesh V. Vazirani

Attempts to find new quantum algorithms that outperform classical computation have focused primarily on the nonAbelian hidden subgroup problem, which generalizes the central problem solved by Shor's factoring algorithm. We suggest an alternative generalization, namely to problems of finding hidden nonlinear structures over finite fields. We give examples of two such problems that can be solved efficiently by a quantum computer, but not by a classical computer. We also give some positive results on the quantum query complexity of finding hidden nonlinear structures.

Details

STOC Conference 2006 Conference Paper

Graph partitioning using single commodity flows

  • Rohit Khandekar
  • Satish Rao
  • Umesh V. Vazirani

We show that the sparsest cut in graphs can be approximated within O(log 2 n) factor in Õ(n 3/2 ) time using polylogarithmic single commodity max-flow computations. Previous algorithms are based on multicommodity flows which take time Õ(n 2 ). Our algorithm iteratively employs max-flow computations to embed an expander flow, thus providing a certificate of expansion. Our technique can also be extended to yield an O(log 2 n) (pseudo) approximation algorithm for the edge-separator problem with a similar running time.

Details

FOCS Conference 2005 Conference Paper

AdWords and Generalized On-line Matching

  • Aranyak Mehta
  • Amin Saberi
  • Umesh V. Vazirani
  • Vijay V. Vazirani

How does a search engine company decide what ads to display with each query so as to maximize its revenue? This turns out to be a generalization of the online bipartite matching problem. We introduce the notion of a tradeoff revealing LP and use it to derive two optimal algorithms achieving competitive ratios of 1-1/e for this problem.

Details

STOC Conference 2004 Conference Paper

Expander flows, geometric embeddings and graph partitioning

  • Sanjeev Arora
  • Satish Rao
  • Umesh V. Vazirani

We give a O(√log n)-approximation algorithm for sparsest cut , balanced separator , and graph conductance problems. This improves the O(log n)-approximation of Leighton and Rao (1988). We use a well-known semidefinite relaxation with triangle inequality constraints. Central to our analysis is a geometric theorem about projections of point sets in R d , whose proof makes essential use of a phenomenon called measure concentration. We also describe an interesting and natural "certificate" for a graph's expansion, by embedding an n-node expander in it with appropriate dilation and congestion. We call this an expander flow.

Details

FOCS Conference 2001 Conference Paper

How Powerful is Adiabatic Quantum Computation?

  • Wim van Dam
  • Michele Mosca
  • Umesh V. Vazirani

The authors analyze the computational power and limitations of the recently proposed 'quantum adiabatic evolution algorithm'. Adiabatic quantum computation is a novel paradigm for the design of quantum algorithms; it is truly quantum in the sense that it can be used to speed up searching by a quadratic factor over any classical algorithm. On the question of whether this new paradigm may be used to efficiently solve NP-complete problems on a quantum computer, we show that the usual query complexity arguments cannot be used to rule out a polynomial time solution. On the other hand, we argue that the adiabatic approach may be thought of as a kind of 'quantum local search'. We design a family of minimization problems that is hard for such local search heuristics, and establish an exponential lower bound for the adiabatic algorithm for these problems. This provides insights into the limitations of this approach. It remains an open question whether adiabatic quantum computation can establish an exponential speed-up over traditional computing or if there exists a classical algorithm that can simulate the quantum adiabatic process efficiently.

Details

STOC Conference 2001 Conference Paper

Quantum walks on graphs

  • Dorit Aharonov
  • Andris Ambainis
  • Julia Kempe
  • Umesh V. Vazirani

We set the ground for a theory of quantum walks on graphs-the generalization of random walks on finite graphs to the quantum world. Such quantum walks do not converge to any stationary distribution, as they are unitary and reversible. However, by suitably relaxing the definition, we can obtain a measure of how fast the quantum walk spreads or how confined the quantum walk stays in a small neighborhood. We give definitions of mixing time, filling time, dispersion time. We show that in all these measures, the quantum walk on the cycle is almost quadratically faster then its classical correspondent. On the other hand, we give a lower bound on the possible speed up by quantum walks for general graphs, showing that quantum walks can be at most polynomially faster than their classical counterparts.

Details

FOCS Conference 1998 Conference Paper

The Quantum Communication Complexity of Sampling

  • Andris Ambainis
  • Leonard J. Schulman
  • Amnon Ta-Shma
  • Umesh V. Vazirani
  • Avi Wigderson

Sampling is an important primitive in probabilistic and quantum algorithms. In the spirit of communication complexity, given a function f: X/spl times/Y/spl rarr/{0, 1} and a probability distribution D over X/spl times/Y, we define the sampling complexity of (f, D) as the minimum number of bits Alice and Bob must communicate for Alice to pick x/spl isin/X and Bob to pick y/spl isin/Y as well as a valve z s. t. the resulting distribution of (x, y, z) is close to the distribution (D, f(D)). In this paper we initiate the study of sampling complexity, in both the classical and quantum model. We give several variants of the definition. We completely characterize some of these tasks, and give upper and lower bounds on others. In particular this allows us to establish an exponential gap between quantum and classical sampling complexity, for the set disjointness function. This is the first exponential gap for any task where the classical probabilistic algorithm is allowed to err.

Details

FOCS Conference 1994 Conference Paper

"Go With the Winners" Algorithms

  • David J. Aldous
  • Umesh V. Vazirani

We can view certain randomized optimization algorithms as rules for randomly moving a particle around in a state space; each state might correspond to a distinct solution to the optimization problem, or more generally, the state space might express some other structure underlying the optimization algorithm. In this setting, a general paradigm for designing heuristics is to run several simulations of the algorithm simultaneously, and every so often classify the particles as "doing well" or "doing badly", and move each particle that is "doing badly" to the position of one that is "doing well". In this paper, we give a rigorous analysis of such a "go with the winners" scheme in the concrete setting of searching for a deep leaf in a tree. There are two relevant parameters of the tree: its depth d, and another parameter /spl kappa/ which is a measure of the imbalance of the tree. We prove that the running time of the "go with the winners" scheme (to achieve 99% probability of success) is bounded by a polynomial in d and /spl kappa/. By contrast, the simple restart scheme: run several independent simulations and pick the deepest leaf encountered takes time exponential in /spl kappa/ and d in the worst-case. We also show that any algorithm that guarantees a constant probability of success must have worst case running time at least /spl kappa/d. >

Details

FOCS Conference 1994 Conference Paper

On Syntactic versus Computational Views of Approximability

  • Sanjeev Khanna
  • Rajeev Motwani 0001
  • Madhu Sudan 0001
  • Umesh V. Vazirani

We attempt to reconcile the two distinct views of approximation classes: syntactic and computational. Syntactic classes such as MAX SNP permit structural results and have natural complete problems, while computational classes such as APX allow us to work with classes of problems whose approximability is well-understood. Our results provide a syntactic characterization of computational classes, and give a computational framework for syntactic classes. >

Details

FOCS Conference 1992 Conference Paper

A Mildly Exponential Approximation Algorithm for the Permanent

  • Mark Jerrum
  • Umesh V. Vazirani

An approximation algorithm for the permanent of an n*n 0, 1-matrix is presented. The algorithm is shown to have worst-case time complexity exp (0(n/sup 1/2/ log/sup 2/ n)). Asymptotically, this represents a considerable improvement over the best existing algorithm, which has worst-case time complexity of the form e/sup theta (n)/. >

Details

FOCS Conference 1990 Conference Paper

A Markovian Extension of Valiant's Learning Model (Extended Abstract)

  • David J. Aldous
  • Umesh V. Vazirani

A model of learning that expands on the Valiant model is introduced. The point of departure from the Valiant model is that the learner is placed in a Markovian environment. The environment of the learner is a (exponentially large) graph, and the examples reside on the vertices of the graph, one example on each vertex. The learner obtains the examples while performing a random walk on the graph. At each step, the learning algorithm guesses the classification of the example on the current vertex using its current hypothesis. If its guess is incorrect, the learning algorithm updates its current working hypothesis. The performance of the learning algorithm in a given environment is judged by the expected number of mistakes made as a function of the number of steps in the random walk. The predictive value of Occam algorithms under this weaker probabilistic model of the learner's environment is studied. >

Details

FOCS Conference 1989 Conference Paper

Graph Products and Chromatic Numbers

  • Nati Linial
  • Umesh V. Vazirani

The problem of computing the chromatic number of a graph is considered. No known approximation algorithm can guarantee a better than O(n/sup 0. 4/) coloring on a three-chromatic graph with n vertices. Evidence is provided that it is inherently impossible to achieve a better than n/sup epsilon / ratio in polynomial time by showing that 'breaking the n/sup epsilon / barrier' will automatically lead to vastly better polynomial-time approximation algorithms that achieve ratios closer to log n. >

Details

FOCS Conference 1988 Conference Paper

Polytopes, Permanents and Graphs with Large Factors

  • Paul Dagum
  • Michael Luby
  • Milena Mihail
  • Umesh V. Vazirani

Randomized algorithms for approximating the number of perfect matchings in a graph are considered. An algorithm that is a natural simplification of one suggested and analyzed previously is introduced and analyzed. One of the key ideas is to view the analysis from a geometric perspective: it is proved that for any graph G the k-slice of the well-known Edmonds matching polytope has magnification 1. For a bipartite graph G=(U, V, E), mod U mod = mod V mod =n, with d edge-disjoint perfect matchings, it is proved that the ratio of the number of almost perfect matchings to the number of perfect matchings is at most n/sup 3n/d/. For any constant alpha >0 this yields a a fully polynomial randomized algorithm for approximating the number of perfect matchings in bipartite graphs with d>or= alpha n. Moreover, for some constant c>0 it is the fastest known approximation algorithm for bipartite graphs with d>or= clog n. >

Details

FOCS Conference 1985 Conference Paper

Random Polynomial Time Is Equal to Slightly-random Polynomial Time

  • Umesh V. Vazirani
  • Vijay V. Vazirani

Random Polynomial Time (Rp) is currently considered to be the class of tractable computational problems. Here one assumes a source of truly random bits. However, the known sources of randomness are imperfect. They can be modeled as an adversary source, called slightly-random source. Slightlyrandom Polynomial Time (SRp) is the class of problems solvable in polynomial time using such a source. SRp is thus a more realistic definition of a tractable computational problem. In this paper we give an affirmative answer to the question "is Rp = SRp? " Our proof method is constructive: given an Rp algorithm for a problem, we show how to obtain an SRp algorithm for it. Studying the relationship between randomized and deterministic computation is currently an important issue. A central question here is "is Rp = P? " Our result may be a step towards answering this question.

Details

FOCS Conference 1984 Conference Paper

Efficient and Secure Pseudo-Random Number Generation (Extended Abstract)

  • Umesh V. Vazirani
  • Vijay V. Vazirani

Cryptographically secure pseudo-random number generators known so far suffer from the handicap of being inefficient; the most efficient ones can generate only one bit on each modular multiplication (n/sup 2/ steps). Blum, Blum and Shub ask the open problem of outputting even two bits securely. We state a simple condition, the XOR-Condition, and show that any generator satisfying this condition can output logn bits on each multiplication. We also show that the logn least significant bits of RSA, Rabin's Scheme, and the x/sup 2/ mod N generator satisfy boolean predicates of these bits are secure. Furthermore, we strengthen the security of the x/sup 2/ mod N generator, which being a Trapdoor Generator, has several applications, by proving it as hard as Factoring.

Details

FOCS Conference 1984 Conference Paper

Generating Quasi-Random Sequences from Slightly-Random Sources (Extended Abstract)

  • Miklos Santha
  • Umesh V. Vazirani

Several applications require truly random bit sequences, whereas physical sources of randomness are at best imperfect. We consider a general model for these slightly-random sources (e, g. zener diodes), and show how to convert their output into 'random looking ' sequences, which we call quasi -random. We show that quasi-random sequences are indistinguishable from truly random ones in a strong sense. This enables us to prove that quasi-random sequences can be used in place of truly random ones for applications such as seeds for pseudo-random number generators, randomizing algorithms, and stochastic simulation experiments.

Details

FOCS Conference 1983 Conference Paper

Global Wire Routing in Two-Dimensional Arrays (Extended Abstract)

  • Richard M. Karp
  • Frank Thomson Leighton
  • Ronald L. Rivest
  • Clark D. Thompson
  • Umesh V. Vazirani
  • Vijay V. Vazirani

We examine the problem of routing wires on a VLSI chip, where the pins to be connected are arranged in a regular rectangular array. We obtain tight bounds for the worst-case "channel-width" needed to route an n × n array, and develop provably good heuristics for the general case. An interesting "rounding algorithm" for obtaining integral approximations to solutions of linear equations is used to show the near-optimality of single-turn routings in the worst-case.

Details

FOCS Conference 1983 Conference Paper

Trapdoor Pseudo-random Number Generators, with Applications to Protocol Design

  • Umesh V. Vazirani
  • Vijay V. Vazirani

We define the class of trapdoor pseudo-random number generators, and introduce a new technique for using these in cryptography. As an application for this technique, we present a provably secure protocol for One-Bit Disclosures i. e. for giving a one-bit message in exchange for receipt.

Details

FOCS Conference 1982 Conference Paper

A Natural Encoding Scheme Proved Probabilistic Polynomial Complete

  • Umesh V. Vazirani
  • Vijay V. Vazirani

We prove a natural encoding scheme intractable (by showing it UR-complete, a technique which may be used when a problem does not yield to a proof of NP-completeness). This is the first non number-theoretic problem that is UR-complete but not known to be NP-complete. We also redefine UR-completeness (henceforth refered to as PR-completeness) in probabilistic terms thus making the notion conceptually simpler. Our result suggests that PR-completeness may be a more widely applicable technique than was previously believed.

Details