# Twtxt is an open, distributed microblogging platform that
# uses human-readable text files, common transport protocols,
# and free software.
#
# Learn more about twtxt at https://github.com/buckket/twtxt
#
# This is an automated Yarn.social feed running feeds v0.1.0@72e53a9
# Learn more about Yarn.social at https://yarn.social
#
# nick = eccc-reports
# url = https://feeds.twtxt.net/eccc-reports/twtxt.txt
# type = rss
# source = https://eccc.weizmann.ac.il/feeds/reports
# avatar =
# description = Latest Reports published at https://eccc.weizmann.ac.il
# updated_at = 2024-09-12T09:04:31Z
#
2024-08-09T02:35:01Z **TR24-127 | Anti-Concentration for the Unitary Haar Measure and Applications to Random Quantum Circuits |
Bill Fefferman,
Soumik Ghosh,
Wei Zhan**
We prove a Carbery-Wright style anti-concentration inequality for the unitary Haar measure, by showing that the probability of a polynomial in the entries of a random unitary falling into an $\\varepsilon$ range is at most a polynomial in $\\varepsilon$. Using it, we show that the scrambling speed of a random quantum circuit is lower bounded: Namely, every input qubit has ... ⌘ [Read more](https://eccc.weizmann.ac.il/report/2024/127)
2024-08-04T05:55:45Z **TR24-126 | On the Complexity of Some Restricted Variants of Quotient Pigeon and a Weaker Variant of König |
Takashi Ishizuka**
One of the most famous TFNP subclasses is PPP, which is the set of all search problems whose totality is guaranteed by the pigeonhole principle. The author's recent preprint [ECCC TR24-002 2024] has introduced a TFNP problem related to the pigeonhole principle over a quotient set, called Quotient Pigeon, and shown that the problem Quotient Pigeon is not only PPP-hard but also PLS-hard. In this pap ... ⌘ [Read more](https://eccc.weizmann.ac.il/report/2024/126)
2024-07-28T09:36:42Z **TR24-125 | On read-$k$ projections of the determinant |
Pavel Hrubes,
Pushkar Joglekar**
We consider read-$k$ determinantal representations of polynomials and prove some non-expressibility results. A square matrix $M$ whose entries are variables or field elements will be called \\emph{read-$k$}, if every variable occurs at most $k$ times in $M$. It will be called a \\emph{determinantal representation} of a polynomial $f$ if $f=\\det(M)$. We show that
\\begin{itemize}
\\item the $n \\times n$ permanent polynomial does n ... ⌘ [Read more](https://eccc.weizmann.ac.il/report/2024/125)
2024-07-26T08:16:21Z **TR24-124 | Solving Tree Evaluation in $o(\log n \cdot \log\log n)$ space |
Oded Goldreich**
The input to the Tree Evaluation problem is a binary tree of height $h$ in which each internal vertex is associated with a function mapping pairs of $\\ell$-bit strings to $\\ell$-bit strings,and each leaf is assigned an $\\ell$-bit string.
The desired output is the value of the root, where the value of each internal node is defined by applying the corresponding function to the value of its children.
A recent result of Cook and Me ... ⌘ [Read more](https://eccc.weizmann.ac.il/report/2024/124)
2024-07-22T13:24:44Z **TR24-123 | Faster & Deterministic FPT Algorithm for Worst-Case Tensor Decomposition |
Vishwas Bhargava,
Devansh Shringi**
We present a deterministic $2^{k^{\\mathcal{O}(1)}} \\text{poly}(n,d)$ time algorithm for decomposing $d$-dimensional, width-$n$ tensors of rank at most $k$ over $\\mathbb{R}$ and $\\mathbb{C}$. This improves upon the previous randomized algorithm of Peleg, Shpilka, and Volk (ITCS '24) that takes $2^{k^{k^{\\mathcal{O}(k)}}} \\text{poly}(n,d)$ time and the deterministic $n^{k^k}$ time algorithms ... ⌘ [Read more](https://eccc.weizmann.ac.il/report/2024/123)
2024-07-21T03:37:15Z **TR24-122 | A high dimensional Cramer's rule connecting homogeneous multilinear equations to hyperdeterminants |
Anand Kumar Narayanan,
Antoine Joux**
We present a new algorithm for solving homogeneous multilinear equations, which are high dimensional generalisations of solving homogeneous linear equations. First, we present a linear time reduction from solving generic homogeneous multilinear equations to computing hyperdeterminants, via a high dimensional Cramer's rule. Hyperdeterminants are generalisations of dete ... ⌘ [Read more](https://eccc.weizmann.ac.il/report/2024/122)
2024-07-16T16:40:04Z **TR24-121 | Approximating the Number of Relevant Variables in a Parity Implies Proper Learning |
Nader Bshouty**
Consider the model where we can access a parity function through random uniform labeled examples in the presence of random classification noise. In this paper, we show that approximating the number of relevant variables in the parity function is as hard as properly learning parities.
More specifically, let $\\gamma:{\\mathbb R}^+\\to {\\mathbb R}^+$, where $\\gamma(x) \\ge x$, be any strictly increasing functio ... ⌘ [Read more](https://eccc.weizmann.ac.il/report/2024/121)
2024-07-15T04:08:32Z **TR24-120 | Consequences of Randomized Reductions from SAT to Time-Bounded Kolmogorov Complexity |
Valentine Kabanets,
Halley Goldberg**
A central open question within meta-complexity is that of NP-hardness of problems such as MCSP and MK$^t$P. Despite a large body of work giving consequences of and barriers for NP-hardness of these problems under (restricted) deterministic reductions, very little is known in the setting of randomized reductions. In this work, we give consequences of randomized NP-hardness reductions f ... ⌘ [Read more](https://eccc.weizmann.ac.il/report/2024/120)
2024-07-14T10:30:44Z **TR24-119 | Explicit Commutative ROABPs from Partial Derivatives |
Vishwas Bhargava,
Anamay Tengse**
The dimension of partial derivatives (Nisan and Wigderson, 1997) is a popular measure for proving lower bounds in algebraic complexity. It is used to give strong lower bounds on the Waring decomposition of polynomials (called Waring rank). This naturally leads to an interesting open question: does this measure essentially characterize the Waring rank of any polynomial?
The well-studied model of Read-once Oblivious ABPs ... ⌘ [Read more](https://eccc.weizmann.ac.il/report/2024/119)
2024-07-14T08:38:35Z **TR24-118 | The Expander Hitting Property When the Sets Are Arbitrarily Unbalanced |
Ron Zadiario,
Amnon Ta-Shma**
Numerous works have studied the probability that a length $t-1$ random walk on an expander is confined to a given rectangle $S\_1 \\times \\ldots \\times S\_t$, providing both upper and lower bounds for this probability.
However, when the densities of the sets $S\_i$ may depend on the walk length (e.g., when all set are equal and the density is $1-1/t$), the currently best known upper and lower bounds are v ... ⌘ [Read more](https://eccc.weizmann.ac.il/report/2024/118)
2024-08-27T15:39:22Z **TR24-128 | Lifting to regular resolution over parities via games |
Dmitry Itsykson,
Yaroslav Alekseev**
The propositional proof system resolution over parities (Res($\\oplus$)) combines resolution and the linear algebra over GF(2). It is a challenging open question to prove a superpolynomial lower bound on the proof size in this system. For many years, superpolynomial lower bounds were known only in tree-like cases. Recently, Efremenko, Garlik, and Itsykson [EGI, STOC 2024] proved an exponential lower bound for regular ... ⌘ [Read more](https://eccc.weizmann.ac.il/report/2024/128)
2024-08-27T19:38:26Z **TR24-129 | On Approximability of Satisfiable k-CSPs: V |
Amey Bhangale,
Subhash Khot,
Dor Minzer**
We propose a framework of algorithm vs. hardness for all Max-CSPs and demonstrate it for a large class of predicates. This framework extends the work of Raghavendra [STOC, 2008], who showed a similar result for almost satisfiable Max-CSPs.
Our framework is based on a new hybrid approximation algorithm, which uses a combination of the Gaussian elimination technique (i.e., solving a system of linear equations over an Ab ... ⌘ [Read more](https://eccc.weizmann.ac.il/report/2024/129)
2024-08-30T11:00:10Z **TR24-130 | Improved Circuit Lower Bounds With Applications to Exponential Separations Between Quantum and Classical Circuits |
Sabee Grewal,
Vinayak Kumar**
Kumar (CCC, 2023) used a novel switching lemma to prove exponential-size lower bounds for a circuit class $GC^0$ that not only contains $AC^0$ but can---with a single gate---compute functions that require exponential-size $TC^0$ circuits. Their main result was that switching-lemma lower bounds for $AC^0$ lift to $GC^0$ with no loss in parameters, even though $GC^0$ ... ⌘ [Read more](https://eccc.weizmann.ac.il/report/2024/130)
2024-09-05T15:03:09Z **TR24-131 | Emulating Computationally Sound Public-Coin IPPs in the Pre-Coordinated Model |
Hadar Strauss**
Interactive proofs of proximity (IPPs) for a property are relaxed proof systems analogous to property testers in which the goal is for the verifier to be convinced to accept inputs that are in the property, and to not be fooled into accepting inputs that are far from the property.
The general definition of IPPs allows the verifier to fully coordinate its interaction with the prover and its queries to the input oracl ... ⌘ [Read more](https://eccc.weizmann.ac.il/report/2024/131)
2024-09-06T18:57:56Z **TR24-132 | Super-critical Trade-offs in Resolution over Parities Via Lifting |
Arkadev Chattopadhyay,
Pavel Dvorak**
Razborov [J. ACM, 2016] exhibited the following surprisingly strong trade-off phenomenon in propositional proof complexity: for a parameter $k = k(n)$, there exists $k$-CNF formulas over $n$ variables, having resolution refutations of $O(k)$ width, but every tree-like refutation of width $n^{1-\\epsilon}/k$ needs size $\\text{exp}\\big(n^{\\Omega(k)}\\big)$. We extend this result to tree-like Resolution ... ⌘ [Read more](https://eccc.weizmann.ac.il/report/2024/132)
2024-09-06T23:57:00Z **TR24-133 | Two-Sided Lossless Expanders in the Unbalanced Setting |
Eshan Chattopadhyay,
Mohit Gurumukhani,
Noam Ringach,
Yunya Zhao**
We present the first explicit construction of two-sided lossless expanders in the unbalanced setting (bipartite graphs that have many more nodes on the left than on the right). Prior to our work, all known explicit constructions in the unbalanced setting achieved only one-sided lossless expansion.
Specifically, we show that the one-sided lossless expanders constructed by Kalev a ... ⌘ [Read more](https://eccc.weizmann.ac.il/report/2024/133)
2024-09-08T11:15:35Z **TR24-136 | One-Way Functions and pKt Complexity |
Shuichi Hirahara,
Zhenjian Lu,
Igor Oliveira**
We introduce $\\mathrm{pKt}$ complexity, a new notion of time-bounded Kolmogorov complexity that can be seen as a probabilistic analogue of Levin's $\\mathrm{Kt}$ complexity. Using $\\mathrm{pKt}$ complexity, we upgrade two recent frameworks that characterize one-way functions ($\\mathrm{OWFs}$) via symmetry of information and meta-complexity, respectively. Among other contributions, we establish the following results:
... ⌘ [Read more](https://eccc.weizmann.ac.il/report/2024/136)
2024-09-09T21:05:56Z **TR24-137 | Implications of Better PRGs for Permutation Branching Programs |
Dean Doron,
William Hoza**
We study the challenge of derandomizing constant-width standard-order read-once branching programs (ROBPs). Let $c \\in [1, 2)$ be any constant. We prove that if there are explicit pseudorandom generators (PRGs) for width-$6$ length-$n$ permutation ROBPs with error $1/n$ and seed length $\\widetilde{O}(\\log^c n)$, then there are explicit hitting set generators (HSGs) for width-$4$ length-$n$ ROBPs with threshold $1/\ ... ⌘ [Read more](https://eccc.weizmann.ac.il/report/2024/137)
2024-09-10T20:01:02Z **TR24-138 | Fully Characterizing Lossy Catalytic Computation |
Marten Folkertsma,
Ian Mertz,
Florian Speelman,
Quinten Tupker**
A catalytic machine is a model of computation where a traditional space-bounded machine is augmented with an additional, significantly larger, "catalytic" tape, which, while being available as a work tape, has the caveat of being initialized with an arbitrary string, which must be preserved at the end of the computation. Despite this restriction, catalytic machines have been shown to have ... ⌘ [Read more](https://eccc.weizmann.ac.il/report/2024/138)
2024-09-11T17:57:39Z **TR24-139 | Distinguishing, Predicting, and Certifying: On the Long Reach of Partial Notions of Pseudorandomness |
Jiatu Li,
Edward Pyne,
Roei Tell**
This paper revisits the study of two classical technical tools in theoretical computer science: Yao's transformation of distinguishers to next-bit predictors (FOCS 1982), and the \`\`reconstruction paradigm'' in pseudorandomness (e.g., as in Nisan and Wigderson, JCSS 1994). Recent works of Pyne, Raz, and Zhan (FOCS 2023) and Doron, Pyne, and Tell (STOC 2024) showed that ... ⌘ [Read more](https://eccc.weizmann.ac.il/report/2024/139)
2024-09-11T21:41:05Z **TR24-140 | Almost-catalytic Computation |
Sagar Bisoyi,
Krishnamoorthy Dinesh,
Bhabya Rai,
Jayalal Sarma**
Designing algorithms for space bounded models with restoration requirements on (most of) the space used by the algorithm is an important challenge posed about the catalytic computation model introduced by Buhrman et al (2014). Motivated by the scenarios where we do not need to restore unless $w$ is "useful", we relax the restoration requirement: only when the content of the catalytic tape is $w \\in A \\subs ... ⌘ [Read more](https://eccc.weizmann.ac.il/report/2024/140)
2024-09-12T08:38:27Z **TR24-141 | Public Coin Interactive Proofs for Label-Invariant Distribution Properties |
Tal Herman**
Assume we are given sample access to an unknown distribution $D$ over a large domain $[N]$. An emerging line of work has demonstrated that many basic quantities relating to the distribution, such as its distance from uniform and its Shannon entropy, despite being hard to approximate through the samples only, can be {\\em efficiently and verifiably} approximated through interaction with an untrusted powerful prover, that {\ ... ⌘ [Read more](https://eccc.weizmann.ac.il/report/2024/141)