Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > LOWER BOUND:
Reports tagged with lower bound:
TR94-011 | 12th December 1994
R. Beigel, W. Hurwood, N. Kahale

#### Fault Diagnosis in a Flash

We consider the fault diagnosis problem: how to use parallel testing
rounds to identify which processors in a set are faulty. We prove
that 4 rounds suffice when 3% or less of the processors are faulty,
and 4 rounds are necessary when any nontrivial constant fraction of
the processors are ... more >>>

TR95-001 | 1st January 1995
Amos Beimel, Anna Gal, Michael S. Paterson

#### Lower Bounds for Monotone Span Programs

The model of span programs is a linear algebraic model of
computation. Lower bounds for span programs imply lower bounds for
contact schemes, symmetric branching programs and for formula size.
Monotone span programs correspond also to linear secret-sharing schemes.
We present a new technique for proving lower bounds for ... more >>>

TR96-063 | 6th November 1996
Martin Dietzfelbinger

#### The Linear-Array Problem in Communication Complexity Resolved

Tiwari (1987) considered the following scenario: k+1 processors P_0,...,P_k,
connected by k links to form a linear array, compute a function f(x,y), for
inputs (x,y) from a finite domain X x Y, where x is only known to P_0 and
y is only known to P_k; the intermediate ... more >>>

TR97-008 | 16th March 1997
Noam Nisan, Ziv Bar-Yossef

#### Pointer Jumping Requires Concurrent Read

We consider the well known problem of determining the k'th
vertex reached by chasing pointers in a directed graph of
out-degree 1. The famous "pointer doubling" technique
provides an O(log k) parallel time algorithm on a
Concurrent-Read Exclusive-Write (CREW) PRAM. We prove that ... more >>>

TR98-015 | 16th January 1998
Valentin E. Brimkov, Stefan S. Dantchev

#### Lower Bounds, "Pseudopolynomial" and Approximation Algorithms for the Knapsack Problem with Real Coefficients

In this paper we study the Boolean Knapsack problem (KP$_{{\bf R}}$)
$a^Tx=1$, $x \in \{0,1\}^n$ with real coefficients, in the framework
of the Blum-Shub-Smale real number computational model \cite{BSS}.
We obtain a new lower bound
$\Omega \left( n\log n\right) \cdot f(1/a_{\min})$ for the time
complexity ... more >>>

TR98-035 | 8th May 1998
Maria Luisa Bonet, Juan Luis Esteban, Jan Johannsen

#### Exponential Separations between Restricted Resolution and Cutting Planes Proof Systems

We prove an exponential lower bound for tree-like Cutting Planes
refutations of a set of clauses which has polynomial size resolution
refutations. This implies an exponential separation between tree-like
and dag-like proofs for both Cutting Planes and resolution; in both
cases only superpolynomial separations were known before.
In order to ... more >>>

TR98-077 | 19th December 1998
Miklos Ajtai

#### Determinism versus Non-Determinism for Linear Time RAMs with Memory Restrictions

Revisions: 1

Our computational model is a random access machine with $n$
read only input registers each containing $c \log n$ bits of
information and a read and write memory. We measure the time by the
number of accesses to the input registers. We show that for all $k$
there is ... more >>>

TR00-047 | 29th June 2000
Tobias Polzin, Siavash Vahdati Daneshmand

#### Primal-Dual Approaches to the Steiner Problem

We study several old and new algorithms for computing lower
and upper bounds for the Steiner problem in networks using dual-ascent
and primal-dual strategies. These strategies have been proven to be
very useful for the algorithmic treatment of the Steiner problem. We
show that none of the known algorithms ... more >>>

TR01-017 | 14th February 2001
Petr Savicky, Detlef Sieling

#### A Hierarchy Result for Read-Once Branching Programs with Restricted Parity Nondeterminism

Restricted branching programs are considered in complexity theory in
order to study the space complexity of sequential computations and
in applications as a data structure for Boolean functions. In this
paper (\oplus,k)-branching programs and (\vee,k)-branching
programs are considered, i.e., branching programs starting with a
... more >>>

TR01-056 | 6th August 2001
Michael Alekhnovich, Jan Johannsen, Alasdair Urquhart

#### An Exponential Separation between Regular and General Resolution

This paper gives two distinct proofs of an exponential separation
between regular resolution and unrestricted resolution.
The previous best known separation between these systems was
quasi-polynomial.

more >>>

TR02-020 | 13th March 2002
Elizaveta Okol'nishnikova

