Relative to the large literature on upper bounds on complexity of convex optimization, lesser attention has been paid to the fundamental hardn4516420ess of these problems. Given the extensive use of ...convex optimization in machine learning and statistics, gaining an understanding of these complexity-theoretic issues is important. In this paper, we study the complexity of stochastic convex optimization in an oracle model of computation. We introduce a new notion of discrepancy between functions, and use it to reduce problems of stochastic convex optimization to statistical parameter estimation, which can be lower bounded using information-theoretic methods. Using this approach, we improve upon known results and obtain tight minimax complexity estimates for various function classes.
Retirement has been associated with cognitive decline. However, the influence of specific job characteristics like occupational complexity on post-retirement cognitive outcomes is not well ...understood. Data from the Midlife in the United States (MIDUS) study were used to examine occupational complexity in relation to cognitive performance and cognitive change after retirement. Initial sample included 471 workers between 45 and 75 years of age. At 9-year follow-up (T2), 149 were retired and 322 were still working. All six tasks from the Brief Test of Adult Cognition by Telephone (BTACT) were used. Hierarchical regression with workers at T1 indicated that, controlling for sociodemographic variables, complexity of work with people significantly contributed to explaining variance in overall cognitive performance (1.7%) and executive function (2%). In Latent Change Score (LCS) models, complexity of work with people was the only significant predictor of cognitive change in retirees, with those retiring from high-complexity jobs showing less decline. In conclusion, high complexity of work with people is related to better executive functioning and overall cognition during working life and slower decline after retirement. The finding that more intellectually stimulating work carries cognitive advantage into retirement fits the cognitive reserve concept, where earlier intellectual stimulation brings about lower risks of cognitive problems later. Study results also go along with the unengaged lifestyle hypothesis, whereby people may slip into so-called "mental retirement," leading to post-retirement cognitive loss, which may be most apparent among those retiring from jobs with low complexity of work with people.
For uplink large-scale multiple-input-multiple-output (MIMO) systems, the minimum mean square error (MMSE) algorithm is near optimal but involves matrix inversion with high complexity. In this paper, ...we propose to exploit the Gauss-Seidel (GS) method to iteratively realize the MMSE algorithm without the complicated matrix inversion. To further accelerate the convergence rate and reduce the complexity, we propose a diagonal-approximate initial solution to the GS method, which is much closer to the final solution than the traditional zero-vector initial solution. We also propose an approximated method to compute log-likelihood ratios for soft channel decoding with a negligible performance loss. The analysis shows that the proposed GS-based algorithm can reduce the computational complexity from O(K 3 ) to O(K 2 ), where K is the number of users. Simulation results verify that the proposed algorithm outperforms the recently proposed Neumann series approximation algorithm and achieves the near-optimal performance of the classical MMSE algorithm with a small number of iterations.
Systems change requires complex interventions. Cross-sector partnerships (CSPs) face the daunting task of addressing complex societal problems by aligning different backgrounds, values, ideas and ...resources. A major challenge for CSPs is how to link the type of partnership to the intervention needed to drive change. Intervention strategies are thereby increasingly based on Theories of Change (ToCs). Applying ToCs is often a donor requirement, but it also reflects the ambition of a partnership to enhance its transformative potential. The current use of ToCs in partnering efforts varies greatly. There is a tendency for a linear and relatively simple use of ToCs that does limited justice to the complexity of the problems partnerships aim to address. Since partnership dynamics are already complex and challenging themselves, confusion and disagreement over the appropriate application of ToCs is likely to hamper rather than enhance the transformative potential of partnerships. We develop a complexity alignment framework and a diagnostic tool that enables partnerships to better appreciate the complexity of the context in which they operate, allowing them to adjust their learning strategy. This paper applies recent insights into how to deal with complexity from both the evaluation and theory of change fields to studies investigating the transformative capacity of partnerships. This can (1) serve as a check to define the challenges of partnering projects and (2) can help delineate the societal sources and layers of complexity that cross-sector partnerships deal with such as failure, insufficient responsibility taking and collective action problems at four phases of partnering.
A new type of Oblivious Transfer protocol is designed under the assumption of ECDDH. The protocol can be safely implemented under a malicious model, 1 of which are selected in N input values. The ...RAND function is defined under this assumption, and the security definition is given. Then, the security interaction mode of the sender and receiver is constructed. Finally, the correctness of the Protocol is analyzed and the security proof is given. The protocol has the interaction complexity of the constant number level, and the computational and communication complexity is only related to n linearity.
Robust sunflowers are a generalization of combinatorial sunflowers that have applications in monotone circuit complexity Rossman (SIAM J. Comput. 43:256–279, 2014), DNF sparsification Gopalan et al. ...(Comput. Complex. 22:275–310 2013), randomness extractors Li et al. (In: APPROX-RANDOM, LIPIcs 116:51:1–13, 2018), and recent advances on the Erdős-Rado sunflower conjecture Alweiss et al. (In: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC. Association for Computing Machinery, New York, NY, USA, 2020) Lovett et al. (From dnf compression to sunflower theorems via regularity, 2019) Rao (Discrete Anal. 8,2020). The recent breakthrough of Alweiss, Lovett, Wu and Zhang Alweiss et al. (In: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC. Association for Computing Machinery, New York, NY, USA, 2020) gives an improved bound on the maximum size of a
w
-set system that excludes a robust sunflower. In this paper, we use this result to obtain an
exp
(
n
1
/
2
-
o
(
1
)
)
lower bound on the monotone circuit size of an explicit
n
-variate monotone function, improving the previous best known
exp
(
n
1
/
3
-
o
(
1
)
)
due to Andreev (Algebra and Logic, 26:1–18, 1987) and Harnik and Raz (In: Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, ACM, New York, 2000). We also show an
exp
(
Ω
(
n
)
)
lower bound on the monotone
arithmetic
circuit size of a related polynomial via a very simple proof. Finally, we introduce a notion of robust clique-sunflowers and use this to prove an
n
Ω
(
k
)
lower bound on the monotone circuit size of the CLIQUE function for all
k
⩽
n
1
/
3
-
o
(
1
)
, strengthening the bound of Alon and Boppana (Combinatorica, 7:1–22, 1987).
Display omitted
• The paper distinguishes between three types of supply chain complexity: static, dynamic and decision making. • It classifies supply chain complexity drivers as: internal, ...supply/demand interface, and external/environmental. • It is possible to make use of systemic property of supply chains to shift complexity from one driver to another. • There is a need to reduce/prevent the unnecessary complexity, and manage the necessary complexity.
Studies on supply chain complexity mainly use the static and dynamic complexity distinction. While static complexity describes the structure of the supply chain, the number and the variety of its components and strengths of interactions between these; the dynamic complexity represents the uncertainty in the supply chain and involves the aspects of time and randomness. This distinction is also valid when classifying the drivers of supply chain complexity according to the way they are generated. Supply chain complexity drivers (e.g., number/variety of suppliers, number/variety of customers, number/variety of interactions, conflicting policies, demand amplification, differing/conflicting/non-synchronized decisions and actions, incompatible IT systems) play a significant and varying role in dealing with complexity of the different types of supply chains (e.g., food, chemical, electronics, automotive).
This paper reviews the typical complexity drivers that are faced in different types of supply chains and presents the complexity driver and solution strategy pairings, in the form of a matrix. Drivers and strategies are extracted from real-life supply chain situations gathered from multiple existing sources; such as reports, archives, observations, interviews. The synthesis of good practices would assist decision-makers in formulating appropriate strategies to deal with complexity in their supply chains.
Ontology-Mediated Queries Bienvenu, Meghyn; Kikot, Stanislav; Kontchakov, Roman ...
Journal of the ACM,
09/2018, Volume:
65, Issue:
5
Journal Article
Peer reviewed
Open access
We give solutions to two fundamental computational problems in ontology-based data access with the W3C standard ontology language OWL 2 QL: the succinctness problem for first-order rewritings of ...ontology-mediated queries (OMQs) and the complexity problem for OMQ answering. We classify OMQs according to the shape of their conjunctive queries (treewidth, the number of leaves) and the existential depth of their ontologies. For each of these classes, we determine the combined complexity of OMQ answering and whether all OMQs in the class have polynomial-size first-order, positive existential, and nonrecursive datalog rewritings. We obtain the succinctness results using hypergraph programs, a new computational model for Boolean functions, which makes it possible to connect the size of OMQ rewritings and circuit complexity.
Since the introduction of the Kolmogorov complexity of binary sequences in the 1960s, there have been significant advancements on the topic of complexity measures for randomness assessment, which are ...of fundamental importance in theoretical computer science and of practical interest in cryptography. This survey reviews notable research from the past four decades on the linear, quadratic and maximum-order complexities of pseudo-random sequences, and their relations with Lempel–Ziv complexity, expansion complexity, 2-adic complexity and correlation measures.
PDF
