8,805 Works

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....

On the Impossibility of Probabilistic Proofs in Relativized Worlds

Alessandro Chiesa & Siqi Liu
We initiate the systematic study of probabilistic proofs in relativized worlds, where the goal is to understand, for a given oracle, the possibility of "non-trivial" proof systems for deterministic or nondeterministic computations that make queries to the oracle. This question is intimately related to a recent line of work that seeks to improve the efficiency of probabilistic proofs for computations that use functionalities such as cryptographic hash functions and digital signatures, by instantiating them via...

Instance Complexity and Unlabeled Certificates in the Decision Tree Model

Tomer Grossman, Ilan Komargodski & Moni Naor
Instance complexity is a measure of goodness of an algorithm in which the performance of one algorithm is compared to others per input. This is in sharp contrast to worst-case and average-case complexity measures, where the performance is compared either on the worst input or on an average one, respectively. We initiate the systematic study of instance complexity and optimality in the query model (a.k.a. the decision tree model). In this model, instance optimality of...

Advancing Subgroup Fairness via Sleeping Experts

Avrim Blum & Thodoris Lykouris
We study methods for improving fairness to subgroups in settings with overlapping populations and sequential predictions. Classical notions of fairness focus on the balance of some property across different populations. However, in many applications the goal of the different groups is not to be predicted equally but rather to be predicted well. We demonstrate that the task of satisfying this guarantee for multiple overlapping groups is not straightforward and show that for the simple objective...

Matching Is as Easy as the Decision Problem, in the NC Model

Nima Anari & Vijay V. Vazirani
Is matching in NC, i.e., is there a deterministic fast parallel algorithm for it? This has been an outstanding open question in TCS for over three decades, ever since the discovery of randomized NC matching algorithms [Karp et al., 1985; Mulmuley et al., 1987]. Over the last five years, the theoretical computer science community has launched a relentless attack on this question, leading to the discovery of several powerful ideas. We give what appears to...

Online Computation with Untrusted Advice

Spyros Angelopoulos, Christoph Dürr, Shendan Jin, Shahin Kamali & Marc Renault
The advice model of online computation captures the setting in which the online algorithm is given some partial information concerning the request sequence. This paradigm allows to establish tradeoffs between the amount of this additional information and the performance of the online algorithm. However, unlike real life in which advice is a recommendation that we can choose to follow or to ignore based on trustworthiness, in the current advice model, the online algorithm treats it...

Generalized List Decoding

Yihan Zhang, Amitalok J. Budkuley & Sidharth Jaggi
This paper concerns itself with the question of list decoding for general adversarial channels, e.g., bit-flip (XOR) channels, erasure channels, AND (Z-) channels, OR channels, real adder channels, noisy typewriter channels, etc. We precisely characterize when exponential-sized (or positive rate) (L-1)-list decodable codes (where the list size L is a universal constant) exist for such channels. Our criterion essentially asserts that: For any given general adversarial channel, it is possible to construct positive rate (L-1)-list...

Monochromatic Triangles, Intermediate Matrix Products, and Convolutions

Andrea Lincoln, Adam Polak & Virginia Vassilevska Williams
The most studied linear algebraic operation, matrix multiplication, has surprisingly fast O(n^?) time algorithms for ? < 2.373. On the other hand, the (min,+) matrix product which is at the heart of many fundamental graph problems such as All-Pairs Shortest Paths, has received only minor n^o(1) improvements over its brute-force cubic running time and is widely conjectured to require n^{3-o(1)} time. There is a plethora of matrix products and graph problems whose complexity seems to...

Certified Algorithms: Worst-Case Analysis and Beyond

