Search

An average-case variant of the k-SUM conjecture asserts that finding k numbers that sum to 0 in a list of r random numbers, each of the order rk, cannot be done in much less than \(r^{\lceil k/2 \rceil }\) time. However, in the dense regime of parameters, where the list contains more numbers and many solutions exist, the complexity of finding one of them can be significantly improved by Wagner's k-tree algorithm. Such algorithms for k-SUM in the dense regime have many applications, notably in cryptanalysis. In this article, assuming the average-case k-SUM conjecture, we prove that known algorithms are essentially optimal for k= 3,4,5. For k> 5, we prove the optimality of the k-tree algorithm for a limited range of parameters. We also prove similar results for k-XOR, where the sum is replaced with exclusive or. Our results are obtained by a self-reduction that, given an instance of k-SUM that has a few solutions, produces from it many instances in the dense regime. We solve each of these instances using the dense k-SUM oracle and hope that a solution to a dense instance also solves the original problem. We deal with potentially malicious oracles (that repeatedly output correlated useless solutions) by an obfuscation process that adds noise to the dense instances. Using discrete Fourier analysis, we show that the obfuscation eliminates correlations among the oracle's solutions, even though its inputs are highly correlated. [ABSTRACT FROM AUTHOR]

This paper addresses the semi-online scheduling problem of minimising the total weighted completion time on a single machine, where a combination of information on jobs release dates and processing times is considered. In this study, jobs can only arrive at known future times and a lower bound on jobs processing times is known in advance. A new semi-online algorithm is presented and is shown to be the best possible for the considered problem. In order to make this statement, a new lower bound on the competitive ratio of any semi-online algorithm for the problem is developed and, using competitive analysis, the proposed semi-online algorithm is shown to have a competitive ratio that matches the lower bound. [ABSTRACT FROM AUTHOR]

We study equi-join computation in the massively parallel computation (MPC) model. Currently, a main open question under this topic is whether it is possible to design an algorithm that can process any join with load O(N polylog N/p1/ρ*) — measured in the number of words communicated per machine — where N is the total number of tuples in the input relations, ρ* is the join's fractional edge covering number, and p is the number of machines. We settle the question in the negative for the class of tuple-based algorithms (all the known MPC join algorithms fall in this class) by proving the existence of a join query with ρ* = 2 that requires a load of Ω (N/p1/3) to evaluate. Our lower bound provides solid evidence that the "AGM bound" alone is not sufficient for characterizing the hardness of join evaluation in MPC (a phenomenon that does not exist in RAM). The hard join instance identified in our argument is cyclic, which leaves the question of whether O(N polylog N/p1/ρ*) is still possible for acyclic joins. We answer this question in the affirmative by showing that any acyclic join can be evaluated with load O(N / p1/ρ*), which is asymptotically optimal (there are no polylogarithmic factors in our bound). The separation between cyclic and acyclic joins is yet another phenomenon that is absent in RAM. Our algorithm owes to the discovery of a new mathematical structure — we call "canonical edge cover" — of acyclic hypergraphs, which has numerous non-trivial properties and makes an elegant addition to database theory. [ABSTRACT FROM AUTHOR]

Nearly thirty years ago, it was shown that \(\Omega (\sqrt {n})\) read/write registers are needed to solve randomized wait-free consensus among n processes. This lower bound was improved to n registers in 2018, which exactly matches known algorithms. The \(\Omega (\sqrt {n})\) space complexity lower bound actually applies to a class of objects called historyless objects, which includes registers, test-and-set objects, and readable swap objects. However, every known n-process obstruction-free consensus algorithm from historyless objects uses Ω (n) objects. In this paper, we give the first Ω (n) space complexity lower bounds on consensus algorithms for two kinds of historyless objects. First, we show that any obstruction-free consensus algorithm from swap objects uses at least n-1 objects. More generally, we prove that any obstruction-free k-set agreement algorithm from swap objects uses at least \(\lceil \frac{n}{k}\rceil - 1\) objects. The k-set agreement problem is a generalization of consensus in which processes agree on no more than k different output values. This is the first non-constant lower bound on the space complexity of solving k-set agreement with swap objects when k > 1. We also present an obstruction-free k-set agreement algorithm from n-k swap objects, which exactly matches our lower bound when k=1. Second, we show that any obstruction-free binary consensus algorithm from readable swap objects with domain size b uses at least \(\frac{n-2}{3b+1}\) objects. When b is a constant, this asymptotically matches the best known obstruction-free consensus algorithms from readable swap objects with unbounded domains. Since any historyless object can be simulated by a readable swap object with the same domain, our results imply that any obstruction-free consensus algorithm from historyless objects with domain size b uses at least \(\frac{n-2}{3b+1}\) objects. For b = 2, we show a slightly better lower bound of n-2. There is an obstruction-free binary consensus algorithm using 2n-1 readable swap objects with domain size 2, asymptotically matching our lower bound. [ABSTRACT FROM AUTHOR]

