[HTML][HTML] In search of an easy witness: Exponential time vs. probabilistic polynomial time
R Impagliazzo, V Kabanets, A Wigderson - Journal of Computer and …, 2002 - Elsevier
Restricting the search space {0, 1} n to the set of truth tables of “easy” Boolean functions on
log n variables, as well as using some known hardness–randomness tradeoffs, we establish …
log n variables, as well as using some known hardness–randomness tradeoffs, we establish …
On the computational intractability of exact and approximate dictionary learning
AM Tillmann - IEEE Signal Processing Letters, 2014 - ieeexplore.ieee.org
The efficient sparse coding and reconstruction of signal vectors via linear observations has
received a tremendous amount of attention over the last decade. In this context, the …
received a tremendous amount of attention over the last decade. In this context, the …
The complexity of manipulative attacks in nearly single-peaked electorates
P Faliszewski, E Hemaspaandra… - Proceedings of the 13th …, 2011 - dl.acm.org
Many electoral bribery, control, and manipulation problems (which we will refer to in general
as" manipulative actions" problems) are NP-hard in the general case. It has recently been …
as" manipulative actions" problems) are NP-hard in the general case. It has recently been …
Conspiracies between learning algorithms, circuit lower bounds and pseudorandomness
IC Oliveira, R Santhanam - arXiv preprint arXiv:1611.01190, 2016 - arxiv.org
We prove several results giving new and stronger connections between learning, circuit
lower bounds and pseudorandomness. Among other results, we show a generic learning …
lower bounds and pseudorandomness. Among other results, we show a generic learning …
Non-disjoint promise problems from meta-computational view of pseudorandom generator constructions
S Hirahara - 35th Computational Complexity Conference (CCC …, 2020 - drops.dagstuhl.de
The standard notion of promise problem is a pair of disjoint sets of instances, each of which
is regarded as Yes and No instances, respectively, and the task of solving a promise …
is regarded as Yes and No instances, respectively, and the task of solving a promise …
Geometric complexity theory V: Equivalence between blackbox derandomization of polynomial identity testing and derandomization of Noether's normalization lemma
KD Mulmuley - 2012 IEEE 53rd Annual Symposium on …, 2012 - ieeexplore.ieee.org
It is shown that black-box derandomization of polynomial identity testing (PIT) is essentially
equivalent to derandomization of Noether's Normalization Lemma for explicit algebraic …
equivalent to derandomization of Noether's Normalization Lemma for explicit algebraic …
Expressivity of planning with horn description logic ontologies
State constraints in AI Planning globally restrict the legal environment states. Standard
planning languages make closed-domain and closed-world assumptions. Here we address …
planning languages make closed-domain and closed-world assumptions. Here we address …
The power of natural properties as oracles
We study the power of randomized complexity classes that are given oracle access to a
natural property of Razborov and Rudich (JCSS, 1997) or its special case, the Minimal …
natural property of Razborov and Rudich (JCSS, 1997) or its special case, the Minimal …
Relations and equivalences between circuit lower bounds and Karp-Lipton theorems
A frontier open problem in circuit complexity is to prove P^{NP} is not in SIZE [n^ k] for all k;
this is a necessary intermediate step towards NP is not in P_ {/poly}. Previously, for several …
this is a necessary intermediate step towards NP is not in P_ {/poly}. Previously, for several …
The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory
We continue an investigation into resource-bounded Kolmogorov complexity (Allender et al.,
2006 [4]), which highlights the close connections between circuit complexity and Levin's time …
2006 [4]), which highlights the close connections between circuit complexity and Levin's time …