A - B - C - D - E - F - G - H - I - J - K - L - M - N - O - P - Q - R - S - T - U - V - W - X - Y - Z - Other

**W**

__
TR03-024
| 25th February 2003
__

Till Tantau#### Weak Cardinality Theorems for First-Order Logic

__
TR05-047
| 10th April 2005
__

Kooshiar Azimian, Mahmoud Salmasizadeh, Javad Mohajeri#### Weak Composite Diffie-Hellman is not Weaker than Factoring

__
TR11-072
| 1st May 2011
__

Danny Hermelin, Xi Wu#### Weak Compositions and Their Applications to Polynomial Lower-Bounds for Kernelization

Revisions: 1

__
TR10-005
| 3rd January 2010
__

Haitao Jiang, Binhai Zhu#### Weak Kernels

Revisions: 7

__
TR13-164
| 28th November 2013
__

Scott Aaronson, Andris Ambainis, Kaspars Balodis, Mohammad Bavarian#### Weak Parity

__
TR97-011
| 7th April 1997
__

Alexander E. Andreev, Andrea E. F. Clementi, Jose' D.P. Rolim and Trevisan#### Weak Random Sources, Hitting Sets, and BPP Simulations

__
TR15-170
| 26th October 2015
__

Alexander Golovnev, Alexander Kulikov#### Weighted gate elimination: Boolean dispersers for quadratic varieties imply improved circuit lower bounds

__
TR14-166
| 8th December 2014
__

Mark Bun, Thomas Steinke#### Weighted Polynomial Approximations: Limits for Learning and Pseudorandomness

__
TR23-114
| 8th August 2023
__

Lijie Chen, William Hoza, Xin Lyu, Avishay Tal, Hongxun Wu#### Weighted Pseudorandom Generators via Inverse Analysis of Random Walks and Shortcutting

__
TR17-083
| 5th May 2017
__

Arkadev Chattopadhyay, Nikhil Mande#### Weights at the Bottom Matter When the Top is Heavy

Revisions: 1

__
TR13-095
| 24th June 2013
__

Uriel Feige, Rani Izsak#### Welfare Maximization and the Supermodular Degree

__
TR15-054
| 7th April 2015
__

Noga Alon, Noam Nisan, Ran Raz, Omri Weinstein#### Welfare Maximization with Limited Interaction

__
TR04-044
| 1st June 2004
__

Eric Allender, Harry Buhrman, Michal Koucky#### What Can be Efficiently Reduced to the Kolmogorov-Random Strings?

__
TR22-057
| 25th April 2022
__

Lijie Chen, Roei Tell#### When Arthur has Neither Random Coins nor Time to Spare: Superfast Derandomization of Proof Systems

Revisions: 2

__
TR01-084
| 1st October 2001
__

Gerhard J. Woeginger#### When does a dynamic programming formulation guarantee the existence of an FPTAS?

__
TR06-065
| 24th May 2006
__

Jan Arpe, Rüdiger Reischuk#### When Does Greedy Learning of Relevant Features Succeed? --- A Fourier-based Characterization ---

__
TR18-002
| 31st December 2017
__

Constantinos Daskalakis, Gautam Kamath, John Wright#### Which Distribution Distances are Sublinearly Testable?

__
TR07-065
| 13th July 2007
__

Jonathan Katz#### Which Languages Have 4-Round Zero-Knowledge Proofs?

__
TR17-015
| 4th February 2017
__

Ilan Komargodski, Moni Naor, Eylon Yogev#### White-Box vs. Black-Box Complexity of Search Problems: Ramsey and Graph Property Testing

Revisions: 2

__
TR11-108
| 8th August 2011
__

Scott Aaronson#### Why Philosophers Should Care About Computational Complexity

Revisions: 2

__
TR15-159
| 28th September 2015
__

Juraj Hromkovic#### Why the Concept of Computational Complexity is Hard for Verifiable Mathematics

