Search

Divide and Conquer is a well-known technique for designing algorithms. Many of the existing algorithms are a product of this popular algorithm design technique. Such include Quick sort and Merge sort sorting algorithms. These two algorithms have been widely employed for sorting, however, determining the most efficient among the two has always been a contentious issue. Most of the existing literature have compared these algorithms using machine dependent factors such as computational complexity but few have employed machine independent factors such as internal/external sorting, algorithm complexity: best, average, and worst cases, memory usage, stability etc. This study intends to contribute to this discuss using both machine dependent and independent factors. The implementation was carried out in MATLAB programming environment and the internal system clock was set to keep track of the time required for sorting. Results obtained revealed that in terms of computational speed using array of small sizes, Quick sort algorithm is faster, though Merge sort algorithm is faster with array of large sizes. Also, both algorithms are of O(nlogn) best case and average case complexity while the worst case for quicksort is O(n2) and that of merge sort remains unchanged. In terms of stability, Quick sort is stable while Merge sort is not. Despite the excellent performance of Merge sort algorithm, the need for an auxiliary memory for sorting makes it less preferable than Quick sort algorithm for applications where a good cache locality is of paramount importance.

A long-standing and central open question in the theory of average-case complexity is to base average-case hardness of NP on worst-case hardness of NP. A frontier question along this line is to prove that PH is hard on average if UP requires (sub-)exponential worst-case complexity. The difficulty of resolving this question has been discussed from various perspectives based on technical barrier results, such as the limits of black-box reductions and the non-existence of worst-case hardness amplification procedures in PH. In this paper, we overcome these barriers and resolve the open question by presenting the following main results: 1. UP ⊈DTIME(2O(n / logn)) implies DistNP ⊈AvgP. 2. PH ⊈DTIME(2O(n / logn)) implies DistPH ⊈AvgP. 3. NP ⊈DTIME(2O(n / logn)) implies DistNP ⊈AvgP P. Here, AvgP P denotes P-computable average-case polynomial time, which interpolates average-case polynomial-time and worst-case polynomial-time. We complement this result by showing that DistPH ⊈AvgP if and only if DistPH ⊈AvgP P. At the core of all of our results is a new notion of universal heuristic scheme, whose running time is P-computable average-case polynomial time under every polynomial-time samplable distribution. Our proofs are based on the meta-complexity of time-bounded Kolmogorov complexity: We analyze average-case complexity through the lens of worst-case meta-complexity using a new “algorithmic” proof of language compression and weak symmetry of information for time-bounded Kolmogorov complexity.

In this work, we study a variant of nonnegative matrix factorization where we wish to find a symmetric factorization of a given input matrix into a sparse, Boolean matrix. Formally speaking, given $\mathbf{M}\in\mathbb{Z}^{m\times m}$, we want to find $\mathbf{W}\in\{0,1\}^{m\times r}$ such that $\| \mathbf{M} - \mathbf{W}\mathbf{W}^\top \|_0$ is minimized among all $\mathbf{W}$ for which each row is $k$-sparse. This question turns out to be closely related to a number of questions like recovering a hypergraph from its line graph, as well as reconstruction attacks for private neural network training. As this problem is hard in the worst-case, we study a natural average-case variant that arises in the context of these reconstruction attacks: $\mathbf{M} = \mathbf{W}\mathbf{W}^{\top}$ for $\mathbf{W}$ a random Boolean matrix with $k$-sparse rows, and the goal is to recover $\mathbf{W}$ up to column permutation. Equivalently, this can be thought of as recovering a uniformly random $k$-uniform hypergraph from its line graph. Our main result is a polynomial-time algorithm for this problem based on bootstrapping higher-order information about $\mathbf{W}$ and then decomposing an appropriate tensor. The key ingredient in our analysis, which may be of independent interest, is to show that such a matrix $\mathbf{W}$ has full column rank with high probability as soon as $m = \widetilde{\Omega}(r)$, which we do using tools from Littlewood-Offord theory and estimates for binary Krawtchouk polynomials., Comment: 33 pages, to appear in Innovations in Theoretical Computer Science (ITCS 2022), v2: updated refs

