8,805 Works

OV Graphs Are (Probably) Hard Instances

Josh Alman & Virginia Vassilevska Williams
A graph G on n nodes is an Orthogonal Vectors (OV) graph of dimension d if there are vectors v_1, …, v_n ? {0,1}^d such that nodes i and j are adjacent in G if and only if ?v_i,v_j? = 0 over Z. In this paper, we study a number of basic graph algorithm problems, except where one is given as input the vectors defining an OV graph instead of a general graph. We show...

Affine Determinant Programs: A Framework for Obfuscation and Witness Encryption

James Bartusek, Yuval Ishai, Aayush Jain, Fermi Ma, Amit Sahai & Mark Zhandry
An affine determinant program ADP: {0,1}^n ? {0,1} is specified by a tuple (A,B_1,…,B_n) of square matrices over ?_q and a function Eval: ?_q ? {0,1}, and evaluated on x ? {0,1}^n by computing Eval(det(A + ?_{i?[n]} x_i B_i)). In this work, we suggest ADPs as a new framework for building general-purpose obfuscation and witness encryption. We provide evidence to suggest that constructions following our ADP-based framework may one day yield secure, practically feasible obfuscation....

Pseudo-Deterministic Streaming

Shafi Goldwasser, Ofer Grossman, Sidhanth Mohanty & David P. Woodruff
A pseudo-deterministic algorithm is a (randomized) algorithm which, when run multiple times on the same input, with high probability outputs the same result on all executions. Classic streaming algorithms, such as those for finding heavy hitters, approximate counting, ?_2 approximation, finding a nonzero entry in a vector (for turnstile algorithms) are not pseudo-deterministic. For example, in the instance of finding a nonzero entry in a vector, for any known low-space algorithm A, there exists a...

Limits to Non-Malleability

Marshall Ball, Dana Dachman-Soled, Mukul Kulkarni & Tal Malkin
There have been many successes in constructing explicit non-malleable codes for various classes of tampering functions in recent years, and strong existential results are also known. In this work we ask the following question: When can we rule out the existence of a non-malleable code for a tampering class ?? First, we start with some classes where positive results are well-known, and show that when these classes are extended in a natural way, non-malleable codes...

Graph Spanners in the Message-Passing Model

Manuel Fernández V, David P. Woodruff & Taisuke Yasuda
Graph spanners are sparse subgraphs which approximately preserve all pairwise shortest-path distances in an input graph. The notion of approximation can be additive, multiplicative, or both, and many variants of this problem have been extensively studied. We study the problem of computing a graph spanner when the edges of the input graph are distributed across two or more sites in an arbitrary, possibly worst-case partition, and the goal is for the sites to minimize the...

Computational Hardness of Certifying Bounds on Constrained PCA Problems

Afonso S. Bandeira, Dmitriy Kunisky & Alexander S. Wein
Given a random n × n symmetric matrix ? drawn from the Gaussian orthogonal ensemble (GOE), we consider the problem of certifying an upper bound on the maximum value of the quadratic form ?^? ? ? over all vectors ? in a constraint set ? ? ??. For a certain class of normalized constraint sets we show that, conditional on a certain complexity-theoretic conjecture, no polynomial-time algorithm can certify a better upper bound than the...

Choice and Bias in Random Walks

Agelos Georgakopoulos, John Haslegrave, Thomas Sauerwald & John Sylvester
We analyse the following random walk process inspired by the power-of-two-choice paradigm: starting from a given vertex, at each step, unlike the simple random walk (SRW) that always moves to a randomly chosen neighbour, we have the choice between two uniformly and independently chosen neighbours. We call this process the choice random walk (CRW). We first prove that for any graph, there is a strategy for the CRW that visits any given vertex in expected...

Local-To-Global Agreement Expansion via the Variance Method

Tali Kaufman & David Mass
Agreement expansion is concerned with set systems for which local assignments to the sets with almost perfect pairwise consistency (i.e., most overlapping pairs of sets agree on their intersections) implies the existence of a global assignment to the ground set (from which the sets are defined) that agrees with most of the local assignments. It is currently known that if a set system forms a two-sided or a partite high dimensional expander then agreement expansion...

MPC for MPC: Secure Computation on a Massively Parallel Computing Architecture

T-H. Hubert Chan, Kai-Min Chung, Wei-Kai Lin & Elaine Shi
Massively Parallel Computation (MPC) is a model of computation widely believed to best capture realistic parallel computing architectures such as large-scale MapReduce and Hadoop clusters. Motivated by the fact that many data analytics tasks performed on these platforms involve sensitive user data, we initiate the theoretical exploration of how to leverage MPC architectures to enable efficient, privacy-preserving computation over massive data. Clearly if a computation task does not lend itself to an efficient implementation on...