We prove near-optimal tradeoffs for quantifier depth (also called quantifier rank) versus number of variables in first-order logic by exhibiting pairs of n-element structures that can be distinguished by a k-variable firstorder sentence but where every such sentence requires quantifier depth at least nΩ(k/logk). Our tradeoffs also apply to first-order counting logic and, by the known connection to the k-dimensional Weisfeiler--Leman algorithm, imply near-optimal lower bounds on the number of refinement iterations. A key component in our proof is the hardness condensation technique introduced by Razborov in the context of proof complexity. We apply this method to reduce the domain size of relational structures while maintaining the minimal quantifier depth needed to distinguish them in finite variable logics. [ABSTRACT FROM AUTHOR]

Given simple graphs \(X\) and \(Y\) on the same number of vertices, the friends-and-strangers graph \(\operatorname{FS}(X, Y)\) has as its vertices all bijections from \(V(X)\) to \(V(Y)\), where two bijections are adjacent if and only if they differ on two adjacent elements of \(V(X)\) with images adjacent in \(Y\). We study the diameters of connected components of friends-and-strangers graphs: the diameter of a component of \(\operatorname{FS}(X,Y)\) corresponds to the largest number of swaps necessary to go from one configuration in the component to another. We show that any component of \(\operatorname{FS}(\operatorname{Path}_n, Y)\) has \(O(n^2)\) diameter and that any component of \(\operatorname{FS}(\operatorname{Cycle}_n, Y)\) has \(O(n^4)\) diameter, improvable to \(O(n^3)\) whenever \(\operatorname{FS}(\operatorname{Cycle}_n, Y)\) is connected. Answering a question raised by Alon, Defant, and Kravitz in the negative, we use an explicit construction to show that there exist \(n\)-vertex graphs \(X\) and \(Y\) such that \(\operatorname{FS}(X,Y)\) has a component with \(e^{\Omega(n)}\) diameter. We conclude with several suggestions for future research.Mathematics Subject Classifications: 05C12, 05C35, 05C38Keywords: Friends-and-strangers graphs, diameter, extremal combinatorics, lower bounds, paths, cycles, token swapping, interchange process

We consider the oracle complexity of computing an approximate stationary point of a Lipschitz function. When the function is smooth, it is well known that the simple deterministic gradient method has finite dimension-free oracle complexity. However, when the function can be nonsmooth, it is only recently that a randomized algorithm with finite dimension-free oracle complexity has been developed. In this paper, we show that no deterministic algorithm can do the same. Moreover, even without the dimension-free requirement, we show that any finite-time deterministic method cannot be general zero-respecting. In particular, this implies that a natural derandomization of the aforementioned randomized algorithm cannot have finite-time complexity. Our results reveal a fundamental hurdle in modern large-scale nonconvex nonsmooth optimization. [ABSTRACT FROM AUTHOR]

In this note we study estimates from below of the single radius spherical discrepancy in the setting of compact two-point homogeneous spaces. Namely, given a d-dimensional manifold M endowed with a distance ρ so that (M , ρ) is a two-point homogeneous space and with the Riemannian measure μ , we provide conditions on r such that if D r denotes the discrepancy of the ball of radius r, then, for an absolute constant C > 0 and for every set of points { x j } j = 1 N , one has ∫ M | D r (x) | 2 d μ (x) ⩾ C N - 1 - 1 d . The conditions on r that we have depend on the dimension d of the manifold and cannot be achieved when d ≡ 1 (mod 4) . Nonetheless, we prove a weaker estimate for such dimensions as well. [ABSTRACT FROM AUTHOR]

Many Boolean functions that need to be encoded as CNF in practice, have only exponential size CNF representations. To avoid this effect, one usually introduces nondeterministic variables. For example, whereas the minimum number of clauses in a CNF computing the parity function x 1 ⊕ x 2 ⊕ ⋯ ⊕ x n is 2 n - 1 , one can use n - 1 nondeterministic variables to get a CNF encoding with 4n clauses. In this paper, we prove tradeoffs between various parameters (the number of clauses, the width of clauses, and the number of nondeterministic variables) of CNF encodings of various symmetric functions. In particular, we show that a folklore way of encoding parity as CNF is provably optimal. We do this by using a tight connection between CNF encodings and depth-3 circuits. This connection shows that CNF encodings is an interesting computational model for Boolean functions: on the one hand, it is routinely used in practice when translating a computational problem to a format acceptable by a SAT solver, on the other hand, lower bounds on the size of CNF encodings imply depth-3 circuit lower bounds. [ABSTRACT FROM AUTHOR]

The eigenvalues of complex q-Sturm–Liouville boundary value problems are the focus of this paper. The coefficients of the corresponding q-Sturm–Liouville equation provide the lower bounds on the real parts of all eigenvalues, and the real part of the eigenvalue and the coefficients of this q-Sturm–Liouville equation provide the bounds on the imaginary part of each eigenvalue. [ABSTRACT FROM AUTHOR]

A monotone Boolean (∨ , ∧) circuit computing a monotone Boolean function f is a read- k circuit if the polynomial produced (purely syntactically) by the arithmetic (+ , ×) version of the circuit has the property that for every prime implicant of f , the polynomial contains at least one monomial with the same set of variables, each appearing with degree ⩽ k. Every monotone circuit is a read- k circuit for some k. We show that already read-1 (∨ , ∧) circuits are not weaker than monotone arithmetic constant-free (+ , ×) circuits computing multilinear polynomials, are not weaker than non-monotone multilinear (∨ , ∧ , ¬) circuits computing monotone Boolean functions, and have the same power as tropical (min , +) circuits solving 0 / 1 minimization problems. Finally, we show that read-2 (∨ , ∧) circuits can be exponentially smaller than read-1 (∨ , ∧) circuits. [ABSTRACT FROM AUTHOR]