We consider the question of whether PPAD hardness can be based on standard cryptographic assumptions, such as the existence of one-way functions or public-key encryption. This question is particularly well-motivated in light of new devastating attacks on obfuscation candidates and their underlying building blocks, which are currently the only known source for PPAD hardness.

We exactly characterize the average-case complexity of the polynomial-time hierarchy (PH) by the worst-case (meta-)complexity of GapMINKTPH, i.e., an approximation version of the problem of determining if a given string can be compressed to a short PH-oracle efficient program. Specifically, we establish the following equivalence: \begin{align*} &\text{DistPH}\subseteq \text{AvgP}\ \ (\mathrm{i}.\mathrm{e}.,\ \text{PH}\ \mathrm{is\ easy\ on\ average})\\ \Longleftrightarrow &\text{GapMINKT}^{\text{PH}}\in \mathrm{P}. \end{align*} In fact, our equivalence is significantly broad: A number of statements on several fundamental notions of complexity theory, such as errorless and one-sided-error average-case complexity, sublinear-time-bounded and polynomial-time-bounded Kolmogorov complexity, and PH-computable hitting set generators, are all shown to be equivalent. Our equivalence provides fundamentally new proof techniques for analyzing average-case complexity through the lens of meta-complexity of time-bounded Kolmogorov complexity and resolves, as immediate corollaries, questions of equivalence among different notions of average-case complexity of PH: low success versus high success probabilities (i.e., a hardness amplification theorem for DistPH against uniform algorithms) and errorless versus one-sided-error average-case complexity of PH. Our results are based on a sequence of new technical results that further develops the proof techniques of the author's previous work on the non-black-box worst-case to average-case reduction and unexpected hardness results for Kolmogorov complexity (FOCS'18, CCC'20, ITCS'20, STOC'20). Among other things, we prove the following. 1) $\text{GapMINKT}^{\text{NP}}\in \mathrm{P}$ implies $\mathrm{P}=\text{BPP}$ . At the core of the proof is a new black-box hitting set generator construction whose reconstruction algorithm uses few random bits, which also improves the approximation quality of the non-black-box worst-case to average-case reduction without using a pseudorandom generator. 2) $\text{GapMINKT}^{\text{PH}}\in \mathrm{P}$ implies $\text{DistPH}\subseteq \text{AvgBPP}=\text{AvgP}$ . 3)If MINKTPH is easy on a $1/\text{poly}(n)$ -fraction of inputs, then $\text{GapMINKT}^{\text{PH}}\in \mathrm{P}$ . This improves the error tolerance of the previous non-black-box worst-case to average-case reduction. The full version of this paper is available on ECCC.

We prove that for all constants a, NQP = NTIME[n polylog(n)] cannot be (1/2 + 2−log a n )-approximated by 2log a n -size ACC 0 ∘ THR circuits ( ACC 0 circuits with a bottom layer of THR gates). Previously, it was even open whether E NP can be (1/2+1/√n)-approximated by AC 0[⊕] circuits. As a straightforward application, we obtain an infinitely often ( NE ∩ coNE)/1-computable pseudorandom generator for poly-size ACC 0 circuits with seed length 2logє n , for all є > 0. More generally, we establish a connection showing that, for a typical circuit class C, non-trivial nondeterministic algorithms estimating the acceptance probability of a given S-size C circuit with an additive error 1/S (we call it a CAPP algorithm) imply strong (1/2 + 1/n ω(1)) average-case lower bounds for nondeterministic time classes against C circuits. Note that the existence of such (deterministic) algorithms is much weaker than the widely believed conjecture PromiseBPP = PromiseP. We also apply our results to several sub-classes of TC 0 circuits. First, we show that for all k, NP cannot be (1/2 + n −k )-approximated by n k -size Sum∘ THR circuits (exact ℝ-linear combination of threshold gates), improving the corresponding worst-case result in [Williams, CCC 2018]. Second, we establish strong average-case lower bounds and build ( NE ∩ coNE)/1-computable PRGs for Sum ∘ PTF circuits, for various regimes of degrees. Third, we show that non-trivial CAPP algorithms for MAJ ∘ MAJ indeed already imply worst-case lower bounds for TC 3 0 ( MAJ ∘ MAJ ∘ MAJ). Since exponential lower bounds for MAJ ∘ MAJ are already known, this suggests TC 3 0 lower bounds are probably within reach. Our new results build on a line of recent works, including [Murray and Williams, STOC 2018], [Chen and Williams, CCC 2019], and [Chen, FOCS 2019]. In particular, it strengthens the corresponding (1/2 + 1/polylog(n))-inapproximability average-case lower bounds in [Chen, FOCS 2019]. The two important technical ingredients are techniques from Cryptography in NC 0 [Applebaum et al., SICOMP 2006], and Probabilistic Checkable Proofs of Proximity with NC 1-computable proofs.