Smoothed Efficient Algorithms and Reductions for Network Coordination Games

Shant Boodaghians, Rucha Kulkarni & Ruta Mehta
We study the smoothed complexity of finding pure Nash equilibria in Network Coordination Games, a PLS-complete problem in the worst case, even when each player has two strategies. This is a potential game where the sequential-better-response algorithm is known to converge to a pure NE, albeit in exponential time. First, we prove polynomial (respectively, quasi-polynomial) smoothed complexity when the underlying game graph is complete (resp. arbitrary), and every player has constantly many strategies. The complete...

Trade-Offs Between Size and Degree in Polynomial Calculus

Guillaume Lagarde, Jakob Nordström, Dmitry Sokolov & Joseph Swernofsky
Building on [Clegg et al. '96], [Impagliazzo et al. '99] established that if an unsatisfiable k-CNF formula over n variables has a refutation of size S in the polynomial calculus resolution proof system, then this formula also has a refutation of degree k + O(?(n log S)). The proof of this works by converting a small-size refutation into a small-degree one, but at the expense of increasing the proof size exponentially. This raises the question...

Beyond Natural Proofs: Hardness Magnification and Locality

Lijie Chen, Shuichi Hirahara, Igor C. Oliveira, Ján Pich, Ninad Rajgopal & Rahul Santhanam
Hardness magnification reduces major complexity separations (such as EXP ? NC^1) to proving lower bounds for some natural problem Q against weak circuit models. Several recent works [Igor Carboni Oliveira and Rahul Santhanam, 2018; Dylan M. McKay et al., 2019; Lijie Chen and Roei Tell, 2019; Igor Carboni Oliveira et al., 2019; Lijie Chen et al., 2019; Igor Carboni Oliveira, 2019; Lijie Chen et al., 2019] have established results of this form. In the most...

Separating Two-Round Secure Computation From Oblivious Transfer

Benny Applebaum, Zvika Brakerski, Sanjam Garg, Yuval Ishai & Akshayaram Srinivasan
We consider the question of minimizing the round complexity of protocols for secure multiparty computation (MPC) with security against an arbitrary number of semi-honest parties. Very recently, Garg and Srinivasan (Eurocrypt 2018) and Benhamouda and Lin (Eurocrypt 2018) constructed such 2-round MPC protocols from minimal assumptions. This was done by showing a round preserving reduction to the task of secure 2-party computation of the oblivious transfer functionality (OT). These constructions made a novel non-black-box use...

Incentive Compatible Active Learning

Federico Echenique & Siddharth Prasad
We consider active learning under incentive compatibility constraints. The main application of our results is to economic experiments, in which a learner seeks to infer the parameters of a subject’s preferences: for example their attitudes towards risk, or their beliefs over uncertain events. By cleverly adapting the experimental design, one can save on the time spent by subjects in the laboratory, or maximize the information obtained from each subject in a given laboratory session; but...

Pseudorandomness and the Minimum Circuit Size Problem

Rahul Santhanam
We explore the possibility of basing one-way functions on the average-case hardness of the fundamental Minimum Circuit Size Problem (MCSP[s]), which asks whether a Boolean function on n bits specified by its truth table has circuits of size s(n). 1) (Pseudorandomness from Zero-Error Average-Case Hardness) We show that for a given size function s, the following are equivalent: Pseudorandom distributions supported on strings describable by s(O(n))-size circuits exist; Hitting sets supported on strings describable by...

Testing Properties of Multiple Distributions with Few Samples

Maryam Aliakbarpour & Sandeep Silwal
We propose a new setting for testing properties of distributions while receiving samples from several distributions, but few samples per distribution. Given samples from s distributions, p_1, p_2, …, p_s, we design testers for the following problems: (1) Uniformity Testing: Testing whether all the p_i’s are uniform or ?-far from being uniform in ?_1-distance (2) Identity Testing: Testing whether all the p_i’s are equal to an explicitly given distribution q or ?-far from q in...

Computation-Aware Data Aggregation

Bernhard Haeupler, D. Ellis Hershkowitz, Anson Kahng & Ariel D. Procaccia
Data aggregation is a fundamental primitive in distributed computing wherein a network computes a function of every nodes' input. However, while compute time is non-negligible in modern systems, standard models of distributed computing do not take compute time into account. Rather, most distributed models of computation only explicitly consider communication time. In this paper, we introduce a model of distributed computation that considers both computation and communication so as to give a theoretical treatment of...

Convertible Codes: New Class of Codes for Efficient Conversion of Coded Data in Distributed Storage