In this paper sharp lower error bounds for numerical methods for jump-diffusion stochastic differential equations (SDEs) with discontinuous drift are proven. The approximation of jump-diffusion SDEs with non-adaptive as well as jump-adapted approximation schemes is studied and lower error bounds of order 3/4 for both classes of approximation schemes are provided. This yields optimality of the transformation-based jump-adapted quasi-Milstein scheme. [ABSTRACT FROM AUTHOR]

It is well-known that randomness is essential for secure cryptography. The randomness used in cryptographic primitives is not necessarily recoverable even by the party who can, e.g., decrypt or recover the underlying secret/message. Several cryptographic primitives that support randomness recovery have turned out useful in various applications. In this paper, we study randomness recoverable secret sharing schemes (RR-SSS), in both information-theoretic and computational settings and provide two results. First, we show that while every access structure admits a perfect RR-SSS, there are very simple access structures (e.g., in monotone AC 0 ) that do not admit efficient perfect (or even statistical) RR-SSS. Second, we show that the existence of efficient computational RR-SSS for certain access structures in monotone AC 0 implies the existence of one-way functions. This stands in sharp contrast to (non-RR) SSS schemes for which no such results are known. RR-SSS plays a key role in making advanced attributed-based encryption schemes randomness recoverable, which in turn have applications in the context of designated-verifier non-interactive zero knowledge. [ABSTRACT FROM AUTHOR]

We show that, for every homogeneous polynomial of degree d , if it has determinantal complexity at most s , then it can be computed by a homogeneous algebraic branching program (ABP) of size at most O (d 5 s) . Moreover, we show that for most homogeneous polynomials, the width of the resulting homogeneous ABP is just s - 1 and the size is at most O (d s) . Thus, for constant-degree homogeneous polynomials, their determinantal complexity and ABP complexity are within a constant factor of each other and hence, a super-linear lower bound for ABPs for any constant-degree polynomial implies a super-linear lower bound on determinantal complexity; this relates two open problems of great interest in algebraic complexity. As of now, super-linear lower bounds for ABPs are known only for polynomials of growing degree (Chatterjee et al. 2022; Kumar 2019), and for determinantal complexity the best lower bounds are larger than the number of variables only by a constant factor (Kumar & Volk 2022). While determinantal complexity and ABP complexity are classically known to be polynomially equivalent (Mahajan & Vinay 1997), the standard transformation from the former to the latter incurs a polynomial blow up in size in the process, and thus, it was unclear if a super-linear lower bound for ABPs implies a super-linear lower bound on determinantal complexity. In particular, a size preserving transformation from determinantal complexity to ABPs does not appear to have been known prior to this work, even for constant-degree polynomials. [ABSTRACT FROM AUTHOR]

Abraham, Dolev, Geffner, and Halpern [1] proved that, in asynchronous systems, a (k, t )-robust equilibrium for n players and a trusted mediator can be implemented without the mediator as long as n > 4(k +t ), where an equilibrium is (k, t )-robust if, roughly speaking, no coalition of t players can decrease the payoff of any of the other players, and no coalition of k players can increase their payoff by deviating. We prove that this bound is tight, in the sense that if n ≤ 4(k+t ) there exist (k, t )-robust equilibriawith a mediator that cannot be implemented by the players alone. Even though implementing (k, t )-robust mediators seems closely related to implementing asynchronous multiparty (k +t )-secure computation [6], to the best of our knowledge there is no known straightforward reduction from one problem to another. Nevertheless, we show that there is a non-trivial reduction from a slightly weaker notion of (k +t )-secure computation, which we call (k +t )-strict secure computation, to implementing (k, t )-robust mediators. We prove the desired lower bound by showing that there are functions on n variables that cannot be (k + t )-strictly securely computed if n ≤ 4(k + t ). This also provides a simple alternative proof for the well-known lower bound of 4t + 1 on asynchronous secure computation in the presence of up to t malicious agents. [ABSTRACT FROM AUTHOR]