We prove that the PNP-type query complexity (alternatively, decision list width) of any Boolean function f is quadratically related to the PNP-type communication complexity of a lifted version of f. As an application, we show that a certain “product” lower bound method of Impagliazzo and Williams (CCC 2010) fails to capture PNP communication complexity up to polynomial factors, which answers a question of Papakonstantinou, Scheder, and Song (CCC 2014).

The average-case complexity of computation of underdetermined functions by straight-line programs with conditional stop over the basis of all at most two-place Boolean functions is considered. Correct order estimates of the average-case complexity of functions with maximum average-case complexity among all underdetermined functions are derived depending on the degree of their determinacy, the size of their domain, and the size of their support.

It is known that the problem of deciding k -colorability of a graph exhibits an easy-hard-easy pattern,—that is, the average-case complexity for backtrack-type algorithms, as a function of k , has a peak. This complexity peak is either at k = χ − 1 or k = χ, where χ is the chromatic number of the graph. However, the behavior around the complexity peak is poorly understood. In this article, we use list coloring to model coloring with a fractional number of colors between χ − 1 and χ. We present a comprehensive computational study on the complexity of backtrack-type graph coloring algorithms in this critical range. According to our findings, an easy-hard-easy pattern can be observed on a finer scale between χ − 1 and χ as well. The highest complexity found this way can be higher than for any integer value of k . It turns out that the complexity follows an alternating three-dimensional pattern; understanding this pattern is very important for benchmarking purposes. Our results also answer the previously open question whether coloring with χ − 1 or with χ colors is harder: this depends on the location of the maximal fractional complexity.

Network virtualization (NV) is widely accepted as one enabling technology for future network, which enables multiple virtual networks (VNs) with different paradigms and protocols to coexist on the shared substrate network (SN). One key challenge in NV is VN embedding (VNE), which maps a VN onto the shared SN. Since VNE is NP-hard, existing efforts mainly focus on proposing heuristic algorithms that try to achieve feasible VNE in reasonable time, consequently the resulted embedding is not optimal. To tackle this difficulty, we propose a candidate assisted (CAN-A) optimal VNE algorithm with lower computational complexity. The key idea of the CAN-A algorithm lies in constructing the candidate substrate node subset and the candidate substrate path subset before embedding. This reduces the mapping execution time substantially without performance loss. In the following embedding, four types of node and link constraints are considered in the CAN-A algorithm, making it more applicable to realistic networks. Simulation results show that the execution time of CAN-A is hugely cut down compared with pure VNE-MIP algorithm. CAN-A also outperforms the typical heuristic algorithms in terms of other performance indices, such as the average VN request acceptance ratio and the average virtual link propagation delay.

We prove a lower bound expressed in the increment sequence on the average-case complexity of the number of inversions of Shellsort. This lower bound is sharp in every case where it could be checked. A special case of this lower bound yields the general Jiang-Li-Vit\'anyi lower bound. We obtain new results e.g. determining the average-case complexity precisely in the Yao-Janson-Knuth 3-pass case., Comment: 13 pages LaTeX

This paper focuses on the classification of faults in an electromechanical switch machine, which is an equipment used for handling railroad switches. In this paper, we introduce the use of Set-Membership concept, derived from the adaptive filter theory, into the training procedure of type-1 and singleton/non-singleton fuzzy logic systems, in order to reduce computational complexity and to increase convergence speed. We also present different criteria for using along with Set-Membership. Furthermore, we discuss the usefulness of delta rule delta, local Lipschitz estimation, variable step size, and variable step size adaptive techniques to yield additional improvement in terms of computational complexity reduction and convergence speed. Based on data set provided by a Brazilian railway company, which covers the four possible faults in a switch machine, we present performance analysis in terms of classification ratio, convergence speed, and computational complexity reduction. The reported results show that the proposed models result in improved convergence speed, slightly higher classification ratio, and remarkable computation complexity reduction when we limit the number of epochs for training, which may be required due to real-time constraint or low computational resource availability.

