Factors of low individual degree polynomials

Kaltofen (Randomness in computation, vol 5, pp 375–412, 1989) proved the remarkable fact that multivariate polynomial factorization can be done efficiently, in randomized polynomial time. Still, more than twenty years after Kaltofen’s work, many questions remain unanswered regarding the complexity aspects of polynomial factorization, such as the question of whether factors of polynomials efficiently computed by arithmetic formulas also have small arithmetic formulas, asked in Kopparty et al. (2014), and the question of bounding the depth of the circuits computing the factors of a polynomial. We are able to answer these questions in the affirmative for the interesting class of polynomials of bounded individual degrees, which contains polynomials such as the determinant and the permanent. We show that if \({P(x_{1},\ldots,x_{n})}\) is a polynomial with individual degrees bounded by r that can be computed by a formula of size s and depth d, then any factor \({f(x_{1},\ldots, x_{n})}\) of \({P(x_{1},\ldots,x_{n})}\) can be computed by a formula of size \({\textsf{poly}((rn)^{r},s)}\) and depth d + 5. This partially answers the question above posed in Kopparty et al. (2014), who asked if this result holds without the dependence on r. Our work generalizes the main factorization theorem from Dvir et al. (SIAM J Comput 39(4):1279–1293, 2009), who proved it for the special case when the factors are of the form \({f(x_{1}, \ldots, x_{n}) \equiv x_{n} - g(x_{1}, \ldots, x_{n-1})}\). Along the way, we introduce several new technical ideas that could be of independent interest when studying arithmetic circuits (or formulas).     

Product fit uncertainty and its effects on vendor choice: an experimental study

Recommender systems and other Internet-enabled technologies have changed the surrounding conditions of pre-purchase evaluations on the Internet. In some cases consumers can now sample entire products prior to a purchase – hereby removing all uncertainty about whether a product fits their taste. While previous research has mainly focused on vendor and product quality uncertainty, it is still not clear how declining product fit uncertainty affects consumers. To close this gap, we conducted a laboratory experiment to analyze the effects on consumers’ vendor selection. We find that full elimination of product fit uncertainty is beneficial for vendors, as it increases both the number of purchases and consumer loyalty. Interestingly, if product fit uncertainty is only partially eliminated, consumers do not necessarily show differential behavior for different levels of remaining product fit uncertainty. This has important implications for online vendors that consider the implementation of additional means to reduce product fit uncertainty.     

Consequences of customer engagement behavior: when negative Facebook posts have positive effects

Sharing product information has become an integral part of today’s online social networking world. This research study addresses the effects of customer engagement behavior in online social networks on other consumers in order to understand how online social connections impact decision making. We investigate how different variations of a brand-related Facebook post trigger different response reactions. In particular, we analyze under which conditions negative posts can have positive consequences. The results of two online experiments set in a restaurant context suggest a difference when the user knows the restaurant brand. For users who are familiar with the restaurant brand, a positive effect of negative information posted by distant acquaintances is found with regard to the visiting intention of the user. The results of both experiments demonstrate that information posted by a close friend is perceived to be more diagnostic. For users not familiar with the restaurant brand, negative posts from strong ties induce the highest diagnosticity levels.     

The complexity of intersecting finite automata having few final states

The problem of determining whether several finite automata accept a word in common is closely related to the well-studied membership problem in transformation monoids. We raise the issue of limiting the number of final states in the automata intersection problem. For automata with two final states, we show the problem to be \({\oplus}\)L-complete or NP-complete according to whether a nontrivial monoid other than a direct product of cyclic groups of order 2 is allowed in the automata. We further consider idempotent commutative automata and (Abelian, mainly) group automata with one, two, or three final states over a singleton or larger alphabet, elucidating (under the usual hypotheses on complexity classes) the complexity of the intersection nonemptiness and related problems in each case.     

Topology-Aware Multiple Routing Configurations for Fault Tolerant Networking

Real-time services require reliable and fault tolerant communication networks to support their stringent Quality of Service requirements. Multi Topology Routing based IP Fast Re-route (MT-IPFRR) technologies provide seamless forwarding of IP packets during network failures by constructing virtual topologies (VTs) to re-route the disrupted traffic. Multiple Routing Configurations (MRC) is a widely studied MT-IPFRR technique. In this paper, we propose two heuristics, namely mMRC-1 and mMRC-2, to reduce the number of VTs required by the MRC to provide full coverage for single link/node failures, and hence, to decrease its operational complexity. Both heuristics are designed to construct more robust VTs against network partitioning by taking their topological characteristics into consideration. We perform extensive experiments on 3200 topologies with diverse structural properties using our automated topology generation and analysis tool. Numerical results show that the amount of reductions in VT requirements get higher up to 31.84 %, as the networks tend to have more hub nodes whose degree is much higher than the rest of the network.     