For a size parameter s : ℕ → ℕ , the Minimum Circuit Size Problem (denoted by MCSP[s(n)]) is the problem of deciding whether the minimum circuit size of a given function f : {0,1}n →{0,1} (represented by a string of length N := 2n) is at most a threshold s(n). A recent line of work exhibited "hardness magnification" phenomena for MCSP: A very weak lower bound for MCSP implies a breakthrough result in complexity theory. For example, McKay, Murray, and Williams (STOC 2019) implicitly showed that, for some constant μ1 > 0, if MCSP [ 2 μ 1 ⋅ n ] cannot be computed by a one-tape Turing machine (with an additional one-way read-only input tape) running in time N1.01, then P≠NP. In this paper, we present the following new lower bounds against one-tape Turing machines and branching programs: (1) A randomized two-sided error one-tape Turing machine (with an additional one-way read-only input tape) cannot compute MCSP [ 2 μ 2 ⋅ n ] in time N1.99, for some constant μ2 > μ1. (2) A non-deterministic (or parity) branching program of size o (N 1.5 / log N) cannot compute MKTP, which is a time-bounded Kolmogorov complexity analogue of MCSP. This is shown by directly applying the Nečiporuk method to MKTP, which previously appeared to be difficult. (3) The size of any non-deterministic, co-non-deterministic, or parity branching program computing MCSP is at least N 1.5 − o 1 . These results are the first non-trivial lower bounds for MCSP and MKTP against one-tape Turing machines and non-deterministic branching programs, and essentially match the best-known lower bounds for any explicit functions against these computational models. The first result is based on recent constructions of pseudorandom generators for read-once oblivious branching programs (ROBPs) and combinatorial rectangles (Forbes and Kelley, FOCS 2018; Viola, Electron. Colloq. Comput. Complexity (ECCC) 26, 51, 2019). En route, we obtain several related results: (1) There exists a (local) hitting set generator with seed length O ~ (N) secure against read-once polynomial-size non-deterministic branching programs on N-bit inputs. (2) Any read-once co-non-deterministic branching program computing MCSP must have size at least 2 Ω ~ (N) . [ABSTRACT FROM AUTHOR]

The amount of hyperplanes that are needed in order to cover the Boolean cube has been studied in various contexts. Linial and Radhakrishnan introduced the notion of essential covers. An essential cover is a collection of hyperplanes that form a minimal cover of the vertices of the hypercube, and every coordinate is influential in at least one of the hyperplanes. Linial and Radhakrishnan proved using algebraic tools that every essential cover of the n-cube must be of size at least Ω (n) . We devise a stronger lower bound method, and show that the size of every essential cover is at least Ω (n 0.52) . This result has implications in proof complexity, because essential covers have been used to prove lower bounds for several proof systems. [ABSTRACT FROM AUTHOR]

We study the 2k-th moment of central values of the family of Dirichlet L-functions to a fixed prime modulus. We establish sharp lower bounds for all real k ≥ 0 and sharp upper bounds for k in the range 0 ≤ k ≤ 1 . [ABSTRACT FROM AUTHOR]

This study aims to address a variant of the hybrid flow shop problem by simultaneously integrating lag times, unloading times, and transportation times, with the goal of minimizing the maximum completion time, or makespan. With applications in image processing, manufacturing, and industrial environments, this problem presents significant theoretical challenges, being classified as NP-hard. Notably, the problem demonstrates a notable symmetry property, resulting in a symmetric problem formulation where both the scheduling problem and its symmetric counterpart share the same optimal solution. To improve solution quality, all proposed procedures are extended to the symmetric problem. This research pioneers the consideration of the hybrid flow shop scheduling problem with simultaneous attention to lag, unloading, and transportation times, building upon a comprehensive review of existing literature. A two-phase heuristic is introduced as a solution to this complex problem, involving iterative solving of parallel machine scheduling problems. This approach decomposes the problem into manageable sub-problems, facilitating focused and efficient resolution. The efficient solving of sub-problems using the developed heuristic yields satisfactory near-optimal solutions. Additionally, two new lower bounds are proposed, derived from estimating minimum idle time within each stage via solving a polynomial parallel machine problem aimed at minimizing total flow time. These lower bounds serve to evaluate the performance of the developed two-phase heuristic, over measuring the relative gap. Extensive experimental studies on benchmark test problems of varying sizes demonstrate the effectiveness of the proposed approaches. All test problems are efficiently solved within reasonable timeframes, indicating practicality and efficiency. The proposed methods exhibit an average computational time of 8.93 seconds and an average gap of 2.75%. These computational results underscore the efficacy and potential applicability of the proposed approaches in real-world scenarios, providing valuable insights and paving the way for further research and practical implementations in hybrid flow shop scheduling. [ABSTRACT FROM AUTHOR]

Improving efficiency in multi-stage flexible flowshop operations is essential for modern industrial systems. Optimizing total completion time while simultaneously considering the unloading and transportation times is vital for enhanced productivity and cost-effectiveness. This study delves into the intricate realm of flexible flow shop scheduling, particularly focusing on scenarios prevalent in modern manufacturing processes such as sand casting. Despite limited exploration in prior literature for particular cases, the significance of this problem underscores the pressing need for efficient algorithms and the exploration of new problem properties. Notably, we unveil the symmetry inherent in the problem, where scheduling from the initial stage to the final one, or vice versa, yields identical optimal solutions, thereby augmenting solution quality. Given the strongly NP-Hard nature of the problem, approximate solutions are preferred, especially for medium to large-scale instances. To address this challenge, we propose a novel two-phase heuristic approach, encompassing both a constructive phase and an improvement phase. Leveraging an existing efficient heuristic tailored for parallel machine scheduling, our method extends to efficiently incorporate considerations for unloading and transportation times. The efficacy of the two-phase heuristic lies in its ability to consistently generate high-quality schedules at each stage. Furthermore, we introduce efficient lower bounds derived from estimating the minimum idle time within each stage, drawing from insights in polynomial parallel machine scheduling with a focus on flow time minimization in preceding stages. These lower bounds serve as critical benchmarks for evaluating the performance of the two-phase heuristic against the relative gap performance measure. Extensive experimentation on benchmark test problems underscores the effectiveness of our proposed algorithms, with results demonstrating an average computation time of 9.48 seconds and a mean relative gap of only 2.42% across varying job and stage quantities up to 200 jobs and 10 stages. [ABSTRACT FROM AUTHOR]