Game semantics was initially defined and used to characterize pcf functionals. We use this approach to propose a definition of complexity for such higher-order functions, as well as a class of polynomial time computable higher-order functions. We define a notion of size and complexity for strategies in sequential games.This defines a notion of complexity for PCF functions.The corresponding higher-order polynomial time complexity class contains BFF.

Computing geodesic distances on 2-manifold meshes is a fundamental problem in computational geometry. To date, two notable classes of exact algorithms, namely, the Mitchell–Mount–Papadimitriou (MMP) algorithm and the Chen–Han (CH) algorithm, have been widely studied. For an arbitrary triangle mesh with n vertices, these algorithms have space complexity of O ( n 2 ) . In this paper, we prove that both algorithms have Θ ( n 1.5 ) space complexity on a completely regular triangulation (i.e., all triangles are equilateral).

In this work, we study Static and Dynamic Games on Large Networks of interacting agents, assuming that the players have some statistical description of the interaction graph, as well as some local information. Inspired by Statistical Physics, we consider statistical ensembles of games and define a Probabilistic Approximate equilibrium notion for such ensembles. A Necessary Information Complexity notion is introduced to quantify the minimum amount of information needed for the existence of a Probabilistic Approximate equilibrium. We then focus on some special classes of games for which it is possible to derive upper and/or lower bounds for the complexity. At first, static and dynamic games on random graphs are studied and their complexity is determined as a function of the graph connectivity. In the low complexity case, we compute Probabilistic Approximate equilibrium strategies. We then consider static games on lattices and derive upper and lower bounds for the complexity, using contraction mapping ideas. A LQ game on a large ring is also studied numerically. Using a reduction technique, approximate equilibrium strategies are computed and it turns out that the complexity is relatively low.

This paper proposes a criterion based on which, using methods of mathematical programming, an algorithm is constructed for successively reducing the limit complexity of a controller.

This paper proposes a methodology based on system connections to calculate its complexity. Two study cases are proposed: the dining Chinese philosophers’ problem and the distribution center. Both studies are modeled using the theory of Discrete Event Systems and simulations in different contexts were performed in order to measure their complexities. The obtained results present i) the static complexity as a limiting factor for the dynamic complexity, ii) the lowest cost in terms of complexity for each unit of measure of the system performance and iii) the output sensitivity to the input parameters. The associated complexity and performance measures aggregate knowledge about the system.

One of the central open questions in the theory of average-case complexity is to establish the equivalence between the worst-case and average-case complexity of the Polynomial-time Hierarchy (PH). One general approach is to show that there exists a PH-computable hitting set generator whose security is based on some NP-hard problem. We present the limits of such an approach, by showing that there exists no exponential-time-computable hitting set generator whose security can be proved by using a nonadaptive randomized polynomial-time reduction from any problem outside AM ∩ coAM, which significantly improves the previous upper bound BPP^NP of Gutfreund and Vadhan (RANDOM/APPROX 2008 [Gutfreund and Vadhan, 2008]). In particular, any security proof of a hitting set generator based on some NP-hard problem must use either an adaptive or non-black-box reduction (unless the polynomial-time hierarchy collapses). To the best of our knowledge, this is the first result that shows limits of black-box reductions from an NP-hard problem to some form of a distributional problem in DistPH. Based on our results, we argue that the recent worst-case to average-case reduction of Hirahara (FOCS 2018 [Hirahara, 2018]) is inherently non-black-box, without relying on any unproven assumptions. On the other hand, combining the non-black-box reduction with our simulation technique of black-box reductions, we exhibit the existence of a "non-black-box selector" for GapMCSP, i.e., an efficient algorithm that solves GapMCSP given as advice two circuits one of which is guaranteed to compute GapMCSP.

