Arrow Research search

Author name cluster

Michael Ben-Or

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.

23 papers
1 author row

Possible papers

23

FOCS Conference 2008 Conference Paper

Quantum Multi Prover Interactive Proofs with Communicating Provers

  • Michael Ben-Or
  • Avinatan Hassidim
  • Haran Pilpel

We introduce another variant of quantum MIP, where the provers do not share entanglement, the communication between the verifier and the provers is quantum, but the provers are unlimited in the classical communication between them. At first, this model may seem very weak, as provers who exchange information seem to be equivalent in power to a simple prover. This in fact is not the case-we show that any language in NEXP can be recognized in this model efficiently, with just two provers and two rounds of communication, with a constant completeness-soundness gap. Similar ideas and techniques may help help with other models of quantum MIP, including the dual question, of non communicating provers with unlimited entanglement.

Details

FOCS Conference 2008 Conference Paper

The Bayesian Learner is Optimal for Noisy Binary Search (and Pretty Good for Quantum as Well)

  • Michael Ben-Or
  • Avinatan Hassidim

We use a Bayesian approach to optimally solve problems in noisy binary search. We deal with two variants: 1. Each comparison is erroneous with independent probability 1-p. 2. At each stage k comparisons can be performed in parallel and a noisy answer is returned. We present a (classical) algorithm which solves both variants optimally (with respect to p and k), up to an additive term of O(loglog n), and prove matching information-theoretic lower bounds. We use the algorithm to improve the results of Farhi et al. , presenting an exact quantum search algorithm in an ordered list of expected complexity less than (log 2 n)/3.

Details

STOC Conference 2006 Conference Paper

Byzantine agreement in the full-information model in O(log n) rounds

  • Michael Ben-Or
  • Elan Pavlov
  • Vinod Vaikuntanathan

We present a randomized Byzantine Agreement (BA) protocol with an expected running time of O(log n) rounds, in a synchronous full-information network of n players. For any constant ε > 0, the constructed protocol tolerates t non-adaptive Byzantine faults, as long as n ≥ (4 + ε)t. In the full-information model, no restrictions are placed on the computational power of the faulty players or the information available to them. In particular, the faulty players may be infinitely powerful, and they can observe all communication among the honest players.This constitutes significant progress over the best known randomized BA protocol in the same setting which has a round-complexity of Θ(t/log n) rounds [9], and answers an open problem posed by Chor and Dwork [10].

Details

FOCS Conference 2006 Conference Paper

Secure Multiparty Quantum Computation with (Only) a Strict Honest Majority

  • Michael Ben-Or
  • Claude Crépeau
  • Daniel Gottesman
  • Avinatan Hassidim
  • Adam Smith 0006

Secret sharing and multiparty computation (also called "secure function evaluation") are fundamental primitives in modern cryptography, allowing a group of mutually distrustful players to perform correct, distributed computations under the sole assumption that some number of them will follow the protocol honestly. This paper investigates how much trust is necessary -- that is, how many players must remain honest -- in order for distributed quantum computations to be possible. We present a verifiable quantum secret sharing (VQSS) protocol, and a general secure multiparty quantum computation (MPQC) protocol, which can tolerate any \left[ {\frac{{n - 1}} {2}} \right] cheaters among n players. Previous protocols for these tasks tolerated \left[ {\frac{{n - 1}} {4}} \right] and \left[ {\frac{{n - 1}} {6}} \right] cheaters, respectively. The threshold we achieve is tight -- even in the classical case, "fair" multiparty computation is not possible if any set of n/2 players can cheat. Our protocols rely on approximate quantum errorcorrecting codes, which can tolerate a larger fraction of errors than traditional, exact codes. We introduce new families of authentication schemes and approximate codes tailored to the needs of our protocols, as well as new state purification techniques along the lines of those used in faulttolerant quantum circuits.

Details

FOCS Conference 1996 Conference Paper