Determining the number of registers required for solving obstruction-free (or randomized wait-free) k-set agreement is an open problem that highlights important gaps in our understanding of the space complexity of synchronization. The best known upper bound on the number of registers needed to solve this problem among n > k processes is n k + 1 registers. No general lower bound better than 2 was known. We prove that any obstruction-free protocol solving k-set agreement among n >k processes must use at least n/k registers. In particular, we get a tight lower bound of exactly n registers for solving obstruction-free and randomized wait-free consensus. Our main tool is a simulation that serves as a reduction from the impossibility of deterministic waitfree k-set agreement. In particular, we show that if an obstruction-free protocol for k-set agreement uses fewer registers, then it is possible for k +1 processes to simulate the protocol and deterministically solve k-set agreement in a wait-free manner, which is impossible. An important aspect of the simulation is the ability of simulating processes to revise the past of simulated processes. We introduce an augmented snapshot object, which facilitates this. More generally, our simulation applies to the broad class of colorless tasks. We can use it to prove, for example, a lower bound on the number of registers needed to solve obstruction-free epsilon -approximate agreement, which matches the best known upper bound to within a factor of 2 when epsilon is sufficiently small. No general lower bound for this problem was known. Finally, we prove that any lower bound on the number of registers used by obstruction-free protocols applies to protocols that satisfy nondeterministic solo-termination. Hence, our lower bounds for obstruction-free protocols also hold for randomized wait-free protocols. [ABSTRACT FROM AUTHOR]

In this paper, we establish the expected order of magnitude of the k th-moment of central values of the family of Dirichlet L -functions to a fixed prime modulus over function fields for all real k ≥ 0. [ABSTRACT FROM AUTHOR]

This paper considers the problem of scheduling independent jobs with release dates and tails on m identical machines to minimize the makespan. The three main bounds are the preemptive bound, the energetic bound and the Jackson Pseudo Preemptive bound. It is known that they are very close in practice. The aim of this paper is to provide worst case instances where the slack between them is maximal and to prove tight bounds on the slack. We show that the slack is smaller than the maximal processing time. [ABSTRACT FROM AUTHOR]

This paper tackles the two-machine chain-reentrant flow shop scheduling problem with the no-wait constraint; we assume that each job passes from the first machine to the second and returns back to the first machine in order to execute its last operation. The objective is to minimize the makespan. In this work, we prove that the symmetric case of this problem, which is proven to be N P -hard in the strong sense, remains N P -hard. Then we provide two polynomial subproblems. For the main problem’s resolution, we propose two new efficient heuristics as well as two improved lower bounds that consistently outperform the existing methods. Additionally, we provide an effective Branch & Bound algorithm that can solve up to 100 jobs for some types of instances. These contributions not only enhance the theoretical comprehension of the problem but also offer efficient solutions supported by extensive statistical analysis over randomly generated instances. [ABSTRACT FROM AUTHOR]

The aim of this paper is to propose efficient algorithms for computing the energetic lower bounds of the cumulative sheduling problem. So we have to schedule in a minimal makespan a set of non preemptive tasks on a resource with a given capacity. A task has a release date, a processing time and a tail and requires a given amount of the resource capacity during its processing. The energetic lower bound is the largest value of the makespan such that the energetic reasoning check cannot detect unfeasability. We report some algorithms to practically compute this lower bound with efficient complexity. These algorithms rely on iterative augmentations of C max until the cumulative constraint or the energetic constraint is satisfied. Our Computational results show their practical efficiencies. [ABSTRACT FROM AUTHOR]

The Multi-Objective Mixed-Integer Programming (MOMIP) problem is one of the most challenging. To derive its Pareto optimal solutions one can use the well-known Chebyshev scalarization and Mixed-Integer Programming (MIP) solvers. However, for a large-scale instance of the MOMIP problem, its scalarization may not be solved to optimality, even by state-of-the-art optimization packages, within the time limit imposed on optimization. If a MIP solver cannot derive the optimal solution within the assumed time limit, it provides the optimality gap, which gauges the quality of the approximate solution. However, for the MOMIP case, no information is provided on the lower and upper bounds of the components of the Pareto optimal outcome. For the MOMIP problem with two and three objective functions, an algorithm is proposed to provide the so-called interval representation of the Pareto optimal outcome designated by the weighting vector when there is a time limit on solving the Chebyshev scalarization. Such interval representations can be used to navigate on the Pareto front. The results of several numerical experiments on selected large-scale instances of the multi-objective multidimensional 0–1 knapsack problem illustrate the proposed approach. The limitations and possible enhancements of the proposed method are also discussed. [ABSTRACT FROM AUTHOR]

We establish sharp lower bonds for the 2k-th moment of families of quadratic twists of modular L-functions at the central point for all real k < 0 , assuming a conjecture of S. Chowla on the non-vanishing of these L-values. [ABSTRACT FROM AUTHOR]