__
TR15-048
| 14th February 2015
__

Kamil Khadiev#### Width Hierarchy for $k$-OBDD of Small Width

Revisions: 1

__
TR06-092
| 5th July 2006
__

Matthias Englert, Heiko Röglin, Berthold Vöcking#### Worst Case and Probabilistic Analysis of the 2-Opt Algorithm for the TSP

__
TR08-072
| 11th August 2008
__

Shachar Lovett, Tali Kaufman#### Worst case to Average case reductions for polynomials

__
TR18-056
| 20th March 2018
__

Zvika Brakerski, Vadim Lyubashevsky, Vinod Vaikuntanathan, Daniel Wichs#### Worst-Case Hardness for LPN and Cryptographic Hashing via Code Smoothing

__
TR00-019
| 20th March 2000
__

Edward Hirsch#### Worst-case time bounds for MAX-k-SAT w.r.t. the number of variables using local search

__
TR18-090
| 4th May 2018
__

Eli Ben-Sasson, Swastik Kopparty, Shubhangi Saraf#### Worst-case to average case reductions for the distance to a code

Revisions: 1

__
TR24-077
| 19th April 2024
__

Divesh Aggarwal, JinMing Leong, Alexandra Veliche#### Worst-Case to Average-Case Hardness of LWE: A Simple and Practical Perspective

Revisions: 1

__
TR17-130
| 30th August 2017
__

Oded Goldreich, Guy Rothblum#### Worst-case to Average-case reductions for subclasses of P

Revisions: 4

__
TR22-020
| 18th February 2022
__

Vahid Reza Asadi, Alexander Golovnev, Tom Gur, Igor Shinkar#### Worst-Case to Average-Case Reductions via Additive Combinatorics

Till Tantau

Kummer's cardinality theorem states that a language is recursive

if a Turing machine can exclude for any n words one of the

n + 1 possibilities for the number of words in the language. It

is known that this theorem does not hold for polynomial-time

computations, but there ...
more >>>

Kooshiar Azimian, Mahmoud Salmasizadeh, Javad Mohajeri

In1985, Shmuley proposed a theorem about intractability of Composite Diffie-Hellman [Sh85]. The Theorem of Shmuley may be paraphrased as saying that if there exist a probabilistic poly-time oracle machine which solves the Diffie-Hellman modulo an

RSA-number with odd-order base then there exist a probabilistic algorithm which factors the modulo. ...
more >>>

Danny Hermelin, Xi Wu

We introduce a new form of composition called \emph{weak composition} that allows us to obtain polynomial kernelization lower-bounds for several natural parameterized problems. Let $d \ge 2$ be some constant and let $L_1, L_2 \subseteq \{0,1\}^* \times \N$ be two parameterized problems where the unparameterized version of $L_1$ is \NP-hard. ... more >>>

Haitao Jiang, Binhai Zhu

In this paper, we formalize a folklore concept and formally define

{\em weak kernels} for fixed-parameter computation. We show that a

problem has a (traditional) kernel then it also has a weak kernel.

It is unknown yet whether the converse is always true. On the other hand,

for a problem ...
more >>>

Scott Aaronson, Andris Ambainis, Kaspars Balodis, Mohammad Bavarian

We study the query complexity of Weak Parity: the problem of computing the parity of an n-bit input string, where one only has to succeed on a 1/2+eps fraction of input strings, but must do so with high probability on those inputs where one does succeed. It is well-known that ... more >>>

Alexander E. Andreev, Andrea E. F. Clementi, Jose' D.P. Rolim and Trevisan

We show how to simulate any BPP algorithm in polynomial time

using a weak random source of min-entropy $r^{\gamma}$

for any $\gamma >0$.

This follows from a more general result about {\em sampling\/}

with weak random sources.

Our result matches an information-theoretic lower bound ...
more >>>

Alexander Golovnev, Alexander Kulikov

