Abstract It is a classical result that the inner product function cannot be computed by an $${\rm AC}^0$$ AC 0 circuit. It is conjectured that this holds even if we allow arbitrary preprocessing of each of the two inputs separately. We prove this conjecture when the preprocessing of one of the inputs is limited to output $$n + n/(\log^{\omega(1)}n)$$ n + n / ( log ω ( 1 ) n ) bits and obtain a tight correlation bound. Our methods extend to many other functions, including pseudorandom functions, and imply a---weak yet nontrivial---limitation on the power of encoding inputs in low-complexity cryptography. Finally, under cryptographic assumptions, we relate the question of proving variants of the above conjecture with the question of learning $${\rm AC}^0$$ AC 0 under simple input distributions.

We consider the following question of bounded simultaneous messages (BSM) protocols: Can computationally unbounded Alice and Bob evaluate a function f(x,y) of their inputs by sending polynomial-size messages to a computationally bounded Carol? The special case where f is the mod-2 inner-product function and Carol is bounded to AC⁰ has been studied in previous works. The general question can be broadly motivated by applications in which distributed computation is more costly than local computation. In this work, we initiate a more systematic study of the BSM model, with different functions f and computational bounds on Carol. In particular, we give evidence against the existence of BSM protocols with polynomial-size Carol for naturally distributed variants of NP-complete languages.

A pair of sources X, Y over {0,1}ⁿ are k-indistinguishable if their projections to any k coordinates are identically distributed. Can some AC^0 function distinguish between two such sources when k is big, say k = n^{0.1}? Braverman’s theorem (Commun. ACM 2011) implies a negative answer when X is uniform, whereas Bogdanov et al. (Crypto 2016) observe that this is not the case in general. We initiate a systematic study of this question for natural classes of low-complexity sources, including ones that arise in cryptographic applications, obtaining positive results, negative results, and barriers. In particular: - There exist Ω(√n)-indistinguishable X, Y, samplable by degree-O(log n) polynomial maps (over F₂) and by poly(n)-size decision trees, that are Ω(1)-distinguishable by OR. - There exists a function f such that all f(d, ε)-indistinguishable X, Y that are samplable by degree-d polynomial maps are ε-indistinguishable by OR for all sufficiently large n. Moreover, f(1, ε) = ⌈log(1/ε)⌉ + 1 and f(2, ε) = O(log^{10}(1/ε)). - Extending (weaker versions of) the above negative results to AC^0 distinguishers would require settling a conjecture of Servedio and Viola (ECCC 2012). Concretely, if every pair of n^{0.9}-indistinguishable X, Y that are samplable by linear maps is ε-indistinguishable by AC^0 circuits, then the binary inner product function can have at most an ε-correlation with AC^0 ◦ ⊕ circuits. Finally, we motivate the question and our results by presenting applications of positive results to low-complexity secret sharing and applications of negative results to leakage-resilient cryptography.

It is a classical result that the inner product function cannot be computed by an AC⁰ circuit [Merrick L. Furst et al., 1981; Miklós Ajtai, 1983; Johan Håstad, 1986]. It is conjectured that this holds even if we allow arbitrary preprocessing of each of the two inputs separately. We prove this conjecture when the preprocessing of one of the inputs is limited to output n + n/(log^{ω(1)} n) bits. Our methods extend to many other functions, including pseudorandom functions, and imply a (weak but nontrivial) limitation on the power of encoding inputs in low-complexity cryptography. Finally, under cryptographic assumptions, we relate the question of proving variants of the main conjecture with the question of learning AC⁰ under simple input distributions.

Social media sites have become very popular within large enterprises. Still, employees are experiencing difficulties in engaging efficiently. In this paper, we present a study of a personalized action recommendation system in an enterprise social network. Following a previous study on how to raise one's social eminence in the enterprise and a set of interviews, we built an innovative recommendation system which provides employees with concrete personalized recommendations on how and where to engage. Differently from other systems, it presents recommendations in context of limiting social network behavioral patterns. The recommendations goal is to assist employees in growing out of these patterns. The paper presents the interview findings, the innovative recommendation system and results of a wide survey investigating the effectiveness of such a system.

Social media platforms have become popular in many enterprises. Employees build their social eminence by effectively engaging on these platforms. Becoming socially eminent in the organization is a personal journey and many employees need guidance to succeed. In this paper, we describe a tool called Personal Social Dashboard deployed within our enterprise. The tool provides feedback to employees on how effectively they engage in the enterprise social network by maintaining a set of scores covering different aspects of one's social role, such as Activity, Network, Reaction, and Eminence. We provide a description of the tool with a subsequent study of its use within the company and effect on employees' behavior in the company's social network.

Companies are motivating their employees to become socially engaged in enterprise social networks as a means to raise employee engagement. This is also beneficial for employees as it provides an opportunity for them to get a voice and raise their eminence. Unfortunately, not all employees are born "social butterflies" and many have difficulties in becoming more socially active. Failing to engage in an effective manner creates frustration which over time decreases their activity and lowers their chance to become socially eminent. This paper is a first of a kind study that reveals insights on social behavioral patterns of socially eminent employees. We extracted a comprehensive set of tips and recommendations to help employees become more socially eminent and investigate if and how eminent employees engage differently than others. We conducted interviews with top socially eminent employees and a quantitative inspection of bloggers behavioral patterns. Furthermore, we show that indeed best practices stated by socially eminent employees are fulfilled by eminent bloggers and less by others. We also found differences in how socially eminent employees engage compared to less eminent employees.

Floating point operations such as divide and square root are typically implemented in microcode rather than dedicated logic. Bugs in these operations missed by generic black-box verification tools, were analyzed. This led to the conclusion that the corner cases, in addition to being implementation dependent, could not be characterized in terms of special input or output values in a straightforward manner. However, many of those cases can be easily generalized for many known implementations. The typical implementation uses a known iterative approximation algorithm, such as the Newton-Raphson method, to calculate the desired result; thus, it is sufficient to produce the corner cases associated with the specific algorithm. We investigated the following problem: given an iterative algorithm to compute a binary floating point operation, the iteration number, and an interval, find random inputs for the operation that, after the requested iteration, yield a relative error within the specified interval. This paper describes a method to solve this problem. This method was implemented in a floating-point test generator and is currently being used to verify the floating-point units of several processors.