Pages that link to "Item:Q4696224"
From MaRDI portal
The following pages link to The effect of random restrictions on formula size (Q4696224):
Displaying 27 items.
- An improved deterministic \#SAT algorithm for small De Morgan formulas (Q334923) (← links)
- A satisfiability algorithm and average-case hardness for formulas over the full binary basis (Q354655) (← links)
- Local restrictions from the Furst-Saxe-Sipser paper (Q519884) (← links)
- Improvements on Khrapchenko's theorem (Q685364) (← links)
- Negation-limited formulas (Q729897) (← links)
- An extension of Khrapchenko's theorem (Q753798) (← links)
- On convex complexity measures (Q964405) (← links)
- Size-depth tradeoffs for Boolean formulae (Q1318766) (← links)
- On the shrinkage exponent for read-once formulae (Q1367534) (← links)
- Toward the KRW composition conjecture: cubic formula lower bounds via communication complexity (Q1616616) (← links)
- Mining circuit lower bound proofs for meta-algorithms (Q2351392) (← links)
- Which formulae shrink under random restrictions? (Q2768368) (← links)
- $$P\mathop{ =}\limits^{?}NP$$ (Q2826803) (← links)
- Satisfiability Algorithms and Lower Bounds for Boolean Formulas over Finite Bases (Q2946392) (← links)
- Improved Average-Case Lower Bounds for De Morgan Formula Size: Matching Worst-Case Lower Bound (Q2963581) (← links)
- Toward Better Formula Lower Bounds: The Composition of a Function and a Universal Relation (Q2968148) (← links)
- Improved Algorithms for Sparse MAX-SAT and MAX-k-CSP (Q3453207) (← links)
- How Do Read-Once Formulae Shrink? (Q4325332) (← links)
- Shrinkage of de Morgan formulae under restriction (Q4696225) (← links)
- Improved boolean formulas for the Ramsey graphs (Q4845078) (← links)
- Tighter connections between Formula-SAT and shaving logs (Q5002674) (← links)
- Quantified Derandomization: How to Find Water in the Ocean (Q5060673) (← links)
- Cubic Formula Size Lower Bounds Based on Compositions with Majority (Q5090412) (← links)
- Algorithms and lower bounds for de morgan formulas of low-communication leaf gates (Q5092464) (← links)
- On the complexity of computing a random Boolean function over the reals (Q5140843) (← links)
- Natural proofs (Q5906823) (← links)
- Improving \(3N\) circuit complexity lower bounds (Q6184294) (← links)