In this paper we motivate the study of Boolean dispersers for quadratic varieties by showing that an explicit construction of such objects gives improved circuit lower bounds. An $(n,k,s)$-quadratic disperser is a function on $n$ variables that is not constant on any subset of $\mathbb{F}_2^n$ of size at least $s$ ... more >>>

Mark Bun, Thomas Steinke

Polynomial approximations to boolean functions have led to many positive results in computer science. In particular, polynomial approximations to the sign function underly algorithms for agnostically learning halfspaces, as well as pseudorandom generators for halfspaces. In this work, we investigate the limits of these techniques by proving inapproximability results for ... more >>>

Lijie Chen, William Hoza, Xin Lyu, Avishay Tal, Hongxun Wu

A weighted pseudorandom generator (WPRG) is a generalization of a pseudorandom generator (PRG) in which, roughly speaking, probabilities are replaced with weights that are permitted to be positive or negative. We present new explicit constructions of WPRGs that fool certain classes of standard-order read-once branching programs. In particular, our WPRGs ... more >>>

Arkadev Chattopadhyay, Nikhil Mande

Proving super-polynomial lower bounds against depth-2 threshold circuits of the form THR of THR is a well-known open problem that represents a frontier of our understanding in boolean circuit complexity. By contrast, exponential lower bounds on the size of THR of MAJ circuits were shown by Razborov and Sherstov (SIAM ... more >>>

Uriel Feige, Rani Izsak

Given a set of items and a collection of players, each with a nonnegative monotone valuation set function over the items,

the welfare maximization problem requires that every item be allocated to exactly one player,

and one wishes to maximize the sum of values obtained by the players,

as computed ...
more >>>

Noga Alon, Noam Nisan, Ran Raz, Omri Weinstein

We continue the study of welfare maximization in unit-demand (matching) markets, in a distributed information model

where agent's valuations are unknown to the central planner, and therefore communication is required to determine an

efficient allocation. Dobzinski, Nisan and Oren (STOC'14) showed that if the market size is $n$, ...
more >>>

Eric Allender, Harry Buhrman, Michal Koucky

We investigate the question of whether one can characterize complexity

classes (such as PSPACE or NEXP) in terms of efficient

reducibility to the set of Kolmogorov-random strings R_C.

We show that this question cannot be posed without explicitly dealing

with issues raised by the choice of universal

machine in the ...
more >>>

Lijie Chen, Roei Tell

What is the actual cost of derandomization? And can we get it for free? These questions were recently raised by Doron et. al (FOCS 2020) and have been attracting considerable interest. In this work we extend the study of these questions to the setting of *derandomizing interactive proofs systems*.

... more >>>Gerhard J. Woeginger

We derive results of the following flavor:

If a combinatorial optimization problem can be formulated via a dynamic

program of a certain structure and if the involved cost and transition

functions satisfy certain arithmetical and structural conditions, then

the optimization problem automatically possesses a fully polynomial time

approximation scheme (FPTAS).

Jan Arpe, Rüdiger Reischuk

Detecting the relevant attributes of an unknown target concept

is an important and well studied problem in algorithmic learning.

Simple greedy strategies have been proposed that seem to perform reasonably

well in practice if a sufficiently large random subset of examples of the target

concept is provided.

Introducing a ... more >>>

Constantinos Daskalakis, Gautam Kamath, John Wright

Given samples from an unknown distribution $p$ and a description of a distribution $q$, are $p$ and $q$ close or far? This question of "identity testing" has received significant attention in the case of testing whether $p$ and $q$ are equal or far in total variation distance. However, in recent ... more >>>

Jonathan Katz

We show that if a language $L$ has a 4-round, black-box, computational zero-knowledge proof system with negligible soundness error, then $\bar L \in MA$. Assuming the polynomial hierarchy does not collapse, this means, in particular, that $NP$-complete languages do not have 4-round zero-knowledge proofs (at least with respect to black-box ... more >>>

Ilan Komargodski, Moni Naor, Eylon Yogev

Ramsey theory assures us that in any graph there is a clique or independent set of a certain size, roughly logarithmic in the graph size. But how difficult is it to find the clique or independent set? If the graph is given explicitly, then it is possible to do so ... more >>>

Scott Aaronson

One might think that, once we know something is computable, how efficiently it can be computed is a practical question with little further philosophical importance. In this essay, I offer a detailed case that one would be wrong. In particular, I argue that computational complexity theory---the field that studies the ... more >>>

Juraj Hromkovic

Mathematics was developed as a strong research instrument with fully verifiable argumentations. We call any formal theory based on syntactic rules that enables to algorithmically verify for any given text whether it is a proof or not algorithmically verifiable mathematics (AV-mathematics for short). We say that a decision problem L ... more >>>

Kamil Khadiev

In this paper was explored well known model $k$-OBDD. There are proven width based hierarchy of classes of boolean functions which computed by $k$-OBDD. The proof of hierarchy is based on sufficient condition of Boolean function's non representation as $k$-OBDD and complexity properties of Boolean

function SAF. This function is ...
more >>>

Matthias Englert, Heiko Röglin, Berthold Vöcking

2-Opt is probably the most basic and widely used local search

heuristic for the TSP. This heuristic achieves amazingly good

results on "real world" Euclidean instances both with respect to

running time and approximation ratio. There are numerous

experimental studies on the performance of 2-Opt. However, the

theoretical knowledge about ...
more >>>

Shachar Lovett, Tali Kaufman

A degree-d polynomial p in n variables over a field F is equidistributed if it takes on each of its |F| values close to equally often, and biased otherwise. We say that p has low rank if it can be expressed as a function of a small number of lower ... more >>>

Zvika Brakerski, Vadim Lyubashevsky, Vinod Vaikuntanathan, Daniel Wichs

We present a worst case decoding problem whose hardness reduces to that of solving the Learning Parity with Noise (LPN) problem, in some parameter regime. Prior to this work, no worst case hardness result was known for LPN (as opposed to syntactically similar problems such as Learning with Errors). The ... more >>>

Edward Hirsch

During the past three years there was an explosion of algorithms

solving MAX-SAT and MAX-2-SAT in worst-case time of the order

c^K, where c<2 is a constant, and K is the number of clauses

in the input formula. Such bounds w.r.t. the number of variables

instead of the number of ...
more >>>

Eli Ben-Sasson, Swastik Kopparty, Shubhangi Saraf

Algebraic proof systems reduce computational problems to problems about estimating the distance of a sequence of functions $u=(u_1,\ldots, u_k)$, given as oracles, from a linear error correcting code $V$. The soundness of such systems relies on methods that act ``locally'' on $u$ and map it to a single function $u^*$ ... more >>>

Divesh Aggarwal, JinMing Leong, Alexandra Veliche

In this work, we study the worst-case to average-case hardness of the Learning with Errors problem (LWE) under an alternative measure of hardness - the maximum success probability achievable by a probabilistic polynomial-time (PPT) algorithm. Previous works by Regev (STOC 2005), Peikert (STOC 2009), and Brakerski, Peikert, Langlois, Regev, Stehle ... more >>>

Oded Goldreich, Guy Rothblum

For every polynomial $q$, we present worst-case to average-case (almost-linear-time) reductions for a class of problems in $\cal P$ that are widely conjectured not to be solvable in time $q$.

These classes contain, for example, the problems of counting the number of $k$-cliques in a graph, for any fixed $k\geq3$.

more >>>

Vahid Reza Asadi, Alexander Golovnev, Tom Gur, Igor Shinkar

We present a new framework for designing worst-case to average-case reductions. For a large class of problems, it provides an explicit transformation of algorithms running in time $T$ that are only correct on a small (subconstant) fraction of their inputs into algorithms running in time $\widetilde{O}(T)$ that are correct on ... more >>>