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 ...
Shivaram Lingamneni's user avatar
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. ...
user3483902's user avatar
  • 1,261
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 ...
Nicholas Brandt's user avatar
4 votes
2 answers
511 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 ...
Kolja's user avatar
  • 181
3 votes
0 answers
99 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 ...
AngryLion's user avatar
  • 173
0 votes
1 answer
504 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 $...
Frizzylicious's user avatar
1 vote
0 answers
161 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 ...
arika's user avatar
  • 11
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?
Turbo's user avatar
  • 12.9k
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 ...
user avatar
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 ...
Matt Groff's user avatar
  • 2,100
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 ...
Timothy Chow's user avatar
  • 7,550
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-...
Jake Shellman's user avatar
4 votes
0 answers
195 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-...
Senf's user avatar
  • 41
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 $...
Steve's user avatar
  • 451
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 ...
Saram Meti's user avatar
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 ...
Ramon Bejar Torres's user avatar
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 ...
Steve's user avatar
  • 451
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-...
Minkov's user avatar
  • 852
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?
Minkov's user avatar
  • 852
-2 votes
1 answer
412 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?
Turbo's user avatar
  • 12.9k
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(...
user avatar
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 ...
Vanessa's user avatar
  • 2,151
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. ...
Vanessa's user avatar
  • 2,151
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 ...
Bapi Chatterjee's user avatar
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 ...
Ross Snider's user avatar
  • 2,035
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 ...
Vanessa's user avatar
  • 2,151
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 ...
Vanessa's user avatar
  • 2,151
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 ...
Anonymous's user avatar
  • 4,041
11 votes
2 answers
404 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-...
user6584's user avatar
  • 1,242
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 ...
Anonymous's user avatar
  • 4,041
3 votes
1 answer
965 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 < ...
Paolo Parisen T.'s user avatar
10 votes
1 answer
378 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 ...
Omid Etesami's user avatar
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 ...
Opt's user avatar
  • 1,311
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 ...
Juho's user avatar
  • 3,170
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 ...
user4359's user avatar
  • 111
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 ...
Sadeq Dousti's user avatar
  • 16.5k
20 votes
1 answer
731 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 $\...
Sadeq Dousti's user avatar
  • 16.5k
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 ...
Sadeq Dousti's user avatar
  • 16.5k
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 ...
Pooya Farshim's user avatar
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$...
Sadeq Dousti's user avatar
  • 16.5k
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$) ...
Mohammad Al-Turkistany's user avatar