As of May 31, 2023, we have updated our Code of Conduct.

# Questions tagged [upper-bounds]

The tag has no usage guidance.

70 questions
Filter by
Sorted by
Tagged with
11k views

### Best Upper Bounds on SAT

In another thread, Joe Fitzsimons asked about "the best current lower bounds on 3SAT." I'd like to go the other way: What's the best current upper bounds on 3SAT? In other words, what is the time ...
2k views

1k views

### Can addition be carried out in less than depth 5?

Using carry look ahead algorithm we can compute addition using a polynomial size depth 5 (or 4?) $AC^0$ circuit family. Is it possible to reduce the depth? Can we compute the addition of two binary ...
2k views

### What are the limits of computation in this universe?

I understand that Turing completeness requires unbounded memory and unbounded time. However there is a finite amount of atoms in this universe, thus making memory bounded. For example even though $\pi$...
1k views

### How large a treewidth can a tree plus half the edges have?

Let G be a tree on 2n vertices. The treewidth of G, tw(G) = 1. Now suppose we add n edges to G to get a graph H. An easy upper bound on tw(H) is n + 1. Is this essentially the best possible? It ...
526 views

### OR-circuit complexity of a dense linear operator

Consider the following simple monotone circuit model: each gate is just a binary OR. What is the complexity of a function $f(x)=Ax$ where $A$ is a Boolean $n \times n$ matrix with $O(n)$ 0's? Can it ...
209 views

### The best known upper bound for two-way probabilistic finite automata with one-counter

It is known that the class of languages recognized by two-way deterministic finite automata with one-counter (2D1CAs) is a proper subset of $\mathsf{L}$ (deterministic log-space): A 2D1CA can run at ...
948 views

### What is the proof of this nonstandard version of Azuma's inequality?

In Appendix B of Boosting and Differential Privacy by Dwork et al., the authors state the following result without proof and refer to it as Azuma's inequality: Let $C_1, \dots, C_k$ be real-valued ...
635 views

### Known upper bounds on the communication complexity of Karchmer-Wigderson games

In 1988 Karchmer and Wigderson established a nice characterization of the circuit depth $d$ (DeMorgan circuits) of a Boolean function $f \colon \{0,1\}^n\rightarrow\{0,1\}$: $d$ is exactly the number ...
820 views

### Are quasi-polynomial sized circuits for 3-SAT trivial?

Suppose we consider 3-SAT with $v$ variables and $c$ clauses. I am researching a method that appears to take $O(v^{2+\log c})$ time/space to solve any SAT problem fitting this description, to within ...
1k views

### What are the current best known upper and lower bounds on the (un)satisfiability threshold for random k-sat and/or 3-sat?

I would like to know the current state of the phase transition for random k-sat, given n variables and m clauses, what is the best known c=m/n for upper and lower bounds.
2k views

### Is Almost-2-SAT NP-hard?

Is a CNF SAT problem NP hard when the total number (but not the width) of the 3-or-more-term clauses is bounded above by a constant? What about specifically when there's only one such clause?
230 views

108 views

### How quickly can we perform base extension in a residue number system?

Thinking about residue number systems, one major operation is to extend the set of primes that a given value is modulated by, also known as base extension. For instance, a given number $N$ can be ...
151 views

### What's the upper bounds for #3-SAT circuits?

We have, from this thread on 3-SAT upper bounds, and this answer on #P that the current best upper bounds for 3-SAT is faster than $O(1.31)^n$, and approximately $O(1.64^n)$ for #3-SAT. Can we do ...
237 views

### Is there an Upper Bound on Number of Redundant Clauses in a satisfiable $3-SAT$?

For a non-empty $3-SAT$ with $n\geq3$ variables and $T\geq1$ non-identical non-degenerate clauses $C_i$: $$S=C_1 \wedge \ldots \wedge C_T$$ where a non-degenerate clause is one containing $3$ unique ...
298 views

### Best SAT upper bounds based on number of clauses

What's the best upper bounds based on number of clauses? In this question shown fastest algorithms for SAT, but there bounds depends from number of variables ( $O(const^n)$ where n is number of ...
317 views

1k views

### Is there a better than brute-force solution to the shortest simple path problem?

Given as input graph which can possibly contain negative weight cycles, we can still ask for the weight of the shortest simple path between two vertices (i.e., a path that does not visit any vertex ...