Search

We introduce the problem of constructing explicit variety evasive subspace families. Given a family F of subvarieties of a projective or affine space, a collection H of projective or affine k -subspaces is (F , ϵ) -evasive if for every V ∈ F , all but at most ϵ -fraction of W ∈ H intersect every irreducible component of V with (at most) the expected dimension. The problem of constructing such an explicit subspace family generalizes both deterministic black-box polynomial identity testing (PIT) and the problem of constructing explicit (weak) lossless rank condensers. Using Chow forms, we construct explicit k -subspace families of polynomial size that are evasive for all varieties of bounded degree in a projective or affine n -space. As one application, we obtain a complete derandomization of Noether’s normalization lemma for varieties of low degree in a projective or affine n -space. In another application, we obtain a simple polynomial-time black-box PIT algorithm for depth-4 arithmetic circuits with bounded top fan-in and bottom fan-in that are not in the Sylvester–Gallai configuration, improving and simplifying a result of Gupta (ECCC TR 14-130). As a complement of our explicit construction, we prove a tight lower bound for the size of k -subspace families that are evasive for degree- d varieties in a projective n -space. When n - k = n Ω (1) , the lower bound is superpolynomial unless d is bounded. The proof uses a dimension counting argument on Chow varieties that parametrize projective subvarieties. [ABSTRACT FROM AUTHOR]

Proving superlogarithmic data structure lower bounds in the static group model has been a fundamental challenge in computational geometry since the early '80s. We prove a polynomial (n\Omega (1)) lower bound for an explicit range counting problem of n3 convex polygons in R2 (each with n \~ O(1) facets/semialgebraic complexity), against linear storage arithmetic data structures in the group model. Our construction and analysis are based on a combination of techniques in Diophantine approximation, pseudorandomness, and compressed sensing--in particular, on the existence and partial derandomization of optimal binary compressed sensing matrices in the polynomial sparsity regime (k = n1 \delta). As a byproduct, this establishes a (logarithmic) separation between compressed sensing matrices and the stronger RIP property. [ABSTRACT FROM AUTHOR]