47th International Colloquium on Automata, Languages, and Programming, ICALP 2020, ; Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020). doi:10.4230/LIPIcs.ICALP.2020.40, Published by Schloss Dagstuhl - Leibniz-Zentrum für Informatik

We study a mixture between the average case and worst case complexities of higher-order model checking, the problem of deciding whether the tree generated by a given λ Y-term (or equivalently, a higher-order recursion scheme) satisfies the property expressed by a given tree automaton. Higher-order model checking has recently been studied extensively in the context of higher-order program verification. Although the worst-case complexity of the problem is k-EXPTIME complete for order-k terms, various higher-order model checkers have been developed that run efficiently for typical inputs, and program verification tools have been constructed on top of them. One may, therefore, hope that higher-order model checking can be solved efficiently in the average case, despite the worst-case complexity. We provide a negative result, by showing that, under certain assumptions, for almost every term, the higher-order model checking problem specialized for the term is k-EXPTIME hard with respect to the size of automata. The proof is based on a novel intersection type system that characterizes terms that do not contain any useless subterms.

This paper proposes a fast recursive algorithm for Group-wise Space-Time Block Code (G-STBC), which takes full advantage of the Alamouti structure in the equivalent channel matrix to reduce the computational complexity. With respect to the existing efficient algorithms for G-STBC, the proposed algorithm achieves better performance and usually requires less computational complexity., Comment: TCOM

This paper is aimed at a comparative study of several sorting algorithms with the purpose of evaluating their relative performance when the input array is randomly generated from zero-truncated binomial and poisson distributions. The sorting algorithms to be investigated are quick sort, k-sort, heap sort and merge sort, all having the same average case complexity of O(NlogN). In practical statistical cases, sometimes it is not possible to record or know about the occurrences as they are limited to values which exist above or below a given limit or within a particular range. Such situations result in truncated distributions. The relative performance of the above-mentioned sorting methods was compared on the basis of ‘execution time’ and the ‘number of swapping’ for both the average and worst cases of different algorithms.

We consider the methodology for proving lower bounds on the query complexity of property testing via communication complexity, which was put forward by Blais, Brody, and Matulef (Computational Complexity, 2012). They provided a restricted formulation of their methodology (via “simple combining operators”) and also hinted towards a more general formulation, which we spell out in this paper.

Suppose F:=(f_1,ldots,f_n) is a system of random n-variate polynomials with f_i having degree leq\!d_i and the coefficient of x^a_1 _1\cdots x^a_n _n in f_i being an independent complex Gaussian of mean 0 and variance \fracd_i! a_1!\cdots a_n!left(d_i-\sum^n_j=1 a_j \right)! . Recent progress on Smale's 17þth Problem by Lairez --- building upon seminal work of Shub, Beltran, Pardo, Bu rgisser, and Cucker --- has resulted in a deterministic algorithm that finds a single (complex) approximate root of F using just N^O(1) arithmetic operations on average, where N\!:=\!\sum^n_i=1 \frac(n+d_i)! n!d_i! (=n(n+\max_i d_i)^O(\min\n,\max_i d_i)\ ) is the maximum possible total number of monomial terms for such an F. However, can one go faster when the number of terms is smaller, and we restrict to real coefficient and real roots? And can one still maintain average-case polynomial-time with more general probability measures? We show the answer is yes when F is instead a binomial system --- a case whose numerical solution is a key step in polyhedral homotopy algorithms for solving arbitrary polynomial systems. We give a deterministic algorithm that finds a real approximate root (or correctly decides there are none) using just O(n^3log^2(n\max_i d_i)) arithmetic operations on average. Furthermore, our approach allows real Gaussians with arbitrary variance. We also discuss briefly the obstructions to maintaining average-case time polynomial in nlog \max_i d_i when F has more terms.

We show that complexity analysis of probabilistic higher-order functional programs can be carried out compositionally by way of a type system. The introduced type system is a significant extension of refinement types. On the one hand, the presence of probabilistic effects requires adopting a form of dynamic distribution type, subject to a coupling-based subtyping discipline. On the other hand, recursive definitions are proved terminating by way of Lyapunov ranking functions. We prove not only that the obtained type system, called $\ell \pmb{\mathsf{RPCF}}$ , provides a sound methodology for average case complexity analysis, but also that it is extensionally complete, in the sense that any average case nolytime Turing machines can be encoded as a term typable in $\ell\pmb{\mathsf{RPCF}}$ .