In this paper, we study the power and limitations of component-stable algorithms in the low-space model of massively parallel computation (MPC). Recently Ghaffari, Kuhn and Uitto (FOCS 2019) introduced the class of component-stable low-space MPC algorithms, which are, informally, those algorithms for which the outputs reported by the nodes in different connected components are required to be independent. This very natural notion was introduced to capture most (if not all) of the known efficient MPC algorithms to date, and it was the first general class of MPC algorithms for which one can show non-trivial conditional lower bounds. In this paper we enhance the framework of component-stable algorithms and investigate its effect on the complexity of randomized and deterministic low-space MPC. Our key contributions include: 1. We revise and formalize the lifting approach of Ghaffari, Kuhn and Uitto. This requires a very delicate amendment of the notion of component stability, which allows us to fill in gaps in the earlier arguments. 2. We also extend the framework to obtain conditional lower bounds for deterministic algorithms and fine-grained lower bounds that depend on the maximum degree Δ . 3. We demonstrate a collection of natural graph problems for which deterministic component-unstable algorithms break the conditional lower bound obtained for component-stable algorithms. This implies that, in the context of deterministic algorithms, component-stable algorithms are conditionally weaker than the component-unstable ones. 4. We also show that the restriction to component-stable algorithms has an impact in the randomized setting. We present a natural problem which can be solved in O(1) rounds by a component-unstable MPC algorithm, but requires Ω (log log ∗ n) rounds for any component-stable algorithm, conditioned on the connectivity conjecture. Altogether our results imply that component-stability might limit the computational power of the low-space MPC model, at least in certain contexts, paving the way for improved upper bounds that escape the conditional lower bound setting of Ghaffari, Kuhn, and Uitto. [ABSTRACT FROM AUTHOR]

Quantified conflict-driven clause learning (QCDCL) is one of the main solving approaches for quantified Boolean formulas (QBF). One of the differences between QCDCL and propositional CDCL is that QCDCL typically follows the prefix order of the QBF for making decisions. We investigate an alternative model for QCDCL solving where decisions can be made in arbitrary order. The resulting system QCDCL A NY is still sound and terminating, but does not necessarily allow to always learn asserting clauses or cubes. To address this potential drawback, we additionally introduce two subsystems that guarantee to always learn asserting clauses ( QCDCL U NI - A NY ) and asserting cubes ( QCDCL E XI - A NY ), respectively. We model all four approaches by formal proof systems and show that QCDCL U NI - A NY is exponentially better than QCDCL on false formulas, whereas QCDCL E XI - A NY is exponentially better than QCDCL on true QBFs. Technically, this involves constructing specific QBF families and showing lower and upper bounds in the respective proof systems. We complement our theoretical study with some initial experiments that confirm our theoretical findings. [ABSTRACT FROM AUTHOR]

This study aims to address a variant of the hybrid flow shop problem by simultaneously integrating lag times, unloading times, and transportation times, with the goal of minimizing the maximum completion time, or makespan. With applications in image processing, manufacturing, and industrial environments, this problem presents significant theoretical challenges, being classified as NP-hard. Notably, the problem demonstrates a notable symmetry property, resulting in a symmetric problem formulation where both the scheduling problem and its symmetric counterpart share the same optimal solution. To improve solution quality, all proposed procedures are extended to the symmetric problem. This research pioneers the consideration of the hybrid flow shop scheduling problem with simultaneous attention to lag, unloading, and transportation times, building upon a comprehensive review of existing literature. A two-phase heuristic is introduced as a solution to this complex problem, involving iterative solving of parallel machine scheduling problems. This approach decomposes the problem into manageable sub-problems, facilitating focused and efficient resolution. The efficient solving of sub-problems using the developed heuristic yields satisfactory near-optimal solutions. Additionally, two new lower bounds are proposed, derived from estimating minimum idle time within each stage via solving a polynomial parallel machine problem aimed at minimizing total flow time. These lower bounds serve to evaluate the performance of the developed two-phase heuristic, over measuring the relative gap. Extensive experimental studies on benchmark test problems of varying sizes demonstrate the effectiveness of the proposed approaches. All test problems are efficiently solved within reasonable timeframes, indicating practicality and efficiency. The proposed methods exhibit an average computational time of 8.93 seconds and an average gap of 2.75%. These computational results underscore the efficacy and potential applicability of the proposed approaches in real-world scenarios, providing valuable insights and paving the way for further research and practical implementations in hybrid flow shop scheduling.

Agreeing on a common value among a set of agents is a fundamental problem in distributed computing, which occurs in several variants: In contrast to exact consensus, approximate variants are studied in systems where exact agreement is not possible or required, e.g., in human-made distributed control systems and in the analysis of natural distributed systems, such as bird flocking and opinion dynamics. We study the time complexity of two classical agreement problems: non-terminating asymptotic consensus and terminating approximate consensus. Asymptotic consensus, requires agents to repeatedly set their out- puts such that the outputs converge to a common value within the convex hull of initial values; approximate consensus requires agents to eventually stop setting their outputs, which must then lie within a predefined distance of each other. We prove tight lower bounds on the contraction ratios of asymptotic consensus algorithms subject to oblivious message adversaries, from which we deduce bounds on the time complexity of approximate consensus algorithms. In particular, the obtained bounds show optimality of asymptotic and approximate consensus algorithms presented by Charron-Bost et al. (ICALP’16) for certain systems, including the strongest oblivious message adversary in which asymptotic and approximate consensus are solvable. As a corollary we also obtain asymptotically tight bounds for asymptotic consensus in the classical asynchronous model with crashes. Central to the lower-bound proofs is an extended notion of valency, the set of reachable limits of an asymptotic consensus algorithm starting from a given configuration. We further relate topological properties of valencies to the solvability of exact consensus, shedding some light on the relation of these three fundamental problems in dynamic networks. [ABSTRACT FROM AUTHOR]

