Pages that link to "Item:Q642463"
From MaRDI portal
The following pages link to Boolean function complexity. Advances and frontiers. (Q642463):
Displaying 50 items.
- Separating OR, SUM, and XOR circuits (Q269494) (← links)
- A note on the size of prenex normal forms (Q269710) (← links)
- On various nonlinearity measures for Boolean functions (Q276554) (← links)
- On the read-once property of branching programs and CNFs of bounded treewidth (Q309788) (← links)
- Zero-information protocols and unambiguity in Arthur-Merlin communication (Q343848) (← links)
- Cutting planes cannot approximate some integer programs (Q453048) (← links)
- Clique problem, cutting plane proofs and communication complexity (Q456115) (← links)
- Upper bounds for the formula size of symmetric Boolean functions (Q465106) (← links)
- Random arithmetic formulas can be reconstructed efficiently (Q488050) (← links)
- Lower bounds for tropical circuits and dynamic programs (Q493653) (← links)
- Limitations of incremental dynamic programming (Q517805) (← links)
- A quantum query algorithm for computing the degree of a perfect nonlinear Boolean function (Q669952) (← links)
- Negation-limited formulas (Q729897) (← links)
- Toward the KRW composition conjecture: cubic formula lower bounds via communication complexity (Q1616616) (← links)
- On the limits of gate elimination (Q1635510) (← links)
- The landscape of communication complexity classes (Q1653337) (← links)
- Upper bounds for the size and the depth of formulae for MOD-functions (Q1675519) (← links)
- Asymptotics of growth for non-monotone complexity of multi-valued logic function systems (Q1685402) (← links)
- Size-treewidth tradeoffs for circuits computing the element distinctness function (Q1702852) (← links)
- Multiplicative complexity of vector valued Boolean functions (Q1704580) (← links)
- The minimum number of negations in circuits for systems of multi-valued functions (Q1744290) (← links)
- On the CNF-complexity of bipartite graphs containing no squares (Q1936267) (← links)
- On the mystery of negations in circuits: structure vs power (Q2019505) (← links)
- Formula complexity of a linear function in a \(k\)-ary basis (Q2037681) (← links)
- Nondeterministic and randomized Boolean hierarchies in communication complexity (Q2041245) (← links)
- Counting the number of perfect matchings, and generalized decision trees (Q2044128) (← links)
- Bounded-depth Frege complexity of Tseitin formulas for all graphs (Q2084956) (← links)
- On the decision tree complexity of threshold functions (Q2095465) (← links)
- PAC-learning gains of Turing machines over circuits and neural networks (Q2111729) (← links)
- On separation between the degree of a Boolean function and the block sensitivity (Q2117108) (← links)
- Expander-based cryptography meets natural proofs (Q2125080) (← links)
- Improved bounds on the an-complexity of \(O(1)\)-linear functions (Q2159467) (← links)
- Quadratic lower bounds for algebraic branching programs and formulas (Q2159469) (← links)
- Skew circuits of small width (Q2173307) (← links)
- The function-inversion problem: barriers and opportunities (Q2175919) (← links)
- Power of uninitialized qubits in shallow quantum circuits (Q2220824) (← links)
- Exact value of the nonmonotone complexity of Boolean functions (Q2313604) (← links)
- Computing majority by constant depth majority circuits with low fan-in gates (Q2321926) (← links)
- Proving that \(\mathrm{prBPP}=\mathrm{prP}\) is as hard as proving that ``almost NP'' is not contained in P/poly (Q2328311) (← links)
- On the complexity of bounded-depth circuits and formulas over the basis of fan-in gates (Q2332856) (← links)
- A short proof that the extension complexity of the correlation polytope grows exponentially (Q2340413) (← links)
- Cancellation-free circuits in unbounded and bounded depth (Q2348031) (← links)
- Mining circuit lower bound proofs for meta-algorithms (Q2351392) (← links)
- On oblivious branching programs with bounded repetition that cannot efficiently compute CNFs of bounded treewidth (Q2408558) (← links)
- Bounds in ontology-based data access via circuit complexity (Q2411040) (← links)
- On compiling structured CNFs to OBDDs (Q2411046) (← links)
- Local bounds for the optimal information ratio of secret sharing schemes (Q2416938) (← links)
- Query-to-communication lifting for \(\mathsf{P}^{\mathsf{NP}}\) (Q2422767) (← links)
- The price of query rewriting in ontology-based data access (Q2453744) (← links)
- Alternation, sparsity and sensitivity: bounds and exponential gaps (Q2632012) (← links)