We consider the problem of counting $k$-cliques in $s$-uniform Erdos-Renyi hypergraphs $G(n,c,s)$ with edge density $c$, and show that its fine-grained average-case complexity can be based on its worst-case complexity. We prove the following: 1. Dense Erdos-Renyi graphs and hypergraphs: Counting $k$-cliques on $G(n,c,s)$ with $k$ and $c$ constant matches its worst-case time complexity up to a $\mathrm{polylog}(n)$ factor. Assuming randomized ETH, it takes $n^{\Omega(k)}$ time to count $k$-cliques in $G(n,c,s)$ if $k$ and $c$ are constant. 2. Sparse Erdos-Renyi graphs and hypergraphs: When $c = \Theta(n^{-\alpha})$, we give several algorithms exploiting the sparsity of $G(n, c, s)$ that are faster than the best known worst-case algorithms. Complementing this, based on a fine-grained worst-case assumption, our results imply a different average-case phase diagram for each fixed $\alpha$ depicting a tradeoff between a runtime lower bound and $k$. Surprisingly, in the hypergraph case ($s \ge 3$), these lower bounds are tight against our algorithms exactly when $c$ is above the Erd\H{o}s-R\'{e}nyi $k$-clique percolation threshold. This is the first worst-case-to-average-case hardness reduction for a problem on Erd\H{o}s-R\'{e}nyi hypergraphs that we are aware of. We also give a variant of our result for computing the parity of the $k$-clique count that tolerates higher error probability., Comment: 44 pages, 2 figures, appeared in FOCS'19, accepted to SICOMP special edition

We study output-sensitive algorithms and complexity for multiobjective combinatorial optimization problems. In this computational complexity framework, an algorithm for a general enumeration problem is regarded efficient if it is output-sensitive, i.e., its running time is bounded by a polynomial in the input and the output size. We provide both practical examples of MOCO problems for which such an efficient algorithm exists as well as problems for which no efficient algorithm exists under mild complexity theoretic assumptions.

The primary goal of this paper is to define and study the interactive information complexity of functions. Let f(x,y) be a function, and suppose Alice is given x and Bob is given y. Informally, the interactive information complexity IC(f) of f is the least amount of information Alice and Bob need to reveal to each other to compute f. Previously, information complexity has been defined with respect to a prior distribution on the input pairs (x,y). Our first goal is to give a definition that is independent of the prior distribution. We show that several possible definitions are essentially equivalent. We establish some basic properties of the interactive information complexity IC(f). In particular, we show that IC(f) is equal to the amortized (randomized) communication complexity of f. We also show a direct sum theorem for IC(f) and give the first general connection between information complexity and (non-amortized) communication complexity. This connection implies that a non-trivial exchange of information is required when solving problems that have non-trivial communication complexity. We explore the information complexity of two specific problems - Equality and Disjointness. We show that only a constant amount of information needs to be exchanged when solving Equality with no errors, while solving Disjointness with a constant error probability requires the parties to reveal a linear amount of information to each other.

We extend the reach of fixed-parameter analysis by introducing classes of parameterized sets defined based on decidability instead of complexity. Known results in computability theory can be expressed in the language of fixed-parameter analysis, making use of the landscape of these new classes. On the one hand this unifies results that would not otherwise show their kinship, while on the other it allows for further exchange of insights between complexity theory and computability theory. In the landscape of our fixed-parameter decidability classes, we recover part of the classification of real numbers according to their computability. From this, using the structural properties of the landscape, we get a new proof of the existence of P-selective bi-immune sets. Furthermore, we show that parameter values in parameterized sets in our uniformly fixed-parameter decidability classes interact with both instance complexity and Kolmogorov complexity. By deriving a parameter based upper bound on instance complexity, we demonstrate how parameters convey a sense of randomness. Motivated by the instance complexity conjecture, we show that the upper bound on the instance complexity is infinitely often also an upper bound on the Kolmogorov complexity.