Publications by Artur Riazanov

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

Suppose we have a two-party communication protocol for f which allows the parties to make queries to an oracle computing g; for example, they may query an Equality oracle. To translate this protocol into a randomized protocol, we must replace the oracle wi ...

A hitting formula is a set of Boolean clauses such that any two of the clauses cannot be simultaneously falsified. Hitting formulas have been studied in many different contexts at least since [45] and, based on experimental evidence, Peitl and Szeider [53] ...

We consider the proof system Res introduced by Itsykson and Sokolov (Ann. Pure Appl. Log.'20), which is an extension of the resolution proof system and operates with disjunctions of linear equations over .We study characterizations of tree-like size and sp ...

Can every n-bit boolean function with deterministic query complexity k≪ n be restricted to O(k) variables such that the query complexity remains ω(k)? That is, can query complexity be condensed via restriction? We study such hardness condensation questions ...

Aaronson (STOC 2010) conjectured that almost k-wise independence fools constant-depth circuits; he called this the generalised Linial-Nisan conjecture. Aaronson himself later found a counterexample for depth-3 circuits. We give here an improved counterexam ...

We present a top-down lower-bound method for depth-4 boolean circuits. In particular, we give a new proof of the well-known result that the parity function requires depth-4 circuits of size exponential in n(1/3). Our proof is an application of robust sunfl ...

Artur Riazanov

Chat with Graph Search

Better Boosting of Communication Oracles, or Not

Proving Unsatisfiability with Hitting Formulas

Resolution Over Linear Equations: Combinatorial Games for Tree-like Size and Space

Hardness Condensation by Restriction

Generalised Linial-Nisan Conjecture Is False for DNFs

Top-Down Lower Bounds for Depth-Four Circuits