Polynomial Simulations of Decohered Quantum Computers

  • Dorit Aharonov
  • Michael Ben-Or

Recently it has become clear, that a key issue in quantum computation is understanding how interaction with the environment, or "decoherence", affects the computational power of quantum computers. We adopt the standard physical method of describing systems which are interwound with their environment by "density matrices", and within this framework define a model of decoherence in quantum computation. Our results show that the computational power of decohered quantum computers depends strongly on the amount of parallelism in the computation. We first present a simulation of decohered sequential quantum computers, on a classical probabilistic Turing machine, and prove that the expected slowdown of this simulation is polynomial in time and space of the quantum computation, for any non zero decoherence rate. Similar results hold for quantum computers that are allowed to operate on logarithmic number of qubits at a time. For decohered quantum circuits (with local gates), the situation is more subtle and depends on the decoherence rate, /spl eta/. We find that our simulation is efficient for circuits with decoherence rate /spl eta/ higher than some constant /spl eta//sub 1/ but exponential for a general (random) circuit subjected to decoherence rate lower than some constant /spl eta//sub 2/. The transition from exponential cost to polynomial cost happens in a short range of decoherence rates. We use computer experiments to exhibit the phase transitions in various quantum circuits.

Details

FOCS Conference 1994 Conference Paper

Algebraic Computation Trees in Characteristi p>0 (Extended Abstract)

  • Michael Ben-Or

We provide a simple and powerful combinatorial method for proving lower bounds for algebraic computation trees over algebraically closed fields of characteristic p>0. We apply our method to prove, for example, an /spl Omega/(n log n) lower bound for the n element distinctness problem, an /spl Omega/(n log(n/k)) lower bound to the "k-equal problem"-that is deciding whether there are k identical elements out of n input elements, and more. The proof of the main theorem relies on the deep work of B. M. Dwork, P. Deligne, and E. Bombieri on the Weil conjectures. In particular we make use of Bombieri's bound on the degree of the Zeta function of algebraic varieties over finite fields. Our bounds provide a natural extension to the recent topological lower bounds obtained by A. Bjorner, L. Lovasz and A. C. Yao for algebraic computation trees over the real numbers. For the special cases of real subspace arrangements and general complex varieties we can reformulate their specific results using our combinatorial approach without mentioning any topological invariants. >

Details

FOCS Conference 1991 Conference Paper

Asymptotically Optimal PRAM Emulation on Faulty Hypercubes (Extended Abstract)

  • Yonatan Aumann
  • Michael Ben-Or

A scheme for emulating the parallel random access machine (PRAM) on a faulty hypercube is presented. All components of the hypercube, including the memory modules, are assumed to be subject to failure. The faults may occur at any time during the emulation and the system readjusts dynamically. The scheme, which rests on L. G. Valiant's BSP model (1990), is the first to achieve optimal and work-preserving PRAM emulation on a dynamically faulty network. >

Details

FOCS Conference 1985 Conference Paper

Collective Coin Flipping, Robust Voting Schemes and Minima of Banzhaf Values

  • Michael Ben-Or
  • Nati Linial

The power of players in a collective decision process is a central issue in Mathematical Economics and Game Theory. Similar issues arise in Computer Science in the study of distributed, fault tolerant computations when several processes, some perhaps faulty, have to reach agreement. In the present article we study voting schemes which are relatively immune to the presence of unfair players. In particular, we discuss how to perform collective coin flipping which is only slightly biased despite the presence of unfair players. Mathematically this corresponds to problems concerning the minima of Banzhaf values in certain n -person games. These are measures of power studied in Game Theory. It is quite remarkable that while dictatorial voting games are, of course, the most sensitive to the presence of unfair players, some voting schemes that we propose here are significantly more robust than majority voting. Coin flipping was selected as a study case because of its simplicity and because collective coin flipping is widely used in randomized algorithms for distributed computations. It is our feeling that Game Theory has much to contribute to Computer Science and we are sure that further applications will be found.

Details