Kolmogorov Width of Discrete Linear Spaces: an Approach to Matrix Rigidity

A square matrix V is called rigid if every matrix \({V^\prime}\) obtained by altering a small number of entries of V has sufficiently high rank. While random matrices are rigid with high probability, no explicit constructions of rigid matrices are known to date. Obtaining such explicit matrices would have major implications in computational complexity theory. One approach to establishing rigidity of a matrix V is to come up with a property that is satisfied by any collection of vectors arising from a low-dimensional space, but is not satisfied by the rows of V even after alterations. In this paper, we propose such a candidate property that has the potential of establishing rigidity of combinatorial design matrices over the field \({\mathbb{F}_2.}\) Stated informally, we conjecture that under a suitable embedding of \({\mathbb{F}_2^n}\) into \({\mathbb{R}^n,}\) vectors arising from a low-dimensional \({\mathbb{F}_2}\)-linear space always have somewhat small Kolmogorov width, i.e., admit a non-trivial simultaneous approximation by a low-dimensional Euclidean space. This implies rigidity of combinatorial designs, as their rows do not admit such an approximation even after alterations. Our main technical contribution is a collection of results establishing weaker forms and special cases of the conjecture above.     

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.     

Constructing online switching barriers: examining the effects of switching costs and alternative attractiveness on e-store loyalty in online pure-play retailers

Developing switching barriers to retain customers has become a critical marketing strategy for online retailers. However, research on the role of switching barriers in e-retailing is still limited. Recent trends show that when competitors are just one click away, it is questionable if customer loyalty can be achieved at all in online environments. This leads to the research question on whether switching barriers have any impact on e-loyalty in pure-play retailers. The paper examines the influence of switching barriers on customer retention (i.e., e-store loyalty) and further investigates the moderating effects of switching costs and alternative attractiveness. Data were gathered via a survey of 590 shoppers of online pure-play retailers in the UK. Findings show that customer satisfaction and the two dimensions of switching barriers (perceived switching costs and perceived attractiveness of alternatives) significantly influence customer loyalty. Contrary to findings in earlier studies, it was found that switching costs did not moderate the relationships between satisfaction and loyalty nor between perceived attractiveness of alternatives and loyalty. The paper makes imperative recommendations to develop switching barriers and to foster loyalty along with suggestions for future research.     

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.     

Managing a Very Connected World: A Report on APNOMS2015

This article presents a report on APNOMS2015, which was held August 19–21, 2015 in Busan, Korea. The theme of APNOMS2015 was “Managing a Very Connected World.”     

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.