Konstantin Makarychev & Yury Makarychev
In this paper, we introduce the notion of a certified algorithm. Certified algorithms provide worst-case and beyond-worst-case performance guarantees. First, a ?-certified algorithm is also a ?-approximation algorithm - it finds a ?-approximation no matter what the input is. Second, it exactly solves ?-perturbation-resilient instances (?-perturbation-resilient instances model real-life instances). Additionally, certified algorithms have a number of other desirable properties: they solve both maximization and minimization versions of a problem (e.g. Max Cut and Min...

Low Diameter Graph Decompositions by Approximate Distance Computation

Ruben Becker, Yuval Emek & Christoph Lenzen
In many models for large-scale computation, decomposition of the problem is key to efficient algorithms. For distance-related graph problems, it is often crucial that such a decomposition results in clusters of small diameter, while the probability that an edge is cut by the decomposition scales linearly with the length of the edge. There is a large body of literature on low diameter graph decomposition with small edge cutting probabilities, with all existing techniques heavily building...

The Computational Cost of Asynchronous Neural Communication

Yael Hitron, Merav Parter & Gur Perri
Biological neural computation is inherently asynchronous due to large variations in neuronal spike timing and transmission delays. So-far, most theoretical work on neural networks assumes the synchronous setting where neurons fire simultaneously in discrete rounds. In this work we aim at understanding the barriers of asynchronous neural computation from an algorithmic perspective. We consider an extension of the widely studied model of synchronized spiking neurons [Maass, Neural Networks 97] to the asynchronous setting by taking...

Fault Tolerant Subgraphs with Applications in Kernelization

William Lochet, Daniel Lokshtanov, Pranabendu Misra, Saket Saurabh, Roohani Sharma & Meirav Zehavi
In the past decade, the design of fault tolerant data structures for networks has become a central topic of research. Particular attention has been given to the construction of a subgraph H of a given digraph D with as fewest arcs/vertices as possible such that, after the failure of any set F of at most k ? 1 arcs, testing whether D-F has a certain property P is equivalent to testing whether H-F has that...

Strategic Payments in Financial Networks

Nils Bertschinger, Martin Hoefer & Daniel Schmand
In their seminal work on systemic risk in financial markets, Eisenberg and Noe [Larry Eisenberg and Thomas Noe, 2001] proposed and studied a model with n firms embedded into a network of debt relations. We analyze this model from a game-theoretic point of view. Every firm is a rational agent in a directed graph that has an incentive to allocate payments in order to clear as much of its debt as possible. Each edge is...

Algorithms and Adaptivity Gaps for Stochastic k-TSP

Haotian Jiang, Jian Li, Daogao Liu & Sahil Singla
Given a metric (V,d) and a root ? V, the classic k-TSP problem is to find a tour originating at the root of minimum length that visits at least k nodes in V. In this work, motivated by applications where the input to an optimization problem is uncertain, we study two stochastic versions of k-TSP. In Stoch-Reward k-TSP, originally defined by Ene-Nagarajan-Saket [Ene et al., 2018], each vertex v in the given metric (V,d) contains...

Top-Down Induction of Decision Trees: Rigorous Guarantees and Inherent Limitations

Guy Blanc, Jane Lange & Li-Yang Tan
Consider the following heuristic for building a decision tree for a function f : {0,1}^n ? {± 1}. Place the most influential variable x_i of f at the root, and recurse on the subfunctions f_{x_i=0} and f_{x_i=1} on the left and right subtrees respectively; terminate once the tree is an ?-approximation of f. We analyze the quality of this heuristic, obtaining near-matching upper and lower bounds: - Upper bound: For every f with decision tree...

Testing Linear Inequalities of Subgraph Statistics

Lior Gishboliner, Asaf Shapira & Henrique Stagni
Property testers are fast randomized algorithms whose task is to distinguish between inputs satisfying some predetermined property ? and those that are far from satisfying it. Since these algorithms operate by inspecting a small randomly selected portion of the input, the most natural property one would like to be able to test is whether the input does not contain certain forbidden small substructures. In the setting of graphs, such a result was obtained by Alon...

Unexpected Power of Random Strings

Shuichi Hirahara
There has been a line of work trying to characterize BPP (the class of languages that are solvable by efficient randomized algorithms) by efficient nonadaptive reductions to the set of Kolmogorov-random strings: Buhrman, Fortnow, Koucký, and Loff (CCC 2010 [Buhrman et al., 2010]) showed that every language in BPP is reducible to the set of random strings via a polynomial-time nonadaptive reduction (irrespective of the choice of a universal Turing machine used to define Kolmogorov-random...

Ad Hoc Multi-Input Functional Encryption

Shweta Agrawal, Michael Clear, Ophir Frieder, Sanjam Garg, Adam O'Neill & Justin Thaler
Consider sources that supply sensitive data to an aggregator. Standard encryption only hides the data from eavesdroppers, but using specialized encryption one can hope to hide the data (to the extent possible) from the aggregator itself. For flexibility and security, we envision schemes that allow sources to supply encrypted data, such that at any point a dynamically-chosen subset of sources can allow an agreed-upon joint function of their data to be computed by the aggregator....

Consensus vs Broadcast, with and Without Noise (Extended Abstract)

Andrea Clementi, Luciano Gualà, Emanuele Natale, Francesco Pasquale, Giacomo Scornavacca & Luca Trevisan
Consensus and Broadcast are two fundamental problems in distributed computing, whose solutions have several applications. Intuitively, Consensus should be no harder than Broadcast, and this can be rigorously established in several models. Can Consensus be easier than Broadcast? In models that allow noiseless communication, we prove a reduction of (a suitable variant of) Broadcast to binary Consensus, that preserves the communication model and all complexity parameters such as randomness, number of rounds, communication per round,...

Linear Time Subgraph Counting, Graph Degeneracy, and the Chasm at Size Six

Suman K. Bera, Noujan Pashanasangi & C. Seshadhri
We consider the problem of counting all k-vertex subgraphs in an input graph, for any constant k. This problem (denoted SUB-CNT_k) has been studied extensively in both theory and practice. In a classic result, Chiba and Nishizeki (SICOMP 85) gave linear time algorithms for clique and 4-cycle counting for bounded degeneracy graphs. This is a rich class of sparse graphs that contains, for example, all minor-free families and preferential attachment graphs. The techniques from this...

Parameterization Above a Multiplicative Guarantee

Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh & Meirav Zehavi
Parameterization above a guarantee is a successful paradigm in Parameterized Complexity. To the best of our knowledge, all fixed-parameter tractable problems in this paradigm share an additive form defined as follows. Given an instance (I,k) of some (parameterized) problem ? with a guarantee g(I), decide whether I admits a solution of size at least (at most) k+g(I). Here, g(I) is usually a lower bound (resp. upper bound) on the maximum (resp. minimum) size of a...

Computationally Data-Independent Memory Hard Functions

Mohammad Hassan Ameri, Jeremiah Blocki & Samson Zhou
Memory hard functions (MHFs) are an important cryptographic primitive that are used to design egalitarian proofs of work and in the construction of moderately expensive key-derivation functions resistant to brute-force attacks. Broadly speaking, MHFs can be divided into two categories: data-dependent memory hard functions (dMHFs) and data-independent memory hard functions (iMHFs). iMHFs are resistant to certain side-channel attacks as the memory access pattern induced by the honest evaluation algorithm is independent of the potentially sensitive...

Equivalence of Systematic Linear Data Structures and Matrix Rigidity

Sivaramakrishnan Natarajan Ramamoorthy & Cyrus Rashtchian
Recently, Dvir, Golovnev, and Weinstein have shown that sufficiently strong lower bounds for linear data structures would imply new bounds for rigid matrices. However, their result utilizes an algorithm that requires an NP oracle, and hence, the rigid matrices are not explicit. In this work, we derive an equivalence between rigidity and the systematic linear model of data structures. For the n-dimensional inner product problem with m queries, we prove that lower bounds on the...

Learning and Testing Variable Partitions

Andrej Bogdanov & Baoxiang Wang
Let F be a multivariate function from a product set ?^n to an Abelian group G. A k-partition of F with cost ? is a partition of the set of variables V into k non-empty subsets (X_1, ?s, X_k) such that F(V) is ?-close to F_1(X_1)+ ?s+F_k(X_k) for some F_1, ?s, F_k with respect to a given error metric. We study algorithms for agnostically learning k partitions and testing k-partitionability over various groups and error...

Registration Year

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

Resource Types

  • Text
  • Software