io-port.net

io-port 05927982 Watson, Thomas

Lift-and-project integrality gaps for the traveling salesperson problem. (English)

Electron. Colloq. Comput. Complex. 18, 97 (2011).

1

PDF XML AMS-TeX TEXT BIBTeX URL

io-port 05927981 Cohen, Gil; Raz, Ran; Segev, Gil

Non-malleable extractors with short seeds and applications to privacy amplification. (English)

Electron. Colloq. Comput. Complex. 18, 96 (2011).

2

PDF XML AMS-TeX TEXT BIBTeX URL

io-port 05927980 Behle, Christoph; Krebs, Andreas; Lange, Klaus-Jörn; Mckenzie, Pierre

Low uniform versions of NC1. (English)

Electron. Colloq. Comput. Complex. 18, 95 (2011).

3

PDF XML AMS-TeX TEXT BIBTeX URL

io-port 05927979 Lovett, Shachar

Computing polynomials with few multiplications. (English)

Electron. Colloq. Comput. Complex. 18, 94 (2011).

4

PDF XML AMS-TeX TEXT BIBTeX URL

io-port 05927978 Lu, Pinyan

Complexity dichotomies of counting problems. (English)

Electron. Colloq. Comput. Complex. 18, 93 (2011).

5

PDF XML AMS-TeX TEXT BIBTeX URL

io-port 05927977 Benjamin, Doerr; Carola, Winzen

Memory-restricted black-box complexity. (English)

Electron. Colloq. Comput. Complex. 18, 92 (2011).

6

PDF XML AMS-TeX TEXT BIBTeX URL

io-port 05927976 Hirsch, Edward A.; Itsykson, Dmitry; Nikolaenko, Valeria; Smal, Alexander

Optimal heuristic algorithms for the image of an injective function. (English)

Electron. Colloq. Comput. Complex. 18, 91 (2011).

7

PDF XML AMS-TeX TEXT BIBTeX URL

io-port 05927975 Cheraghchi, Mahdi; Klivans, Adam; Kothari, Pravesh; Lee, Homin K.

Submodular functions are noise stable. (English)

Electron. Colloq. Comput. Complex. 18, 90 (2011).

8

PDF XML AMS-TeX TEXT BIBTeX URL

io-port 05927974 Valiant, Paul

Distribution free evolvability of polynomial functions over all convex loss functions. (English)

Electron. Colloq. Comput. Complex. 18, 89 (2011).

9

PDF XML AMS-TeX TEXT BIBTeX URL

io-port 05927973 Hrubes, Pavel

How much commutativity is needed to prove polynomial identities? (English)

Electron. Colloq. Comput. Complex. 18, 88 (2011).

10

PDF XML AMS-TeX TEXT BIBTeX URL

io-port 05921375 Viderman, Michael

A combination of testability and decodability by tensor products. (English)

Electron. Colloq. Comput. Complex. 18, 87 (2011).

11

PDF XML AMS-TeX TEXT BIBTeX URL

io-port 05921374 Yamamoto, Masaki

A tighter lower bound on the circuit size of the hardest Boolean functions. (English)

Electron. Colloq. Comput. Complex. 18, 86 (2011).

12

PDF XML AMS-TeX TEXT BIBTeX URL

io-port 05921373 Chen, Yijia; Flum, Jörg; Müller, Moritz

Hard instances of algorithms and proof systems. (English)

Electron. Colloq. Comput. Complex. 18, 85 (2011).

13

PDF XML AMS-TeX TEXT BIBTeX URL

io-port 05921372 Tulsiani, Madhur; Wolf, Julia

Quadratic goldreich-levin theorems. (English)

Electron. Colloq. Comput. Complex. 18, 84 (2011).

14

PDF XML AMS-TeX TEXT BIBTeX URL

io-port 05921371 Allender, Eric; Wang, Fengming

On the power of algebraic branching programs of width two. (English)

Electron. Colloq. Comput. Complex. 18, 83 (2011).

15

PDF XML AMS-TeX TEXT BIBTeX URL

io-port 05921370 Ajtai, Miklós

Secure computation with information leaking to an adversary. (English)

Electron. Colloq. Comput. Complex. 18, 82 (2011).

16

PDF XML AMS-TeX TEXT BIBTeX URL

io-port 05921369 Arvind, Vikraman; Mukhopadhyay, Partha; Nimbhorkar, Prajakta

Erd{\H}os-Rényi sequences and deterministic construction of expanding Cayley graphs. (English)

Electron. Colloq. Comput. Complex. 18, 81 (2011).

17

PDF XML AMS-TeX TEXT BIBTeX URL

io-port 05921368 Husain, Mohammad Iftekhar; Ko, Steve; Rudra, Atri; Uurtamo, Steve

Storage enforcement with Kolmogorov complexity and list decoding. (English)

Electron. Colloq. Comput. Complex. 18, 80 (2011).

18

PDF XML AMS-TeX TEXT BIBTeX URL

io-port 05921367 Ben-Sasson, Eli; Grigorescu, Elena; Maatouk, Ghid; Shpilka, Amir; Sudan, Madhu

On sums of locally testable affine invariant properties. (English)

Electron. Colloq. Comput. Complex. 18, 79 (2011).

19

PDF XML AMS-TeX TEXT BIBTeX URL

io-port 05921366 Ron, Dana; Tsur, Gilad

On approximating the number of relevant variables in a function. (English)

Electron. Colloq. Comput. Complex. 18, 78 (2011).

20

PDF XML AMS-TeX TEXT BIBTeX URL