Skip to main content

Questions tagged [average-case-complexity]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
2 votes
0 answers
37 views

definition of P-samplable distribution that allows non-binary fractions

Arora and Barak (in chapter 18, on average-case complexity) define a polynomial-time samplable (or P-samplable) distribution $D$ (actually a family $\{D_n\}$, for each output length $n$) as having an ...
7 votes
0 answers
215 views

Relationships between Descriptive Complexity and Average Case Complexity

Descriptive complexity gives one a logic or at least a logic to express languages in a complexity class. The PH can be defined as the union of all classes that can be expressed in Second order logic. ...
9 votes
0 answers
392 views

Hard-on-Average, Quasi-Polynomial-Time Problems

In a paper by Raphael Pass, he writes (page 162): ... most natural problems that we believe are hard on average for polynomial time are also believed hard for quasi-polynomial time. In another post ...
2 votes
1 answer
101 views

Fine-grained average-case derandomization

Many believe derandomization with polynomial overhead, $\mathsf{P} = \mathsf{BPP}$, because it follows from $2^{\Omega(n)}$ circuit lower bounds for $\mathsf{E}$ (IW97). Do we have any evidence for or ...
3 votes
1 answer
971 views

Avarage classes for PP (probabilistic polynomial time) and PPT machines running in expected polytime

i have some question concerning the class PP and PPT machines. PP is defined as the class of problems $L$ for wich exist a probabilistic turing machine running in polytime with error probability < ...
4 votes
2 answers
519 views

NP-hard problem which is easy on average

I have a feeling like I read somewhere that the Hamiltonian circuit problem is NP-hard, but it is easy on average, or easy for a random instance. However, I cannot find a reference for that, nor an ...
6 votes
0 answers
293 views

Quantum computer versus Random 3-SAT?

It seems to be commonly believed that a quantum computer cannot efficiently solve NP-hard problems. What about problems that are challenging in the average-case, such as Planted Clique and Random 3-...
3 votes
0 answers
100 views

Worst to average case reductions for quantum complexity classes

I am studying worst to average case reductions for different complexity classes. Consider quantum complexity classes like QMA, QSZK, or QIP. Is it known or believed that these classes are amenable to ...
0 votes
1 answer
512 views

What are the worst-case and average-case time complexities of the greedy algorithm for the weighted set cover problem?

Let $X$ be the universe of elements, $F$ a collection of subsets $S \subseteq X$, each with an associated cost. The goal is to find a subcollection $C \subseteq F$ of minimum total cost which covers $...
1 vote
0 answers
162 views

Average case hardness of #SAT

Is there anything known about the average case hardness of #SAT? Let’s say over a uniform distribution. We know that in the worst case, it is #P-complete, but what can we say about an average ...
1 vote
0 answers
181 views

On planar $4$ regular graphs

It is $NP$-hard to decide if a $4$-regular planar graph can be $3$-colored. Is an exact algorithm possible that under uniform distribution is in average polynomial time?
7 votes
0 answers
135 views

Can relativization technique be applied to natural NP-complete languages?

Levin [1] defined distNP is the distributional problem (L,D), where L ∈ NP, and D is an ensemble of efficiently samplable distributions over problem instances. We say that a distNP problem (L,D) is ...
3 votes
0 answers
223 views

Fast way of getting a matrix of sums

We are given an array of variables $A$, along with a matrix $M$. The elements of the matrix $M$ are composed of sums of the variables in $A$. We are allowed to pre-process $A$ in order to find a ...
16 votes
2 answers
5k views

What is worst case complexity of number field sieve?