#### On one lower bound for branching programs

The method of obtaining lower bounds on the complexity
of Boolean functions for nondeterministic branching programs
is proposed.
A nonlinear lower bound on the complexity of characteristic
functions of Reed--Muller codes for nondeterministic
branching programs is obtained.

more >>>

TR02-060 | 15th July 2002
Ke Yang

#### New Lower Bounds for Statistical Query Learning

We prove two lower bounds on the Statistical Query (SQ) learning
model. The first lower bound is on weak-learning. We prove that for a
concept class of SQ-dimension $d$, a running time of
$\Omega(d/\log d)$ is needed. The SQ-dimension of a concept class is
defined to be the maximum number ... more >>>

TR03-014 | 28th February 2003
Avrim Blum, Ke Yang

#### On Statistical Query Sampling and NMR Quantum Computing

We introduce a Statistical Query Sampling'' model, in which
the goal of an algorithm is to produce an element in a hidden set
$S\subseteq\bit^n$ with reasonable probability. The algorithm
gains information about $S$ through oracle calls (statistical
queries), where the algorithm submits a query function $g(\cdot)$

TR05-043 | 5th April 2005
Emanuele Viola

#### Pseudorandom Bits for Constant-Depth Circuits with Few Arbitrary Symmetric Gates

We exhibit an explicitly computable pseudorandom' generator stretching $l$ bits into $m(l) = l^{\Omega(\log l)}$ bits that look random to constant-depth circuits of size $m(l)$ with $\log m(l)$ arbitrary symmetric gates (e.g. PARITY, MAJORITY). This improves on a generator by Luby, Velickovic and Wigderson (ISTCS '93) that achieves the same ... more >>>

TR05-066 | 4th June 2005
Jakob Nordström

#### Narrow Proofs May Be Spacious: Separating Space and Width in Resolution

The width of a resolution proof is the maximal number of literals in any clause of the proof. The space of a proof is the maximal number of memory cells used if the proof is only allowed to resolve on clauses kept in memory. Both of these measures have previously ... more >>>

TR06-027 | 22nd February 2006
Hermann Gruber, Markus Holzer

#### Finding Lower Bounds for Nondeterministic State Complexity is Hard

We investigate the following lower bound methods for regular
languages: The fooling set technique, the extended fooling set
technique, and the biclique edge cover technique. It is shown that
the maximal attainable lower bound for each of the above mentioned
techniques can be algorithmically deduced from ... more >>>

TR06-097 | 9th August 2006
Emanuele Viola

#### New correlation bounds for GF(2) polynomials using Gowers uniformity

We study the correlation between low-degree GF(2) polynomials p and explicit functions. Our main results are the following:

(I) We prove that the Mod_m unction on n bits has correlation at most exp(-Omega(n/4^d)) with any GF(2) polynomial of degree d, for any fixed odd integer m. This improves on the ... more >>>

TR07-079 | 11th August 2007
Emanuele Viola, Avi Wigderson

#### One-way multi-party communication lower bound for pointer jumping with applications

In this paper we study the one-way multi-party communication model,
in which every party speaks exactly once in its turn. For every
fixed $k$, we prove a tight lower bound of
$\Omega{n^{1/(k-1)}}$ on the probabilistic communication
complexity of pointer jumping in a $k$-layered tree, where the
pointers of the $i$-th ... more >>>

TR07-130 | 3rd December 2007
Ronen Shaltiel, Emanuele Viola

#### Hardness amplification proofs require majority