Semialgebraic range searching, arguably the most general version of range searching, is a fundamental problem in computational geometry. In the problem, we are to preprocess a set of n points in R D such that the subset of points inside a semialgebraic region described by a constant number of polynomial inequalities of degree Δ can be found efficiently. Relatively recently, several major advances were made on this problem. Using algebraic techniques, "near-linear space" data structures (Agarwal et al. 2013, Yao and Yao 1985) with almost optimal query time of Q (n) = O (n 1 - 1 / D + o (1)) were obtained. This upper bound was developed in the realRAM model equipped with semigroup operations and works for general range searching problems described in the semigroup model. The data structure is essentially a tree-based structure and thus also works for the important special case of range reporting in the more restrictive pointer machine model. For "fast query" data structures (i.e., when Q (n) = n o (1) ), it was conjectured that a similar improvement is possible, i.e., it is possible to achieve space S (n) = O (n D + o (1)) . The conjecture was refuted very recently by Afshani and Cheng (2021). In the plane, i.e., D = 2 , they proved that S (n) = Ω (n Δ + 1 - o (1) / Q (n) (Δ + 3) Δ / 2) which shows Ω (n Δ + 1 - o (1)) space is needed for Q (n) = n o (1) + O (k) where k is the output size for range reporting queries in the pointer machine model. While this refutes the conjecture, it still leaves a number of unresolved issues: First, their lower bound is limited to semialgebraic sets defined by (restricted) bivariate polynomials, while the upper bound holds for general D-variate polynomials. Second, even for bivariate polynomials, the upper bound is O (n b / Q (n) 2 (b - 1)) (Agarwal et al. 2021) where the exponent b = Δ + 2 2 - 1 is much larger than Δ + 1 - o (1) in their lower bound. This is because their lower bound is based on bivariate polynomials defined by Δ + 1 coefficients, while in general a monic bivariate polynomial can have b coefficients. Finally, even for the semialgebraic sets (those defined by Δ + 1 coefficients) they considered, the upper bound is S (n) = O (n Δ + 1 / Q (n) 2 Δ) which has a much smaller exponent of Q(n) in the denominator than that in their lower bound. This means their lower bound is only tight when Q (n) = n o (1) . In this paper, we resolve two of the issues: we prove a lower bound in D-dimensions, for any constant D, and show that when the query time is n o (1) + O (k) , the space usage is Ω (n m - o (1)) where m = D + Δ D - 1 is the maximum number of coefficients needed to define a monic D-variate degree- Δ polynomial, which almost matches the O ~ (n m) upper bound and essentially closes the problem for the fast-query case, as far as the exponent of n is considered in the pointer machine model. When considering the exponent of Q(n), we show that the analysis in Afshani and Cheng (2021) is tight for D = 2 , by presenting matching upper bounds for uniform random point sets. This shows either the existing upper bounds can be improved or to obtain better lower bounds a new fundamentally different input set needs to be constructed. [ABSTRACT FROM AUTHOR]

Stabbing Planes (also known as Branch and Cut) is a proof system introduced very recently which, informally speaking, extends the DPLL method by branching on integer linear inequalities instead of single variables. The techniques known so far to prove size and depth lower bounds for Stabbing Planes are generalizations of those used for the Cutting Planes proof system. For size lower bounds these are established by monotone circuit arguments, while for depth these are found via communication complexity and protection. As such these bounds apply for lifted versions of combinatorial statements. Rank lower bounds for Cutting Planes are also obtained by geometric arguments called protection lemmas. In this work we introduce two new geometric approaches to prove size/depth lower bounds in Stabbing Planes working for any formula: (1) the antichain method, relying on Sperner's Theorem and (2) the covering method which uses results on essential coverings of the boolean cube by linear polynomials, which in turn relies on Alon's combinatorial Nullenstellensatz. We demonstrate their use on classes of combinatorial principles such as the Pigeonhole principle, the Tseitin contradictions and the Linear Ordering Principle. By the first method we prove almost linear size lower bounds and optimal logarithmic depth lower bounds for the Pigeonhole principle and analogous lower bounds for the Tseitin contradictions over the complete graph and for the Linear Ordering Principle. By the covering method we obtain a superlinear size lower bound and a logarithmic depth lower bound for Stabbing Planes proof of Tseitin contradictions over a grid graph. [ABSTRACT FROM AUTHOR]

Copyright of Journal of Xinjiang University (Natural Science Edition) is the property of Xinjiang University and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

Determining the best possible values of the parameters of a linear code is one of the most fundamental and challenging problems in coding theory. There exist databases of best-known linear codes (BKLC) over small finite fields. In this work, we establish a database of BKLC s over the field GF (17) together with upper bounds on the minimum distances for lengths up to 150 and dimensions up to 6. In the process, we have found many new linear codes over GF(17). [ABSTRACT FROM AUTHOR]