Given composite $N\in\Bbb N$ general number field sieve is best known factorization algorithm for integer factorization of $N$. It is a randomized algorithm and we get an expected complexity of $O\Big(...
5 votes
0 answers
170 views

Hard instances in Impagliazzo's Heuristica

In Impagliazzo's imaginary world Heuristica, P ≠ NP but all NP problems are easy on average for any samplable probability distribution. In Impagliazzo's paper, he implies that if you do manage to ...
1 vote
0 answers
69 views

Average case or beyond worse case analysis for non-convex optimization procedures?

I'm not sure if this is a well-formed question or not, but I thought I would ask to see if anyone is aware of related literature. It is known that global optimization of non-convex functions is NP-...
4 votes
0 answers
197 views

Worst-Case and Average-Case running-time equal with universal p-distribution with kolmogorov-complexity any applications of this theory?

at the moment I'm reading "Gems of Theoretical Computer Science" from Schöning and Pruim. In Chapter 8 the book defines a "universal probability distribution" in a way that the Average-Case running-...
5 votes
0 answers
111 views

Optimal polynomial time algorithm to determine if a random graph is $k$-colorable

Let $G(n, d/n)$ be an Erdos-Renyi graph with edge probablity $p = d/n$. For any fixed $k$ sufficiently large, it is known that $d_{k-col} \sim 2 k\log k$ is the sharp threshold for $G(n, d/n)$ to be $...
5 votes
1 answer
328 views

Average-case complexity open problems other than one-way functions

The list of unsolved problems in computer science on Wikipedia lists no problems in average-case complexity, except "Do one-way functions exist?" which is whether there is a polynomial time computable ...
5 votes
0 answers
88 views

Computational depth and p-time hard instances

After reading the nice results of the paper: "Worst-Case Running Times for Average-Case Algorithms" by Antunes and Fortnow, I was wondering about the existence of further results linking basic ...
6 votes
1 answer
2k views

The Average-case Complexity of Simplex Algorithm

I was wondering if there are any results on the average case complexity of the simplex algorithm. Let $A \in \mathbb{R}^{m \times n}$ be the matrix in the linear constraint. I know that Smale did ...
5 votes
2 answers
250 views

Popular average-case complexity assumptions

Except for planted clique and random 3SAT, what are the other commonly used average-case complexity assumptions?
-2 votes
1 answer
413 views

Are Graph and Group Isomorphism problems random self-reducible?

Are Graph and Group Isomorphism problems known to be random self-reducible? If so is there a good proof? Are there other non-trivial examples of random self-reducibility? Is there a good reference?
14 votes
4 answers
1k views

Are there any known NP problems which are conjectured to be exponentially hard on average?

ETH states that SAT cannot be solved in the worst case in subexponential time. What about average case? Are there natural problems in NP that are conjectured to be exponentially hard in the average ...
11 votes
2 answers
2k views

Worst case to average case reductions

Are there problems whose average case complexity is the same as their worst case complexity? What are the underlying properties of these problems that makes reducing the worst case to the average case ...
15 votes
0 answers
458 views

What is the evidence for average case separation between EXP and NEXP?

There is significant evidence from cryptography that there exist NP-complete problems that are hard in the average case (meaning that e.g. $AvgP \nsupseteq DistNP$). Namely, we have candidate one-way ...
9 votes
0 answers
514 views

Assigning probability to membership in an NP-complete language

Motivation Assuming $\mathsf{P}\ne\mathsf{NP}$, it is impossible to efficiently decide membership in an NP-complete language. I would like to assign probability to such membership, in some sense. ...
2 votes
0 answers
235 views

Height of randomly built binary search tree by insert and delete?

In Introduction to algorithm (CLRS), even in its third edition (published in 2009) it is noted in Sec 12.4 that little is known about height of randomly built binary search tree using insert and ...
8 votes
0 answers
637 views

A generalisation of one-wayness

$\mathbf{NP}$-complete problems are worst-case hard. Their average-case counterpart are one-way functions. Is there an analogous one-wayness notion for $\mathbf{coNP}$-complete problems? More ...
3 votes
0 answers
94 views

Closest Vector Problem with sparse basis and target vector

The Closest Vector Problem (and related problems) is random self-reducible and in general is NP-Hard, making it a useful tool in cryptography research and post-quantum public key crypto. For a variety ...
9 votes
0 answers
265 views

Are there sampNP-intermediate problems?

I approximately copied the brief "introduction" to average-case complexity theory of NP from my previous question. However, this question is completely different, so please read on It is conjectured ...
5 votes
0 answers
242 views

Non-uniform average-case complexity of NP

It is conjectured that NP-complete problems are hard not only in the worst case but also in the typical case. Formally, given a language $S \in \lbrace 0,1 \rbrace^*$ and for each $n$ a probability ...
11 votes
2 answers
405 views

Variants of direct product theorems

A direct product theorem, informally, says that computing $k$ instances of a function $f$ is harder than computing $f$ once. Typical direct product theorems (e.g., Yao's XOR Lemma) look at average-...
10 votes
1 answer
379 views

Reducing factoring prime products to factoring integer products (in average-case)

My question is about the equivalence of the security of various candidate one-way functions that can be constructed based on the hardness of factoring. Assuming the problem of FACTORING:[Given $N ...
16 votes
2 answers
514 views

Paradigms for complexity analysis of algorithms

Worst-case and average case analysis are well-known measures for the complexity of an algorithm. Recently smoothed analysis has emerged as another paradigm to explain why some algorithms which are ...
6 votes
1 answer
363 views

Average-case analysis of algorithms using the incompressibility method

I recently became very interested in Kolmogorov complexity and the incompressibility method especially in the context of average-case analysis. The "standard" book by Li & Vitanyi showcases many ...
11 votes
1 answer
1k views

Non-Uniform vs. Uniform Adversaries

This question arose in the context of cryptography, but below I will present it in terms of complexity theory, since people here are more acquainted with the latter. This question is related to ...
11 votes
1 answer
575 views

Average-case space complexity

I am trying to find problems whose average-case space complexity has been analyzed. More specifically, I am interested to know if there are any problems with a proven space complexity lower bound ...
20 votes
1 answer
732 views

Problems in NP but not in Average-P/poly

The Karp–Lipton Theoem states that if $\mathsf{NP} \subset \mathsf{P/poly}$, then $\mathsf{PH}$ collapses to $\mathsf{\Sigma^P_2}$. Therefore, assuming separations between $\mathsf{\Sigma^P_2}$ and $\...
37 votes
2 answers
6k views

Status of Impagliazzo's Worlds?

In 1995, Russell Impagliazzo proposed five complexity worlds: 1- Algorithmica: $P=NP$ with all the amazing consequences. 2- Heuristica: $NP$-complete problems are hard in the worst-case ($P \ne NP$) ...
8 votes
1 answer
1k views

NP-Complete Hard-on-Average Problems

This question considers a special class of problems in (NP,P-samplable). The question is: Do there exists a problem $(L,\mu) \in \mbox{(NP,P-samplable)}$ such that: $L$ is $\rm{NP}$-complete, and $L$...