Francisco Maturana & K. V. Rashmi
Erasure codes are typically used in large-scale distributed storage systems to provide durability of data in the face of failures. In this setting, a set of k blocks to be stored is encoded using an [n, k] code to generate n blocks that are then stored on different storage nodes. A recent work by Kadekodi et al. [Kadekodi et al., 2019] shows that the failure rate of storage devices vary significantly over time, and that...

New Query Lower Bounds for Submodular Function Minimization

Andrei Graur, Tristan Pollner, Vidhya Ramaswamy & S. Matthew Weinberg
We consider submodular function minimization in the oracle model: given black-box access to a submodular set function f:2^[n] ? ?, find an element of arg min_S {f(S)} using as few queries to f(?) as possible. State-of-the-art algorithms succeed with Õ(n²) queries [Yin Tat Lee et al., 2015], yet the best-known lower bound has never been improved beyond n [Nicholas J. A. Harvey, 2008]. We provide a query lower bound of 2n for submodular function minimization,...

Computational Pseudorandomness, the Wormhole Growth Paradox, and Constraints on the AdS/CFT Duality (Abstract)

Adam Bouland, Bill Fefferman & Umesh Vazirani
The AdS/CFT correspondence is central to efforts to reconcile gravity and quantum mechanics, a fundamental goal of physics. It posits a duality between a gravitational theory in Anti de Sitter (AdS) space and a quantum mechanical conformal field theory (CFT), embodied in a map known as the AdS/CFT dictionary mapping states to states and operators to operators. This dictionary map is not well understood and has only been computed on special, structured instances. In this...

Implementation in Advised Strategies: Welfare Guarantees from Posted-Price Mechanisms When Demand Queries Are NP-Hard

Linda Cai, Clay Thomas & S. Matthew Weinberg
State-of-the-art posted-price mechanisms for submodular bidders with m items achieve approximation guarantees of O((log log m)^3) [Sepehr Assadi and Sahil Singla, 2019]. Their truthfulness, however, requires bidders to compute an NP-hard demand-query. Some computational complexity of this form is unavoidable, as it is NP-hard for truthful mechanisms to guarantee even an m^(1/2-?)-approximation for any ? > 0 [Shahar Dobzinski and Jan Vondrák, 2016]. Together, these establish a stark distinction between computationally-efficient and communication-efficient truthful mechanisms....

Toward a General Complexity Theory of Motion Planning: Characterizing Which Gadgets Make Games Hard

Erik D. Demaine, Dylan H. Hendrickson & Jayson Lynch
We begin a general theory for characterizing the computational complexity of motion planning of robot(s) through a graph of "gadgets", where each gadget has its own state defining a set of allowed traversals which in turn modify the gadget’s state. We study two general families of such gadgets within this theory, one which naturally leads to motion planning problems with polynomially bounded solutions, and another which leads to polynomially unbounded (potentially exponential) solutions. We also...

A Tight Lower Bound For Non-Coherent Index Erasure

Nathan Lindzey & Ansis Rosmanis
The index erasure problem is a quantum state generation problem that asks a quantum computer to prepare a uniform superposition over the image of an injective function given by an oracle. We prove a tight ?(?n) lower bound on the quantum query complexity of the non-coherent case of the problem, where, in addition to preparing the required superposition, the algorithm is allowed to leave the ancillary memory in an arbitrary function-dependent state. This resolves an...

Optimal Single-Choice Prophet Inequalities from Samples

Aviad Rubinstein, Jack Z. Wang & S. Matthew Weinberg
We study the single-choice Prophet Inequality problem when the gambler is given access to samples. We show that the optimal competitive ratio of 1/2 can be achieved with a single sample from each distribution. When the distributions are identical, we show that for any constant ? > 0, O(n) samples from the distribution suffice to achieve the optimal competitive ratio (? 0.745) within (1+?), resolving an open problem of [José R. Correa et al., 2019].

Lower Bounds for (Non-Monotone) Comparator Circuits

Anna Gál & Robert Robere
Comparator circuits are a natural circuit model for studying the concept of bounded fan-out computations, which intuitively corresponds to whether or not a computational model can make "copies" of intermediate computational steps. Comparator circuits are believed to be weaker than general Boolean circuits, but they can simulate Branching Programs and Boolean formulas. In this paper we prove the first superlinear lower bounds in the general (non-monotone) version of this model for an explicitly defined function....

Registration Year

  • 2009
  • 2010
  • 2011
  • 2012
  • 2013
  • 2014
  • 2015
  • 2016
  • 2017
  • 2018
  • 2019
  • 2020

Resource Types

  • Text
  • Software