The article explores variants of partial order multiway search (POMS) problem that involves an interaction between an algorithm and an oracle, the classical, taciturn and external memory models. Topics discussed include graph theory around a single-rooted directed acyclic graph G with n nodes, an arbitrary heavy-path depth first search-tree T of G and ordering on the vertices of G determined by T, and algorithms whose performance matches the lower bounds to achieve the probing complexity.

QCDCL is one of the main algorithmic paradigms for solving quantified Boolean formulas (QBF). We design a new technique to show lower bounds for the running time in QCDCL algorithms. For this we model QCDCL by concisely defined proof systems and identify a new width measure for formulas, which we call gauge. We show that for a large class of QBFs, large (e.g. linear) gauge implies exponential lower bounds for QCDCL proof size. We illustrate our technique by computing the gauge for a number of sample QBFs, thereby providing new exponential lower bounds for QCDCL. Our technique is the first bespoke lower bound technique for QCDCL. [ABSTRACT FROM AUTHOR]

While it can be easily shown by counting that almost all Boolean predicates of n variables have circuit size Ω (2 n / n) , we have no example of an NP function requiring even a superlinear number of gates. Moreover, only modest linear lower bounds are known. Until recently, the strongest known lower bound was 3 n - o (n) presented by Blum in 1984. In 2011, Demenkov and Kulikov presented a much simpler proof of the same lower bound, but for a more complicated function —an affine disperser for sublinear dimension. Informally, this is a function that is resistant to any n - o (n) affine substitutions. In 2011, Ben-Sasson and Kopparty gave an explicit construction of such a function. The proof of the lower bound basically goes by showing that for any circuit there exists an affine hyperplane where the function complexity decreases at least by three gates. In this paper, we prove the following two extensions. 1. A (3 + 1 86 n - o (n) lower bound for the circuit size of an affine disperser for sublinear dimension. The proof is based on the gate elimination technique extended with the following three ideas: (i) generalizing the computational model by allowing circuits to contain cycles, this in turn allows us to perform affine substitutions, (ii) a carefully chosen circuit complexity measure to track the progress of the gate elimination process, and (iii) quadratic substitutions that may be viewed as delayed affine substitutions. 2. A much simpler proof of a stronger lower bound of 3.11 n for a quadratic disperser. Informally, a quadratic disperser is resistant to sufficiently many substitutions of the form x ← p , where p is a polynomial of degree at most two. Currently, there are no constructions of quadratic dispersers in NP (although there are constructions over large fields, and constructions with weaker parameters over GF(2)). The key ingredient of this proof is the induction on the size of the underlying quadratic variety instead of the number of variables as in the previously known proofs. [ABSTRACT FROM AUTHOR]

The permutation flow-shop scheduling problem is a classical problem in scheduling that aims at identifying the optimal sequence of jobs that should be processed in a number of machines in an effort to minimize makespan or some other performance criterion. The distributed permutation flow-shop scheduling problem adds multiple factories where copies of the machines exist and asks for minimizing the makespan on the longest-running location. In this paper, the problem is approached using Constraint Programming and its specialized scheduling features, such as interval variables and non-overlap constraints, while a novel heuristic is proposed for computing lower bounds. Two constraint programming models are proposed: one that solves the Distributed Permutation Flow-shop Scheduling problem, and another one that drops the constraint of processing jobs under the same order for all machines of each factory. The experiments use an extended public dataset of problem instances to validate the approach's effectiveness. In the process, optimality is proved for many problem instances known in the literature but has yet to be proven optimal. Moreover, a high speed of reaching optimal solutions is achieved for many problems, even with moderate big sizes (e.g., seven factories, 20 machines, and 20 jobs). The critical role that the number of jobs plays in the complexity of the problem is identified and discussed. In conclusion, this paper demonstrates the great benefits of scheduling problems that stem from using state-of-the-art constraint programming solvers and models that capture the problem tightly. [ABSTRACT FROM AUTHOR]

There are distributed graph algorithms for finding maximal matchings and maximal independent sets in O(Δ + log* n) communication rounds; here, n is the number of nodes and Δ is the maximum degree. The lower bound by Linial (1987, 1992) shows that the dependency on n is optimal: These problems cannot be solved in o(log* n) rounds even if Δ = 2. However, the dependency on Δ is a long-standing open question, and there is currently an exponential gap between the upper and lower bounds. We prove that the upper bounds are tight. We show that any algorithm that finds a maximal matching or maximal independent set with probability at least 1 - 1/n requires Ω(min{Δ, log logn/ log log logn}) rounds in the LOCAL model of distributed computing. As a corollary, it follows that any deterministic algorithm that finds a maximal matching or maximal independent set requires Ω(min{Δ, logn/ log logn}) rounds; this is an improvement over prior lower bounds also as a function of n. [ABSTRACT FROM AUTHOR]

The eigenvalues of complex q-Sturm–Liouville boundary value problems are the focus of this paper. The coefficients of the corresponding q-Sturm–Liouville equation provide the lower bounds on the real parts of all eigenvalues, and the real part of the eigenvalue and the coefficients of this q-Sturm–Liouville equation provide the bounds on the imaginary part of each eigenvalue.