The classic Impagliazzo–Nisan–Wigderson (INW) pseudorandom generator (PRG) (STOC '94) for space-bounded computation uses a seed of length O (log n · log (n w / ε) + log d) to fool ordered branching programs of length n, width w, and alphabet size d to within error ε . A series of works have shown that the analysis of the INW generator can be improved for the class of permutation branching programs or the more general regular branching programs, improving the O (log 2 n) dependence on the length n to O (log n) or O ~ (log n) . However, when also considering the dependence on the other parameters, these analyses still fall short of the optimal PRG seed length O (log (n w d / ε)) . In this paper, we prove that any "spectral analysis" of the INW generator requires seed length Ω log n · log log min { n , d } + log n · log w / ε + log d to fool ordered permutation branching programs of length n, width w, and alphabet size d to within error ε . By "spectral analysis" we mean an analysis of the INW generator that relies only on the spectral expansion of the graphs used to construct the generator; this encompasses all prior analyses of the INW generator. Our lower bound matches the upper bound of Braverman–Rao–Raz–Yehudayoff (FOCS 2010, SICOMP 2014) for regular branching programs of alphabet size d = 2 except for a gap between their O log n · log log n term and our Ω log n · log log min { n , d } term. It also matches the upper bounds of Koucký–Nimbhorkar–Pudlák (STOC 2011), De (CCC 2011), and Steinke (ECCC 2012) for constant-width ( w = O (1) ) permutation branching programs of alphabet size d = 2 to within a constant factor. To fool permutation branching programs in the measure of spectral norm, we prove that any spectral analysis of the INW generator requires a seed of length Ω log n · log log n + log n · log (1 / ε) when the width is at least polynomial in n ( w = n Ω (1) ), matching the recent upper bound of Hoza–Pyne–Vadhan (ITCS 2021) to within a constant factor. [ABSTRACT FROM AUTHOR]

We give new constructions of two classes of algebraic code families that are efficiently list decodable with small output list size from a fraction 1 - R - ε of adversarial errors, where R is the rate of the code, for any desired positive constant ε. The alphabet size depends only ε and is nearly optimal. The first class of codes are obtained by folding algebraic-geometric codes using automorphisms of the underlying function field. The second class of codes are obtained by restricting evaluation points of an algebraicgeometric code to rational points from a subfield. In both cases, we develop a linear-algebraic approach to perform list decoding, which pins down the candidate messages to a subspace with a nice "periodic" structure. To prune this subspace and obtain a good bound on the list size, we pick subcodes of these codes by pre-coding into certain subspace-evasive sets that are guaranteed to have small intersection with the sort of periodic subspaces that arise in our list decoding. We develop two approaches for constructing such subspaceevasive sets. The first is a Monte Carlo construction of hierearchical subspace-evasive (h.s.e.) sets that leads to excellent list size but is not explicit. The second approach exploits a further ultra-periodicity of our subspaces and uses a novel construct called subspace designs, which were subsequently constructed explicitly and also found further applications in pseudorandomness. To get a family of codes over a fixed alphabet size, we instantiate our approach with algebraic-geometric codes based on the Garcia-Stichtenoth tower of function fields. Combining this with pruning via h.s.e. sets yields codes list-decodable up to a 1 - R - ε error fraction with list size bounded by O(1/ε), matching the existential bound for random codes up to constant factors. Further, the alphabet size can be made exp(˜O (1/ε2)), which is not much worse than the lower bound of exp(Ω(1/ε)). The parameters we achieve are thus quite close to the existential bounds in all three aspects (error-correction radius, alphabet size, and list size) simultaneously. This construction is, however, Monte Carlo and the claimed list-decoding property only holds with high probability. Once the code is (efficiently) sampled, the encoding/decoding algorithms are deterministic with a running time Oε (Nc) for an absolute constant c, where N is the code's block length. Using subspace designs instead for the pruning, our approach yields the first deterministic construction of an algebraic code family of rate R with efficient list decoding from 1 - R - ε fraction of errors over an alphabet of constant size exp(˜O (1/ε2)). The list-size bound is upper bounded by a very slowly growing function of the block length N; in particular, it is at most O(log(r) N) (the r th iterated logarithm) for any fixed integer r. The explicit construction avoids the shortcoming of the Monte Carlo sampling at the expense of a slightly worse list size. [ABSTRACT FROM AUTHOR]

We construct an infinite family of bounded-degree bipartite unique neighbour expander graphs with arbitrarily unbalanced sides. Although weaker than the lossless expanders constructed by Capalbo et al., our construction is simpler and may be closer to being implementable in practice, due to the smaller constants. We construct these graphs by composing bipartite Ramanujan graphs with a fixed-size gadget in a way that generalises the construction of unique neighbour expanders by Alon and Capalbo. For the analysis of our construction, we prove a strong upper bound on average degrees in small induced subgraphs of bipartite Ramanujan graphs. Our bound generalises Kahale's average degree bound to bipartite Ramanujan graphs, and may be of independent interest. Surprisingly, our bound strongly relies on the exact Ramanujan-ness of the graph and is not known to hold for nearly-Ramanujan graphs. [ABSTRACT FROM AUTHOR]

An m-sequence is the one of the largest period among those produced by a linear feedback shift register. It possesses several desirable features of pseudorandomness such as balance, uniform pattern distribution and ideal autocorrelation for applications to communications. However, it also possesses undesirable features such as low linear complexity. Here we prove a nontrivial upper bound on its arithmetic autocorrelation, another figure of merit introduced by Mandelbaum for error-correcting codes and later investigated by Goresky and Klapper for FCSRs. The upper bound is close to half of the period and hence rather large, which gives an undesirable feature. [ABSTRACT FROM AUTHOR]

Abstract The arithmetic correlations of two binary half‐ℓ‐sequences with connection integer pr, which is an odd prime power, are investigated. Possible values (of the arithmetic correlation) are calculated. In particular, if p ≡ 1 (mod 8), the authors prove that they are zero for non‐trivial shifts, that is, the half‐ℓ‐sequences have ideal arithmetic correlations. If p ≡ −1 (mod 8), an upper bound, which is of order of magnitude pr−1/2 ln p, is derived by using earlier results on the imbalance of half‐ℓ‐sequences with connection integer p studied by Gu and Klapper and later improved by Wang and Tan.

In the second half of the 1990's Christian Mauduit and András Sárközy introduced a new quantitative theory of pseudorandomness of binary sequences. Since then numerous papers have been written on this subject and the original theory was generalized in several directions. In this paper, I summarize some of the most notable results in the field. I compare four different constructions in the computational point of view. The first construction is the classic Legendre symbol construction, and the other three are construction based on digits of famous constants such as e, π, and v √2. I used SAGE, PYTHON, and MATLAB as programming languages. I run multiple tests and calculated the exact values of the pseudorandom measures for each construction in many cases and the runtime are also presented. [ABSTRACT FROM AUTHOR]

This work presents two codesign implementations of a true random number generation mechanism. Physical components provided by the programmable logic of FPGA are used for true random seed generation. The seed conditioning and generation of the large sequences were implemented using the block cipher Advanced Encryption Standard (AES) implemented on the Cortex-A9 processor (embedded in the Zynq FPGA) or specific AESNI instructions in modern processors. Our implementations use less than 10% of the available resources on the target FPGAs and pass all the National Institute of Standards and Technology (NIST) tests for random generators. [ABSTRACT FROM AUTHOR]

The arithmetic correlations of two binary half‐ℓ‐sequences with connection integer pr, which is an odd prime power, are investigated. Possible values (of the arithmetic correlation) are calculated. In particular, if p ≡ 1 (mod 8), the authors prove that they are zero for non‐trivial shifts, that is, the half‐ℓ‐sequences have ideal arithmetic correlations. If p ≡ −1 (mod 8), an upper bound, which is of order of magnitude pr−1/2 ln p, is derived by using earlier results on the imbalance of half‐ℓ‐sequences with connection integer p studied by Gu and Klapper and later improved by Wang and Tan. [ABSTRACT FROM AUTHOR]

Pseudorandomness is a crucial property that the designers of cryptographic primitives aim to achieve. It is also a key requirement in the calls for proposals of new primitives, as in the case of block ciphers. Therefore, the assessment of the property is an important issue to deal with. Currently, an interesting research line is the understanding of how powerful machine learning methods are in distinguishing pseudorandom objects from truly random objects. Moving along such a research line, in this paper a deep learning-based pseudorandom distinguisher is developed and trained for two well-known lightweight ciphers, Speck and Simon. Specifically, the distinguisher exploits a convolutional Siamese network for distinguishing the outputs of these ciphers from random sequences. Experiments with different instances of Speck and Simon show that the proposed distinguisher highly able to distinguish between the two types of sequences, with an average accuracy of 99.5 % for Speck and 99.6 % for Simon. Hence, the proposed method could significantly impact the security of these cryptographic primitives and of the applications in which they are used. [ABSTRACT FROM AUTHOR]

Beacons are small devices which are playing an important role in the Internet of Things (IoT), connecting “things” without IP connection to the Internet via Bluetooth Low Energy (BLE) communication. In this paper we present the first private end-to-end encryption protocol called the Eddystone-Ephemeral-ID (Eddystone-EID) protocol. This protocol enables connectivity from any beacon to its remote owner, while supporting beacon’s privacy and security, and essentially preserving the beacon’s low power consumption. We describe the Eddystone-EID development goals, discuss the design decisions, show the cryptographic solution, and analyse its privacy, security, and performance. Finally, we present three secure IoT applications built on Eddystone-EID, demonstrating its utility as a security and privacy infrastructure in the IoT domain. Further, Eddystone-EID is a prototypical example of security design for an asymmetric system in which on one side there are small power-deficient elements (the beacons) and on the other side there is a powerful computing engine (a cloud). The crux of the design strategy is based on: (1) transferring work from the beacon to the cloud, and then (2) building a trade-off between cloud online work against cloud offline work, in order to enable fast real-time reaction of the cloud. These two principles seem to be generic and can be used for other problems in the IoT domain. [ABSTRACT FROM AUTHOR]

Many automatic sequences, such as the Thue-Morse sequence or the Rudin-Shapiro sequence, have some desirable features of pseudorandomness such as a large linear complexity and a small well-distribution measure. However, they also have some undesirable properties in view of certain applications. For example, the majority of possible binary patterns never appears in automatic sequences and their correlation measure of order 2 is extremely large. Certain subsequences, such as automatic sequences along squares, may keep the good properties of the original sequence but avoid the bad ones. In this survey we investigate properties of pseudorandomness and non-randomness of automatic sequences and their subsequences and present results on their behaviour under several measures of pseudorandomness including linear complexity, correlation measure of order k, expansion complexity and normality. We also mention some analogs for finite fields. [ABSTRACT FROM AUTHOR]

We present an explicit and efficient algebraic construction of capacity-achieving list decodable codes with both constant alphabet and constant list sizes. More specifically, for any $R \in (0,1)$ and $\epsilon >0$ , we give an algebraic construction of an infinite family of error-correcting codes of rate $R$ , over an alphabet of size $(1/\epsilon)^{O(1/\epsilon ^{2})}$ , that can be list decoded from a $(1-R-\epsilon)$ -fraction of errors with list size at most $\exp (\mathrm {poly}(1/ \epsilon))$. Moreover, the codes can be encoded in time $\mathrm {poly}(1/ \epsilon,n)$ , the output list is contained in a linear subspace of dimension at most $\mathrm {poly}(1/ \epsilon)$ , and a basis for this subspace can be found in time $\mathrm {poly}(1 /\epsilon, n)$. Thus, both encoding and list decoding can be performed in fully polynomial-time $\mathrm {poly}(1/ \epsilon,n)$ , except for pruning the subspace and outputting the final list which takes time $\exp (\mathrm {poly}(1/ \epsilon)) \cdot \mathrm {poly} (n)$. In contrast, prior explicit and efficient constructions of capacity-achieving list decodable codes either required a much higher complexity in terms of $1/ \epsilon $ (and were additionally much less structured), or had super-constant alphabet or list sizes. Our codes are quite natural and structured. Specifically, we use algebraic-geometric (AG) codes with evaluation points restricted to a subfield, and with the message space restricted to a (carefully chosen) linear subspace. Our main observation is that the output list of AG codes with subfield evaluation points is contained in an affine shift of the image of a block-triangular-Toeplitz (BTT) matrix, and that the list size can potentially be reduced to a constant by restricting the message space to a BTT evasive subspace, which is a large subspace that intersects the image of any BTT matrix in a constant number of points. We further show how to explicitly construct such BTT evasive subspaces, based on the explicit subspace designs of Guruswami and Kopparty (Combinatorica, 2016), and composition. [ABSTRACT FROM AUTHOR]

Pseudorandomness is a crucial property that the designers of cryptographic primitives aim to achieve. It is also a key requirement in the calls for proposals of new primitives, as in the case of block ciphers. Therefore, the assessment of the property is an important issue to deal with. Currently, an interesting research line is the understanding of how powerful machine learning methods are in distinguishing pseudorandom objects from truly random objects. Moving along such a research line, in this paper a deep learning-based pseudorandom distinguisher is developed and trained for two well-known lightweight ciphers, Speck and Simon. Specifically, the distinguisher exploits a convolutional Siamese network for distinguishing the outputs of these ciphers from random sequences. Experiments with different instances of Speck and Simon show that the proposed distinguisher highly able to distinguish between the two types of sequences, with an average accuracy of 99.5% for Speck and 99.6% for Simon. Hence, the proposed method could significantly impact the security of these cryptographic primitives and of the applications in which they are used.

We consider coding schemes for computationally bounded channels, which can introduce an arbitrary set of errors as long as (a) the fraction of errors is bounded with high probability by a parameter p and (b) the process that adds the errors can be described by a sufficiently "simple" circuit. Codes for such channel models are attractive since, like codes for standard adversarial errors, they can handle channels whose true behavior is unknown or varying over time. For two classes of channels, we provide explicit, efficiently encodable/decodable codes of optimal rate where only inefficiently decodable codes were previously known. In each case, we provide one encoder/decoder that works for every channel in the class. The encoders are randomized, and probabilities are taken over the (local, unknown to the decoder) coins of the encoder and those of the channel. Unique decoding for additive errors: We give the first construction of a polynomial-time encodable/ decodable code for additive (a.k.a. oblivious) channels that achieve the Shannon capacity 1 - H(p). These are channels that add an arbitrary error vector e ∊ {0, 1}N of weight at most pN to the transmitted word; the vector e can depend on the code but not on the randomness of the encoder or the particular transmitted word. Such channels capture binary symmetric errors and burst errors as special cases. List decoding for polynomial-time channels: For every constant c > 0, we construct codes with optimal rate (arbitrarily close to 1 - H(p)) that efficiently recover a short list containing the correct message with high probability for channels describable by circuits of size at most Nc. Our construction is not fully explicit but rather Monte Carlo (we give an algorithm that, with high probability, produces an encoder/decoder pair that works for all time Nc channels). We are not aware of any channel models considered in the information theory literature other than purely adversarial channels, which require more than linear-size circuits to implement. We justify the relaxation to list decoding with an impossibility result showing that, in a large range of parameters (p > 1/4), codes that are uniquely decodable for a modest class of channels (online, memoryless, nonuniform channels) cannot have positive rate. [ABSTRACT FROM AUTHOR]

We consider a generalized construction of stream ciphers with forward security. The design framework is modular: it is built from a so-called layer function that updates the key and (optionally) the nonce and generates a new pseudorandom output stream. We analyze the generalized construction for four different instantiations: two possible layer functions that are in turn instantiated with either a block cipher or a pseudorandom function. We prove that each of these instantiations gives a stream cipher that is pseudorandom and forward secure in the multi-user setting with a very tight bound. A comprehensive analysis shows that the two block cipher based instantiations achieve very similar bounds. For the pseudorandom function based instantiations there is no clear winner: either layer can be beneficial over the other one, depending on the choice of parameters. By instantiating the pseudorandom function with a generic construction such as the sum of permutations, we obtain a highly efficient and competitive stream cipher based on an n-bit block cipher that is secure beyond the $2^{\text {n}/2}$ birthday bound. [ABSTRACT FROM AUTHOR]

Mauduit and Sárközy proved the following inequality between the well-distribution measure and the correlation measure of order 2: W (E N) ≤ 3 N C 2 (E N) . This result has been generalized to inequalities between the combined pseudorandom measures and correlation measures of even order by the authors of the present paper. Here the multidimensional case is studied, and this inequality is extended further to the case of binary lattices. [ABSTRACT FROM AUTHOR]

In cryptography one needs pseudorandom sequences whose short subsequences are also pseudorandom. To handle this problem, Dartyge, Gyarmati and Sárközy introduced weighted measures of pseudorandomness of binary sequences. In this paper we continue the research in this direction. We introduce weighted pseudorandom measure for multidimensional binary lattices and estimate weighted pseudorandom measure for truly random binary lattices. We also give lower bounds for weighted measures of even order and present an example by using the quadratic character of finite fields. [ABSTRACT FROM AUTHOR]

Automatic sequences are not suitable sequences for cryptographic applications since both their subword complexity and their expansion complexity are small, and their correlation measure of order 2 is large. These sequences are highly predictable despite having a large maximum order complexity. However, recent results show that polynomial subsequences of automatic sequences, such as the Thue–Morse sequence, are better candidates for pseudorandom sequences. A natural generalization of automatic sequences are morphic sequences, given by a fixed point of a prolongeable morphism that is not necessarily uniform. In this paper we prove a lower bound for the maximum order complexity of the sum of digits function in Zeckendorf base which is an example of a morphic sequence. We also prove that the polynomial subsequences of this sequence keep large maximum order complexity, such as the Thue–Morse sequence. [ABSTRACT FROM AUTHOR]

Let 1 < g1 < . . . < gφ(p−1) < p−1 be the ordered primitive roots modulo p. We study the pseudorandomness of the binary sequence (sn) defined by sn ≡ gn+1 + gn+2mod 2, n = 0,1, . . . In particular, we study the balance, linear complexity and 2-adic complexity of (sn). We show that for a typical p the sequence (sn) is quite unbalanced. However, there are still infinitely many p such that (sn) is very balanced. We also prove similar results for the distribution of longer patterns. Moreover, we give general lower bounds on the linear complexity and 2-adic complexity of (sn) and state sufficient conditions for attaining their maximums. Hence, for carefully chosen p, these sequences are attractive candidates for cryptographic applications. [ABSTRACT FROM AUTHOR]

We strengthen the notion of double samplers, first introduced by Dinur and Kaufman ["High dimensional expanders imply agreement expanders," in Proc. 58th IEEE Symp. on Foundations of Comp. Science, IEEE, 2017, pp. 974-985], which are samplers with additional combinatorial properties, and whose existence we prove using high-dimensional expanders. The ABNNR code construction [N. Alon et al., IEEE Trans. Inform. Theory, 38 (1992), pp. 509-516] achieves large distance by starting with a base code C with moderate distance, and then amplifying the distance using a sampler. We show that if the sampler is part of a larger double sampler, then the construction has an efficient list-decoding algorithm. Our algorithm works even if the ABNNR construction is not applied to a base code C but rather to any string. In this case the resulting code is approximate-list-decodable, i.e., the output list contains an approximation to the original input. Our list-decoding algorithm works as follows: It uses a local voting scheme from which it constructs a unique games constraint graph. The constraint graph is an expander, so we can solve unique games efficiently. These solutions are the output of the list-decoder. This is a novel use of a unique games algorithm as a subroutine in a decoding procedure, as opposed to the more common situation in which unique games are used for demonstrating hardness results. Double samplers and high-dimensional expanders are akin to pseudorandom objects in their utility, but they greatly exceed random objects in their combinatorial properties. We believe that these objects hold significant potential for coding theoretic constructions and view this work as demonstrating the power of double samplers in this context. [ABSTRACT FROM AUTHOR]

A stochastic code is a pair of encoding and decoding procedures (Enc, Dec) where Enc : { 0 , 1 } k × { 0 , 1 } d → { 0 , 1 } n . The code is (p, L)-list decodable against a class C of “channel functions” C : { 0 , 1 } n → { 0 , 1 } n if for every message m ∈ { 0 , 1 } k and every channel C ∈ C that induces at most pn errors, applying Dec on the “received word” C(Enc(m,S)) produces a list of at most L messages that contain m with high probability over the choice of uniform S ← { 0 , 1 } d . Note that both the channel C and the decoding algorithm Dec do not receive the random variable S, when attempting to decode. The rate of a code is R = k / n , and a code is explicit if Enc, Dec run in time poly(n). Guruswami and Smith (Journal of the ACM, 2016) showed that for every constants 0 < p < 1 2 , ϵ > 0 and c > 1 there exist a constant L and a Monte Carlo explicit constructions of stochastic codes with rate R ≥ 1 - H (p) - ϵ that are (p, L)-list decodable for size n c channels. Here, Monte Carlo means that the encoding and decoding need to share a public uniformly chosen poly (n c) bit string Y, and the constructed stochastic code is (p, L)-list decodable with high probability over the choice of Y. Guruswami and Smith pose an open problem to give fully explicit (that is not Monte Carlo) explicit codes with the same parameters, under hardness assumptions. In this paper, we resolve this open problem, using a minimal assumption: the existence of poly-time computable pseudorandom generators for small circuits, which follows from standard complexity assumptions by Impagliazzo and Wigderson (STOC 97). Guruswami and Smith also asked to give a fully explicit unconditional constructions with the same parameters against O (log n) -space online channels. (These are channels that have space O (log n) and are allowed to read the input codeword in one pass.) We also resolve this open problem. Finally, we consider a tighter notion of explicitness, in which the running time of encoding and list-decoding algorithms does not increase, when increasing the complexity of the channel. We give explicit constructions (with rate approaching 1 - H (p) for every p ≤ p 0 for some p 0 > 0 ) for channels that are circuits of size 2 n Ω (1 / d) and depth d. Here, the running time of encoding and decoding is a polynomial that does not depend on the depth of the circuit. Our approach builds on the machinery developed by Guruswami and Smith, replacing some probabilistic arguments with explicit constructions. We also present a simplified and general approach that makes the reductions in the proof more efficient, so that we can handle weak classes of channels. [ABSTRACT FROM AUTHOR]

We prove that if every problem in \sansN \sansP has nk-size circuits for a fixed constant k, then for every \sansN \sansP -verifier and every yes-instance x of length n for that verifier, the verifier's search space has an nO(k3)-size witness circuit: A witness for x that can be encoded with a circuit of only nO(k3) size. An analogous statement is proved for nondeterministic quasi-polynomial time, i.e., \sansN \sansQ \sansP = \sansN \sansT \sansI \sansM \sansE [nlogO(1) n]. This significantly extends the Easy Witness Lemma of Impagliazzo, Kabanets, and Wigderson [J. Comput. System Sci., 65 (2002), pp. 672--694] which only held for larger nondeterministic classes such as \sansN \sansE \sansX \sansP. As a consequence, the connections between circuit-analysis algorithms and circuit lower bounds can be considerably sharpened: Algorithms for approximately counting satisfying assignments for given circuits which improve over exhaustive search can imply circuit lower bounds for functions in \sansN \sansQ \sansP, or even \sansN \sansP . To illustrate, applying known algorithms for satisfiability of \sansA \sansC \sansC \circ \sansT \sansH \sansR circuits [R. Williams, New algorithms and lower bounds for circuits with linear threshold gates, in Proceedings of the 46th Annual ACM Symposium on Theory of Computing, ACM, New York, 2014, pp. 194--202] we conclude that for every fixed k, \sansN \sansQ \sansP does not have nlogk nsize \sansA \sansC \sansC \circ \sansT \sansH \sansR circuits. [ABSTRACT FROM AUTHOR]

Let X be randomly chosen from {-1, 1}n, and let Y be randomly chosen from the standard spherical Gaussian on ℝn. For any (possibly unbounded) polytope P formed by the intersection of k halfspaces, we prove that|Pr [X∈P]- Pr [Y∈P]|≤ log8/5 k · Δ, where Δ is a parameter that is small for polytopes formed by the intersection of "regular" halfspaces (i.e., halfspaces with low influence). The novelty of our invariance principle is the polylogarithmic dependence on k. Previously, only bounds that were at least linear in k were known. The proof of the invariance principle is based on a generalization of the Lindeberg method for proving central limit theorems and could be of use elsewhere. We give two important applications of our invariance principle, one from learning theory and the other from pseudorandomness. (1) A bound of logO(1) k · ε1/6 on the Boolean noise sensitivity of intersections of k "regular" halfspaces (previous work gave bounds linear in k). This gives a corresponding agnostic learning algorithm for intersections of regular halfspaces. (2) A pseudorandom generator (PRG) for estimating the Gaussian volume of polytopes with k faces within error δ and seed-length O(log n poly(log k, 1/δ)). We also obtain PRGs with similar parameters that fool polytopes formed by intersection of regular halfspaces over the hypercube. Using our PRG constructions, we obtain the first deterministic quasi-polynomial time algorithms for approximately counting the number of solutions to a broad class of integer programs, including dense covering problems and contingency tables. [ABSTRACT FROM AUTHOR]

We prove that poly-sized AC0 circuits cannot distinguish a polylogarithmically independent distribution from the uniform one. This settles the 1990 conjecture by Linial and Nisan [1990]. The only prior progress on the problem was by Bazzi [2007], who showed that O(log2n)-independent distributions fool poly-size DNF formulas. [Razborov 2008] has later given a much simpler proof for Bazzi's theorem. [ABSTRACT FROM AUTHOR]

This paper explores the possibilities and limitations of error correction by the structural simplicity of error mechanisms. Specifically, we consider channel models, called samplable additive channels , in which (i) errors are efficiently sampled without the knowledge of the coding scheme or the transmitted codeword; (ii) the entropy of the error distribution is bounded; and (iii) the number of errors introduced by the channel is unbounded. For the channels, several negative and positive results are provided. Assuming the existence of one-way functions, there are samplable additive errors of entropy n ε for ε ∈ (0,1) that are pseudorandom, and thus not correctable by efficient coding schemes. It is shown that there is an oracle algorithm that induces a samplable distribution over {0,1} n of entropy m = ω (log n) that is not pseudorandom, but is uncorrectable by efficient schemes of rate less than 1 − m / n − o (1) ⁠. The results indicate that restricting error mechanisms to be efficiently samplable and not pseudorandom is insufficient for error correction. As positive results, some conditions are provided under which efficient error correction is possible. [ABSTRACT FROM AUTHOR]

Green and Tao famously proved in 2005 that any subset of the primes of fixed positive density contains arbitrarily long arithmetic progressions. Green had previously shown that, in fact, any subset of the primes of relative density tending to zero sufficiently slowly contains a three-term progression. This was followed by work of Helfgott and de Roton, and Naslund, who improved the bounds on the relative density in the case of three-term progressions. The aim of this note is to present an analogous result for longer progressions by combining a quantified version of the relative Szemerédi theorem given by Conlon, Fox and Zhao with Henriot's estimates of the enveloping sieve weights. [ABSTRACT FROM AUTHOR]