1,720,994 research outputs found
Two Structural Results for Low Degree Polynomials and Applications
Get PDFIn this paper, two structural results concerning low degree polynomials over finite fields are given. The first states that over any finite field F, for any polynomial f on n variables with degree d > log(n)/10, there exists a subspace of F^n with dimension at least d n^(1/(d-1)) on which f is constant. This result is shown to be tight. Stated differently, a degree d polynomial cannot compute an affine disperser for dimension smaller than the stated dimension. Using a recursive argument, we obtain our second structural result, showing that any degree d polynomial f induces a partition of F^n to affine subspaces of dimension n^(1/(d-1)!), such that f is constant on each part.
We extend both structural results to more than one polynomial. We further prove an analog of the first structural result to sparse polynomials (with no restriction on the degree) and to functions that are close to low degree polynomials. We also consider the algorithmic aspect of the two structural results.
Our structural results have various applications, two of which are:
* Dvir [CC 2012] introduced the notion of extractors for varieties, and gave explicit constructions of such extractors over large fields. We show that over any finite field any affine extractor is also an extractor for varieties with related parameters. Our reduction also holds for dispersers, and we conclude that Shaltiel's affine disperser [FOCS 2011] is a disperser for varieties over the binary field.
* Ben-Sasson and Kopparty [SIAM J. C 2012] proved that any degree 3 affine disperser over a prime field is also an affine extractor with related parameters. Using our structural results, and based on the work of Kaufman and Lovett [FOCS 2008] and Haramaty and Shpilka [STOC 2010], we generalize this result to any constant degree
Quantum Versus Randomized Communication Complexity, with Efficient Players
Get PDFWe study a new type of separations between quantum and classical communication complexity, separations that are obtained using quantum protocols where all parties are efficient, in the sense that they can be implemented by small quantum circuits, with oracle access to their inputs. Our main result qualitatively matches the strongest known separation between quantum and classical communication complexity [Dmitry Gavinsky, 2016] and is obtained using a quantum protocol where all parties are efficient. More precisely, we give an explicit partial Boolean function f over inputs of length N, such that:
(1) f can be computed by a simultaneous-message quantum protocol with communication complexity polylog(N) (where at the beginning of the protocol Alice and Bob also have polylog(N) entangled EPR pairs).
(2) Any classical randomized protocol for f, with any number of rounds, has communication complexity at least Ω̃(N^{1/4}).
(3) All parties in the quantum protocol of Item (1) (Alice, Bob and the referee) can be implemented by quantum circuits of size polylog(N) (where Alice and Bob have oracle access to their inputs).
Items (1), (2) qualitatively match the strongest known separation between quantum and classical communication complexity, proved by Gavinsky [Dmitry Gavinsky, 2016]. Item (3) is new. (Our result is incomparable to the one of Gavinsky. While he obtained a quantitatively better lower bound of Ω(N^{1/2}) in the classical case, the referee in his quantum protocol is inefficient).
Exponential separations of quantum and classical communication complexity have been studied in numerous previous works, but to the best of our knowledge the efficiency of the parties in the quantum protocol has not been addressed, and in most previous separations the quantum parties seem to be inefficient. The only separations that we know of that have efficient quantum parties are the recent separations that are based on lifting [Arkadev Chattopadhyay et al., 2019; Arkadev Chattopadhyay et al., 2019]. However, these separations seem to require quantum protocols with at least two rounds of communication, so they imply a separation of two-way quantum and classical communication complexity but they do not give the stronger separations of simultaneous-message quantum communication complexity vs. two-way classical communication complexity (or even one-way quantum communication complexity vs. two-way classical communication complexity).
Our proof technique is completely new, in the context of communication complexity, and is based on techniques from [Ran Raz and Avishay Tal, 2019]. Our function f is based on a lift of the forrelation problem, using xor as a gadget
On the Sensitivity Conjecture
Get PDFThe sensitivity of a Boolean function f:{0,1}^n -> {0,1} is the maximal number of neighbors a point in the Boolean hypercube has with different f-value. Roughly speaking, the block sensitivity allows to flip a set of bits (called a block) rather than just one bit, in order to change the value of f. The sensitivity conjecture, posed by Nisan and Szegedy (CC, 1994), states that the block sensitivity, bs(f), is at most polynomial in the sensitivity, s(f), for any Boolean function f. A positive answer to the conjecture will have many consequences, as the block sensitivity is polynomially related to many other complexity measures such as the certificate complexity, the decision tree complexity and the degree. The conjecture is far from being understood, as there is an exponential gap between the known upper and lower bounds relating bs(f) and s(f).
We continue a line of work started by Kenyon and Kutin (Inf. Comput., 2004), studying the l-block sensitivity, bs_l(f), where l bounds the size of sensitive blocks. While for bs_2(f) the picture is well understood with almost matching upper and lower bounds, for bs_3(f) it is not. We show that any development in understanding bs_3(f) in terms of s(f) will have great implications on the original question. Namely, we show that either bs(f) is at most sub-exponential in s(f) (which improves the state of the art upper bounds) or that bs_3(f) >= s(f){3-epsilon} for some Boolean functions (which improves the state of the art separations).
We generalize the question of bs(f) versus s(f) to bounded functions f:{0,1}^n -> [0,1] and show an analog result to that of Kenyon and Kutin: bs_l(f) = O(s(f))^l. Surprisingly, in this case, the bounds are close to being tight. In particular, we construct a bounded function f:{0,1}^n -> [0, 1] with bs(f) n/log(n) and s(f) = O(log(n)), a clear counterexample to the sensitivity conjecture for bounded functions.
Finally, we give a new super-quadratic separation between sensitivity and decision tree complexity by constructing Boolean functions with DT(f) >= s(f)^{2.115}. Prior to this work, only quadratic separations, DT(f) = s(f)^2, were known
Tight Bounds on the Fourier Spectrum of AC0
No full textWe show that AC^0 circuits on n variables with depth d and size m have at most 2^{-Omega(k/log^{d-1} m)} of their Fourier mass at level k or above. Our proof builds on a previous result by Hastad (SICOMP, 2014) who proved this bound for the special case k=n. Our result improves the seminal result of Linial, Mansour and Nisan (JACM, 1993) and is tight up to the constants hidden in the Omega notation.
As an application, we improve Braverman's celebrated result (JACM, 2010). Braverman showed that any r(m,d,epsilon)-wise independent distribution epsilon-fools AC^0 circuits of size m and depth d, for r(m,d,epsilon) = O(log(m/epsilon))^{2d^2+7d+3}. Our improved bounds on the Fourier tails of AC^0 circuits allows us to improve this estimate to r(m,d,epsilon) = O(log(m/epsilon))^{3d+3}. In contrast, an example by Mansour (appearing in Luby and Velickovic's paper - Algorithmica, 1996) shows that there is a log^{d-1}(m)\log(1/epsilon)-wise independent distribution that does not epsilon-fool AC^0 circuits of size m and depth d. Hence, our result is tight up to the factor in the exponent
Pseudorandom Generators for Low Sensitivity Functions
Get PDFA Boolean function is said to have maximal sensitivity s if s is the largest number of Hamming neighbors of a point which differ from it in function value. We initiate the study of pseudorandom generators fooling low-sensitivity functions as an intermediate step towards settling the sensitivity conjecture. We construct a pseudorandom generator with seed-length 2^{O(s^{1/2})} log(n) that fools Boolean functions on n variables with maximal sensitivity at most s. Prior to our work, the (implicitly) best pseudorandom generators for this class of functions required seed-length 2^{O(s)} log(n)
Going Beyond Counting First Authors in Author Co-citation Analysis
Get PDFThe present study examines one of the fundamental aspects of author co-citation analysis (ACA) - the way co-citation
counts are defined. Co-citation counting provides the data on which all subsequent statistical analyses and mappings
are based, and we compare ACA results based on two different types of co-citation counting - the traditional type that
only counts the first one among a cited work's authors on the one hand and a non-traditional type that takes into
account the first 5 authors of a cited work on the other hand. Results indicate that the picture produced through this non-traditional author co-citation counting contains more coherent author groups and is therefore considerably clearer. However, this picture represents fewer specialties in the research field being studied than that produced through the traditional first-author co-citation counting when the same number of top-ranked authors is selected and analyzed. Reasons for these effects are discussed
Variations on the Author
Get PDF“Variations on the Author” discusses two of Eduardo Coutinho’s recent films (Um Dia na Vida, from 2010, and Últimas Conversas, posthumously released in 2015) and their contribution to the general question of documentary authorship. The director’s filmography is characterized by a consistent yet self-effacing form of authorial self-inscription: Coutinho often features as an interviewer that rather than express opinions propels discourses; an interviewer that is good at listening. This mode of self-inscription characterizes him as an author who is not expressive but who is nonetheless markedly present on the screen. In Um Dia na Vida, however, Coutinho is completely absent form the image, while Últimas Conversas, on the contrary, includes a confessional prologue that moves the director from the margins to the center of his films. This article examines the ways in which these works stand out in the filmography of a director who offers new insights into the notion of cinematic authorship
Appropriate Similarity Measures for Author Cocitation Analysis
Get PDFWe provide a number of new insights into the methodological discussion about author cocitation analysis. We first argue that the use of the Pearson correlation for measuring the similarity between authors’ cocitation profiles is not very satisfactory. We then discuss what kind of similarity measures may be used as an alternative to the Pearson correlation. We consider three similarity measures in particular. One is the well-known cosine. The other two similarity measures have not been used before in the bibliometric literature. Finally, we show by means of an example that our findings have a high practical relevance.information science;Pearson correlation;cosine;similarity measure;author cocitation analysis
- …
