Search Results

We show that any product-depth Δ algebraic circuit for the Iterated Matrix Multiplication polynomial IMM_{n, d} (when d = O(log n/log log n) must be of size at least \(n^{\Omega (d^{1/(\varphi ^2)^{\Delta }})}\), where φ = 1.618 … is the golden ratio. This ...

We consider the proof system Res \((\oplus)\) introduced by Itsykson and Sokolov (Ann. Pure Appl. Log.’20), which is an extension of the resolution proof system and operates with disjunctions of linear equations over \({\mathbb {F}}_2\).

We study ...

The monotone minimal perfect hash function (MMPHF) problem is the following indexing problem. Given a set \(S=\{s_{1},\ldots,s_{n}\}\) of \(n\) distinct keys from a universe \(U\) of size \(u\), create a data structure \(\text{D}\) that answers ...

In this work, we study the complexity of fundamental distributed graph problems in the recently popular setting where information about the input graph is available to the nodes before the start of the computation. We focus on the most common such ...

Recently, Akbari et al. (ICALP 2023) studied the locality of graph problems in distributed, sequential, dynamic, and online settings from a unified point of view. They designed a novel O(log n)-locality deterministic algorithm for proper 3-coloring ...

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 r^k, cannot be done in much less than \(r^{\lceil k/2 \rceil }\) time. However, in the dense regime of ...

The proof system resolution over parities (Res(⊕)) operates with disjunctions of linear equations (linear clauses) over GF(2); it extends the resolution proof system by incorporating linear algebra over GF(2). Over the years, several exponential lower ...

Strong algebraic proof systems such as IPS (Ideal Proof System; Grochow-Pitassi ‍[J. ‍ACM, 65(6):37:1–55, 2018]) offer a general model for deriving polynomials in an ideal and refuting unsatisfiable propositional formulas, subsuming most standard ...

The majority of established algorithms have polynomial, exponential, or factorial runtime complexities. Examples of problems that admit tight double or even triple exponential bounds on computational complexity are relatively rare. The ...$\mathcal{}{\mathrm{}}^{{\mathrm{}}^{}}{}^{\mathrm{}}$$$${\mathrm{}}_{\mathrm{}}^{}$${\mathrm{}}_{\mathrm{}}^{}$

We prove the first genuine quantified Boolean formula (QBF) proof size lower bounds for the proof system Merge Resolution (MRes), a refutational proof system for prenex QBFs with a CNF matrix. Unlike most QBF resolution systems in the literature, proofs ...

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/p^1/ρ*) — measured in the ...

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 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-...

Private Simultaneous Messages (PSM) is a minimal model of secure computation, where the input players with shared randomness send messages to the output player simultaneously and only once. In this field, finding upper and lower bounds on ...$\mathrm{}{}_{\mathrm{}}\mathrm{}$$\mathrm{}{}_{\mathrm{}}\mathrm{}$

While it can be easily shown by counting that almost all Boolean predicates of n variables have circuit size $\mathrm{\Omega }(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 ...$\mathrm{}$$$

In secure multiparty computation (MPC), the goal is to allow a set of mutually distrustful parties to compute some function of their private inputs in a way that preserves security properties, even in the face of adversarial behavior by some of ...

Partial order multiway search (POMS) is a fundamental problem that finds applications in crowdsourcing, distributed file systems, software testing, and more. This problem involves an interaction between an algorithm 𝒜 and an oracle, conducted on a ...

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 first-order sentence but where every ...

The Tensor Isomorphism problem (TI) has recently emerged as having connections to multiple areas of research within complexity and beyond, but the current best upper bound is essentially the brute force algorithm. Being an algebraic problem, TI (or ...

Recent work has shown that many of the standard TFNP classes - such as PLS, PPADS, PPAD, SOPL, and EOPL - have corresponding proof systems in propositional proof complexity, in the sense that a total search problem is in the class if and only if the ...