Hardness amplification is the fundamental task of
converting a $\delta$-hard function $f : {0,1}^n -> {0,1}$ into a $(1/2-\eps)$-hard function $Amp(f)$,
where $f$ is $\gamma$-hard if small circuits fail to
compute $f$ on at least a $\gamma$ fraction of the
inputs. Typically, $\eps,\delta$ are small (and
$\delta=2^{-k}$ captures the case ... more >>>

TR08-026 | 28th February 2008

#### Towards an Optimal Separation of Space and Length in Resolution

Most state-of-the-art satisfiability algorithms today are variants of
the DPLL procedure augmented with clause learning. The main bottleneck
for such algorithms, other than the obvious one of time, is the amount
of memory used. In the field of proof complexity, the resources of
time and memory correspond to the length ... more >>>

TR08-032 | 18th March 2008
Dmitriy Cherukhin

#### Lower Bounds for Boolean Circuits with Finite Depth and Arbitrary Gates

We consider bounded depth circuits over an arbitrary field $K$. If the field $K$ is finite, then we allow arbitrary gates $K^n\to K$. For instance, in the case of field $GF(2)$ we allow any Boolean gates. If the field $K$ is infinite, then we allow only polinomials.

For every fixed ... more >>>

TR08-076 | 17th June 2008
Ryan Williams

#### Non-Linear Time Lower Bound for (Succinct) Quantified Boolean Formulas

We prove a model-independent non-linear time lower bound for a slight generalization of the quantified Boolean formula problem (QBF). In particular, we give a reduction from arbitrary languages in alternating time t(n) to QBFs describable in O(t(n)) bits by a reasonable (polynomially) succinct encoding. The reduction works for many reasonable ... more >>>

TR08-110 | 19th November 2008
Chris Calabro

#### A Lower Bound on the Size of Series-Parallel Graphs Dense in Long Paths

One way to quantify how dense a multidag is in long paths is to find
the largest n, m such that whichever &le; n edges are removed, there is still
a path from an original input to an original output with &ge; m edges
- the larger ... more >>>

TR09-005 | 7th December 2008
Emanuele Viola

#### Bit-Probe Lower Bounds for Succinct Data Structures

We prove lower bounds on the redundancy necessary to
represent a set $S$ of objects using a number of bits
close to the information-theoretic minimum $\log_2 |S|$,
while answering various queries by probing few bits. Our
main results are:

\begin{itemize}
\item To represent $n$ ternary values $t \in \zot^n$ in ... more >>>

TR09-034 | 25th March 2009
Eli Ben-Sasson, Jakob Nordström

#### Understanding Space in Resolution: Optimal Lower Bounds and Exponential Trade-offs

For current state-of-the-art satisfiability algorithms based on the
DPLL procedure and clause learning, the two main bottlenecks are the
amounts of time and memory used. Understanding time and memory
consumption, and how they are related to one another, is therefore a
question of considerable practical importance. In the field of ... more >>>

TR09-054 | 7th June 2009
Emanuele Viola, Emanuele Viola

#### Cell-Probe Lower Bounds for Prefix Sums

We prove that to store n bits x so that each
prefix-sum query Sum(i) := sum_{k < i} x_k can be answered
by non-adaptively probing q cells of log n bits, one needs
memory > n + n/log^{O(q)} n.

Our bound matches a recent upper bound of n +
n/log^{Omega(q)} ... more >>>

TR10-087 | 17th May 2010
Shachar Lovett, Ely Porat

#### A lower bound for dynamic approximate membership data structures

An approximate membership data structure is a randomized data
structure for representing a set which supports membership
queries. It allows for a small false positive error rate but has
no false negative errors. Such data structures were first
introduced by Bloom in the 1970's, and have since had numerous
applications, ... more >>>

TR10-175 | 14th November 2010
Emanuele Viola

#### Randomness buys depth for approximate counting

Revisions: 1

We show that the promise problem of distinguishing $n$-bit strings of hamming weight $\ge 1/2 + \Omega(1/\log^{d-1} n)$ from strings of weight $\le 1/2 - \Omega(1/\log^{d-1} n)$ can be solved by explicit, randomized (unbounded-fan-in) poly(n)-size depth-$d$ circuits with error $\le 1/3$, but cannot be solved by deterministic poly(n)-size depth-$(d+1)$ circuits, ... more >>>

TR10-192 | 8th December 2010
Frederic Magniez, Ashwin Nayak, Miklos Santha, David Xiao

#### Improved bounds for the randomized decision tree complexity of recursive majority

Revisions: 1

We consider the randomized decision tree complexity of the recursive 3-majority function. For evaluating a height $h$ formulae, we prove a lower bound for the $\delta$-two-sided-error randomized decision tree complexity of $(1-2\delta)(5/2)^h$, improving the lower bound of $(1-2\delta)(7/3)^h$ given by Jayram et al. (STOC '03). We also state a conjecture ... more >>>

TR11-076 | 7th May 2011
Eric Miles, Emanuele Viola

#### The Advanced Encryption Standard, Candidate Pseudorandom Functions, and Natural Proofs

Revisions: 1

We put forth several simple candidate pseudorandom functions f_k : {0,1}^n -> {0,1} with security (a.k.a. hardness) 2^n that are inspired by the AES block-cipher by Daemen and Rijmen (2000). The functions are computable more efficiently, and use a shorter key (a.k.a. seed) than previous
constructions. In particular, we ... more >>>

TR11-150 | 4th November 2011
Anna Gal, Kristoffer Arnsfelt Hansen, Michal Koucky, Pavel Pudlak, Emanuele Viola

#### Tight bounds on computing error-correcting codes by bounded-depth circuits with arbitrary gates

We bound the minimum number $w$ of wires needed to compute any (asymptotically good) error-correcting code
$C:\{0,1\}^{\Omega(n)} \to \{0,1\}^n$ with minimum distance $\Omega(n)$,
using unbounded fan-in circuits of depth $d$ with arbitrary gates. Our main results are:

(1) If $d=2$ then $w = \Theta(n ({\log n/ \log \log n})^2)$.

(2) ... more >>>

TR11-152 | 12th November 2011
Emanuele Viola

Suppose each of $k \le n^{o(1)}$ players holds an $n$-bit number $x_i$ in its hand. The players wish to determine if $\sum_{i \le k} x_i = s$. We give a public-coin protocol with error $1\%$ and communication $O(k \lg k)$. The communication bound is independent of $n$, and for $k ... more >>> TR12-047 | 24th April 2012 Emanuele Viola #### Extractors for Turing-machine sources We obtain the first deterministic randomness extractors for$n$-bit sources with min-entropy$\ge n^{1-\alpha}$generated (or sampled) by single-tape Turing machines running in time$n^{2-16 \alpha}$, for all sufficiently small$\alpha > 0$. We also show that such machines cannot sample a uniform$n$-bit input to the Inner Product function ... more >>> TR12-098 | 3rd August 2012 Ankit Gupta, Pritish Kamath, Neeraj Kayal, Ramprasad Saptharishi #### An exponential lower bound for homogeneous depth four arithmetic circuits with bounded bottom fanin Revisions: 3 Agrawal and Vinay (FOCS 2008) have recently shown that an exponential lower bound for depth four homogeneous circuits with bottom layer of$\times$gates having sublinear fanin translates to an exponential lower bound for a general arithmetic circuit computing the permanent. Motivated by this, we examine the complexity of computing ... more >>> TR12-117 | 17th September 2012 Loïck Magnin, Jérémie Roland #### Explicit relation between all lower bound techniques for quantum query complexity The polynomial method and the adversary method are the two main techniques to prove lower bounds on quantum query complexity, and they have so far been considered as unrelated approaches. Here, we show an explicit reduction from the polynomial method to the multiplicative adversary method. The proof goes by extending ... more >>> TR12-141 | 22nd October 2012 Dmitry Itsykson, Dmitry Sokolov #### Lower bounds for myopic DPLL algorithms with a cut heuristic The paper is devoted to lower bounds on the time complexity of DPLL algorithms that solve the satisfiability problem using a splitting strategy. Exponential lower bounds on the running time of DPLL algorithms on unsatisfiable formulas follow from the lower bounds for resolution proofs. Lower bounds on satisfiable instances are ... more >>> TR13-015 | 18th January 2013 Iordanis Kerenidis, Mathieu Laurière, David Xiao #### New lower bounds for privacy in communication protocols Communication complexity is a central model of computation introduced by Yao in 1979, where two players, Alice and Bob, receive inputs x and y respectively and want to compute$f(x; y)$for some fixed function f with the least amount of communication. Recently people have revisited the question of the ... more >>> TR13-083 | 7th June 2013 Miklos Ajtai #### Lower Bounds for RAMs and Quantifier Elimination For each natural number$d$we consider a finite structure${\bf M}_{d}$whose universe is the set of all$0,1$-sequence of length$n=2^{d}$, each representing a natural number in the set$\lbrace 0,1,...,2^{n}-1\rbrace$in binary form. The operations included in the structure are the four constants$0,1,2^{n}-1,n$, multiplication and addition ... more >>> TR13-186 | 27th December 2013 Nitin Saxena #### Progress on Polynomial Identity Testing - II We survey the area of algebraic complexity theory; with the focus being on the problem of polynomial identity testing (PIT). We discuss the key ideas that have gone into the results of the last few years. more >>> TR14-005 | 14th January 2014 Neeraj Kayal, Nutan Limaye, Chandan Saha, Srikanth Srinivasan #### An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas We show here a$2^{\Omega(\sqrt{d} \cdot \log N)}$size lower bound for homogeneous depth four arithmetic formulas. That is, we give an explicit family of polynomials of degree$d$on$N$variables (with$N = d^3$in our case) with$0, 1$-coefficients such that for any representation of ... more >>> TR14-089 | 16th July 2014 Neeraj Kayal, Chandan Saha #### Lower Bounds for Depth Three Arithmetic Circuits with small bottom fanin Revisions: 1 Shpilka and Wigderson (CCC 1999) had posed the problem of proving exponential lower bounds for (nonhomogeneous) depth three arithmetic circuits with bounded bottom fanin over a field$\mathbb{F}$of characteristic zero. We resolve this problem by proving a$N^{\Omega(\frac{d}{\tau})}$lower bound for (nonhomogeneous) depth three arithmetic circuits with bottom fanin ... more >>> TR14-118 | 9th September 2014 Albert Atserias, Massimo Lauria, Jakob Nordström #### Narrow Proofs May Be Maximally Long We prove that there are 3-CNF formulas over n variables that can be refuted in resolution in width w but require resolution proofs of size n^Omega(w). This shows that the simple counting argument that any formula refutable in width w must have a proof in size n^O(w) is essentially tight. ... more >>> TR14-131 | 7th October 2014 Olaf Beyersdorff, Leroy Chew, Karteek Sreenivasaiah #### A game characterisation of tree-like Q-Resolution size We provide a characterisation for the size of proofs in tree-like Q-Resolution by a Prover-Delayer game, which is inspired by a similar characterisation for the proof size in classical tree-like Resolution. This gives the first successful transfer of one of the lower bound techniques for classical proof systems to QBF ... more >>> TR15-053 | 7th April 2015 Massimo Lauria, Jakob Nordström #### Tight Size-Degree Bounds for Sums-of-Squares Proofs We exhibit families of 4-CNF formulas over n variables that have sums-of-squares (SOS) proofs of unsatisfiability of degree (a.k.a. rank) d but require SOS proofs of size n^{Omega(d)} for values of d = d(n) from constant all the way up to n^{delta} for some universal constant delta. This shows that ... more >>> TR15-078 | 4th May 2015 Mladen Mikša, Jakob Nordström #### A Generalized Method for Proving Polynomial Calculus Degree Lower Bounds We study the problem of obtaining lower bounds for polynomial calculus (PC) and polynomial calculus resolution (PCR) on proof degree, and hence by [Impagliazzo et al. '99] also on proof size. [Alekhnovich and Razborov '03] established that if the clause-variable incidence graph of a CNF formula F is a good ... more >>> TR17-017 | 5th February 2017 Michal Moshkovitz, Dana Moshkovitz #### Mixing Implies Lower Bounds for Space Bounded Learning One can learn any hypothesis class$H$with$O(\log|H|)$labeled examples. Alas, learning with so few examples requires saving the examples in memory, and this requires$|X|^{O(\log|H|)}$memory states, where$X$is the set of all labeled examples. A question that arises is how many labeled examples are needed in ... more >>> TR17-077 | 30th April 2017 Guillaume Lagarde, Nutan Limaye, Srikanth Srinivasan #### Lower Bounds and PIT for Non-Commutative Arithmetic circuits with Restricted Parse Trees We investigate the power of Non-commutative Arithmetic Circuits, which compute polynomials over the free non-commutative polynomial ring$\mathbb{F}\langle x_1,\dots,x_N \rangle$, where variables do not commute. We consider circuits that are restricted in the ways in which they can compute monomials: this can be seen as restricting the families of parse ... more >>> TR18-053 | 19th March 2018 Nader Bshouty #### Lower Bound for Non-Adaptive Estimate the Number of Defective Items We prove that to estimate within a constant factor the number of defective items in a non-adaptive group testing algorithm we need at least$\tilde\Omega((\log n)(\log(1/\delta)))$tests. This solves the open problem posed by Damaschke and Sheikh Muhammad. more >>> TR18-096 | 13th May 2018 Venkatesan Guruswami, Andrii Riazanov #### Beating Fredman-Komlós for perfect$k$-hashing We say a subset$C \subseteq \{1,2,\dots,k\}^n$is a$k$-hash code (also called$k$-separated) if for every subset of$k$codewords from$C$, there exists a coordinate where all these codewords have distinct values. Understanding the largest possible rate (in bits), defined as$(\log_2 |C|)/n$, of a$k$-hash code is ... more >>> TR18-140 | 11th August 2018 Ilan Komargodski, Ran Raz, Yael Tauman Kalai #### A Lower Bound for Adaptively-Secure Collective Coin-Flipping Protocols Revisions: 1 In 1985, Ben-Or and Linial (Advances in Computing Research '89) introduced the collective coin-flipping problem, where$n$parties communicate via a single broadcast channel and wish to generate a common random bit in the presence of adaptive Byzantine corruptions. In this model, the adversary can decide to corrupt a party ... more >>> TR19-005 | 16th January 2019 Omar Alrabiah, Venkatesan Guruswami #### An Exponential Lower Bound on the Sub-Packetization of MSR Codes An$(n,k,\ell)$-vector MDS code is a$\mathbb{F}$-linear subspace of$(\mathbb{F}^\ell)^n$(for some field$\mathbb{F}$) of dimension$k\ell$, such that any$k$(vector) symbols of the codeword suffice to determine the remaining$r=n-k$(vector) symbols. The length$\ell$of each codeword symbol is called the sub-packetization of the code. Such a ... more >>> TR19-065 | 1st May 2019 Mrinal Kumar, Ramprasad Saptharishi, Noam Solomon #### Derandomization from Algebraic Hardness: Treading the Borders Revisions: 3 A hitting-set generator (HSG) is a polynomial map$Gen:\mathbb{F}^k \to \mathbb{F}^n$such that for all$n$-variate polynomials$Q$of small enough circuit size and degree, if$Q$is non-zero, then$Q\circ Gen$is non-zero. In this paper, we give a new construction of such a HSG assuming that we have ... more >>> TR19-172 | 28th November 2019 Prasad Chaugule, Mrinal Kumar, Nutan Limaye, Chandra Kanta Mohapatra, Adrian She, Srikanth Srinivasan #### Schur Polynomials do not have small formulas if the Determinant doesn't! Schur Polynomials are families of symmetric polynomials that have been classically studied in Combinatorics and Algebra alike. They play a central role in the study of Symmetric functions, in Representation theory [Sta99], in Schubert calculus [LM10] as well as in Enumerative combinatorics [Gas96, Sta84, Sta99]. In recent years, they have ... more >>> TR19-178 | 5th December 2019 Dmitry Itsykson, Artur Riazanov, Danil Sagunov, Petr Smirnov #### Almost Tight Lower Bounds on Regular Resolution Refutations of Tseitin Formulas for All Constant-Degree Graphs We show that the size of any regular resolution refutation of Tseitin formula$T(G,c)$based on a graph$G$is at least$2^{\Omega(tw(G)/\log n)}$, where$n$is the number of vertices in$G$and$tw(G)$is the treewidth of$G$. For constant degree graphs there is known upper bound$2^{O(tw(G))}$... more >>> TR19-182 | 9th December 2019 Zachary Remscrim #### The Limitations of Few Qubits: One-way and Two-way Quantum Finite Automata and the Group Word Problem Revisions: 1 The two-way finite automaton with quantum and classical states (2QCFA), defined by Ambainis and Watrous, is a model of quantum computation whose quantum part is extremely limited; however, as they showed, 2QCFA are surprisingly powerful: a 2QCFA with only a single-qubit can recognize the language$L_{pal}=\{w \in \{a,b\}^*:w \text{ is ... more >>>

TR20-067 | 30th April 2020
Dmitry Itsykson, Alexander Okhotin, Vsevolod Oparin

#### Computational and proof complexity of partial string avoidability

The partial string avoidability problem is stated as follows: given a finite set of strings with possible holes'' (wildcard symbols), determine whether there exists a two-sided infinite string containing no substrings from this set, assuming that a hole matches every symbol. The problem is known to be NP-hard and in ... more >>>

TR20-071 | 4th May 2020
Iftach Haitner, Yonatan Karidi-Heller

#### A Tight Lower Bound on Adaptively Secure Full-Information Coin Flip

Revisions: 1

In a distributed coin-flipping protocol, Blum [ACM Transactions on Computer Systems '83],
the parties try to output a common (close to) uniform bit, even when some adversarially chosen parties try to bias the common output. In an adaptively secure full-information coin flip, Ben-Or and Linial [FOCS '85], the parties communicate ... more >>>

TR21-050 | 2nd April 2021
Marshall Ball, Alper Cakan, Tal Malkin

#### Linear Threshold Secret-Sharing with Binary Reconstruction

Motivated in part by applications in lattice-based cryptography, we initiate the study of the size of linear threshold ($t$-out-of-$n$') secret-sharing where the linear reconstruction function is restricted to coefficients in $\{0,1\}$. We prove upper and lower bounds on the share size of such schemes. One ramification of our results is ... more >>>

ISSN 1433-8092 | Imprint