OPTIMA: On-Line Partitioning Skew Mitigation for MapReduce with Resource Adjustment

Partitioning skew has been shown to be a major issue that can significantly prolong the execution time of MapReduce jobs. Most of the existing off-line heuristics for partitioning skew mitigation are inefficient; they have to wait for the completion of all the map tasks. Some solutions can tackle this problem on-line, but will impose an additional overhead by repartitioning the workload of overloaded tasks. In this paper, we present OPTIMA, an on-line partitioning skew mitigation technique for MapReduce. OPTIMA predicts the workload distribution of reduce tasks at run-time, leverages the deviation detection technique to identify the overloaded tasks and pro-actively adjusts resource allocation for these tasks to reduce their execution time. We provide the upper bound of OPTIMA in time complexity, while allowing OPTIMA to perform totally on-line. Through experiments using both real and synthetic workloads running on an 11-node Hadoop cluster, we have observed OPTIMA can effectively mitigate the partitioning skew and improved the job completion time by up to 36.73 % in our experiments.     

Cost-Efficient Traffic Aggregation Employing Cross-Layer Shared Protection

Shared protection/restoration is a promising solution for reducing protection resources and is supported at each layer of the current multi-layer networks. Software-defined networking is expected to reduce equipment cost as well as operational cost by orchestrating these shared protection functionalities. However, although protection resource sharing improves link utilization, it sometimes increases the required equipment. Meanwhile, traffic re-aggregation at each layer is an important technique for low volume traffic to utilize the underlying link capacity more efficiently, but re-aggregation also makes it difficult to share protection resources with traffic at lower layers. In this paper, we present multi-layer network design strategy and method that reduce equipment cost by means of both traffic re-aggregation at each layer and protection resource sharing among multiple service traffic at different layers. The strategy first prioritizes traffic re-aggregation at each layer, and then maximally delegates shared protection to lower layers as long as it does not increase the required capacity at the lower layer. Evaluation results from the example three-layer networks confirm that the proposed method can effectively reduce equipment cost compared to the conventional design method. Cost reduction is achieved by leveraging shared protection functions at multiple layers.     

Reliable Communication Networks for Smart Grid Transmission Systems

In this paper, we discuss the communications reliability requirements posed by the smart power grid with a focus on communications in support of wide area situational awareness. Implementation of wide area situational awareness relies on both transmission substation networks and wide area optical networks. We study the reliability of a sample communications network of the California Power Grid and find that its reliability falls short of proposed requirements. To overcome this issue, we consider the problem of designing the substation network and the wide area network to meet the reliability requirements while minimizing the network cost. For the wide area network design problem, we propose two alternate design approaches, namely: (1) following the power lines and (2) a mesh based design interconnecting the nodes. For the first approach we develop two greedy iterative heuristics and a heuristic integer linear programming (H-ILP) model using minimum cut-sets for network reliability optimization. The greedy iterative algorithms outperform the H-ILP approach in terms of cost, but require a larger amount of computing resources. Both proposed models are in fact complementary and thus provide a framework to optimize the reliability of smart grid communications networks restricted to following the power lines. In the second approach a greenfield mesh network method is proposed based on starting with a minimum spanning tree which is then augmented through a greedy heuristic into a mesh. Comparative numerical results show that the reliable mesh design has advantages in terms of the number of links and total link distance needed.     

External sorting on flash storage: reducing cell wearing and increasing efficiency by avoiding intermediate writes

This paper studies the problem of how to conduct external sorting on flash drives while avoiding intermediate writes to the disk. The focus is on sort in portable electronic devices, where relations are only larger than the main memory by a small factor, and on sort as part of distributed processes where relations are frequently partially sorted. In such cases, sort algorithms that refrain from writing intermediate results to the disk have three advantages over algorithms that perform intermediate writes. First, on devices in which read operations are much faster than writes, such methods are efficient and frequently outperform Merge Sort. Secondly, they reduce flash cell degradation caused by writes. Thirdly, they can be used in cases where there is not enough disk space for the intermediate results. Novel sort algorithms that avoid intermediate writes to the disk are presented. An experimental evaluation, on different flash storage devices, shows that in many cases the new algorithms can extend the lifespan of the devices by avoiding unnecessary writes to the disk, while maintaining efficiency, in comparison with Merge Sort.